[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())