[BOJ 25542, Python] 약속 장소

문제 링크

BOJ 25542

분류

브루트포스 알고리즘, 구현, 문자열

설명

처음 이 문제를 대회에서 마주했을 때 아이디어 자체는 어렵지 않다고 생각했었다. 하지만 생각보다 구현에 손이 많이 가는 문제였고 7달 전의 나는 파이썬 코드 짜는 것도 굉장히 버거워했기 때문에 이 문제를 풀지 못했다.

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