[BOJ 25542, Python] 约会地点

题目链接

[BOJ 25542](https://www.acmicpc.net/problem/25542

)

分类

暴力搜索算法、实现、字符串

说明

最初在比赛中遇到这道题时，我以为思路本身并不难。但这道题的实现比想象中要费工夫，而且7个月前的我连写Python代码都觉得非常吃力，因此没能解出这道题。

3个月前的我也曾试图解决这道题，但最终得出结论：构思的思路还需要额外的剪枝，结果再次受挫，只能暂时搁置这道题。

最近有了些空闲，加上想重新挑战之前没解出的题目，于是再次尝试，终于解出来了！不过，我仍然对这道题被归类为银牌题感到疑惑……

起初，我尝试仅使用已有的字符串来输出结果，但这显然存在反例，因此以失败告终。

之后尝试的代码虽然在实现上稍作改进，但依然只使用了已知的字符串，因此无法解决使用其他字符串的反例。附上代码如下。

import sys
from itertools import product

input = sys.stdin.readline

def is_similar(checker: str, target: str) -> bool:
	'''
    두 문자열이 비슷한지 확인하는 함수
    '''
    
    length = len(checker)
    counter = 0

    for idx in range(length):

        if checker[idx] != target[idx]:
            counter += 1

    if counter <= 1:
        return True
    
    else:
        return False

# 입력
store_number, name_length = map(int, input().split())

# 각 문자열의 동일 인덱스를 집합화
name_list = []
store_chr_arr = [set() for _ in range(name_length)]

for _ in range(store_number):
    each_name = list(input())
    name_list.append(each_name)

    for idx in range(name_length):
        store_chr_arr[idx].add(each_name[idx])

result = None

# 겹치지 않는 문자열의 Product를 비교
for each_name_combination in product(*store_chr_arr):
    target_name = ''.join(each_name_combination)
    
    is_answer = True

    for check_name in name_list:
        if not is_similar(target_name, check_name):
            is_answer = False
            break

    if is_answer:
        result = target_name
        break

if result is None:
    print('CALL FRIEND')

else:
    print(result)

虽然起初曾尝试使用未使用的字符，但因实现能力不足未能付诸实践，但通过该方法最终获得了“正解”判定。

解法代码

# 약속 장소

import sys

input = sys.stdin.readline

def is_similar(checker: str, target: str) -> bool:
    '''
    두 문자열이 비슷한지 확인하는 함수
    '''

    length = len(checker)
    counter = 0

    for idx in range(length):

        if checker[idx] != target[idx]:
            counter += 1

    if counter <= 1:
        return True
    else:
        return False

# 정보 입력
store_number, name_length = map(int, input().split())

name_list = []
first_checker = True

# 첫 문자열만 따로 분류하고 나머지는 이름 리스트에 기록
for _ in range(store_number):
    each_name = list(input().rstrip('\n'))

    if first_checker:
        target_name = each_name
        first_checker = False

    else:
        name_list.append(each_name)

# 첫 문자열을 통해 문자열 변형된 후보를 양산
result_set = set()

for idx in range(name_length):
    for alpha in range(65, 91):
        temp = target_name[:]
        temp[idx] = chr(alpha)
        result_set.add(''.join(temp))

# 확인하면서 후보를 소거
while result_set and name_list:

    now_check_name = name_list.pop()
    remove_target = set()

    for each_result in result_set:
        if not is_similar(now_check_name, each_result):
            remove_target.add(each_result)

    for each_target in remove_target:
        result_set.remove(each_target)

# 후보가 안 남았다면 문구를 출력, 후보가 남았다면 후보 중 하나를 출력한다.
if not result_set:
    print('CALL FRIEND')

else:
    print(result_set.pop())