[BOJ 25542, Python] Meeting Place

Problem Link

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

)

Categories

Brute Force Algorithm, Implementation, Strings

Description

When I first encountered this problem in a contest, I thought the idea itself wasn’t difficult. However, it turned out to be more labor-intensive to implement than I expected, and since I was struggling even with writing Python code seven months ago, I couldn’t solve it.

I also tried to solve this problem three months ago, but I concluded that my initial idea required additional pruning, so I had to set the problem aside once again.

Recently, I’ve had some free time and felt the urge to revisit problems I hadn’t been able to solve before, so I gave it another shot—and finally managed to solve it! However, I still have my doubts about why this is classified as a Silver-level problem...

At first, I tried to generate results using only the given strings, but this inevitably failed because counterexamples existed.

The code I tried next included a bit more implementation, but since it still relied solely on the given strings, it couldn’t handle counterexamples using other strings. I’ve attached the code below.

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)

I had tried using unused characters at first, but my implementation skills weren’t sufficient enough to actually put it into practice; however, I was able to get a “Correct” result using that method.

Solution Code

# 약속 장소

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