[백준] 2179번: 비슷한 단어

정답 비율과 푼사람이 적었지만 문제 해결 알고리즘은 쉽게 생각나서 이 문제를 골랐지만 의외로 복잡했고, 코드가 지저분해졌었다. 그래서 다른 사람의 도움을 얻어보려 열심히 구글링을 해봤지만 맞힌 사람이 63명 밖에 없었고(2022.4.18기준) 파이썬으로 풀이를 적어둔 사람은 한명도 보지 못했다...ㅎㅎ

2179번: 비슷한 단어

📘풀이

1. 입력된 단어들을 사전순으로 정렬한다. 이때 인덱스도 같이 저장해준다.
2. 정렬된 단어들을 한글자씩 비교해가면서 접두사의 길이가 최대인 경우를 찾는다.
3. 접두사의 길이가 최대이면서 가장 먼저 입력된 단어를 출력한다.

 

💻코드

n = int(input())
a = [input() for _ in range(n)]

# n = 9
# a = ["noon", "is", "for","lunch","most","noone","waits","until","two"]

# 입력받은 문자들을 인덱스와 함께 사전순으로 정렬한다.
b = sorted(list(enumerate(a)),key = lambda x: x[1])
# b = [(2, 'for'), (1, 'is'), (3, 'lunch'), (4, 'most'), (0, 'noon'), (5, 'noone'), (8, 'two'), (7, 'until'), (6, 'waits')]

# check 함수는 글자 하나하나가 서로 같은지 탐색
def check(a, b):
    cnt = 0
    for i in range(min(len(a), len(b))):
        if a[i] == b[i]: cnt += 1
        else: break
    return cnt

# 최장 접두사를 가진 문자열 담아둘 리스트 생성
length = [0] * (n+1)
maxlength = 0

for i in range(n-1):
    # 인접한 두개의 문자열을  check함수에 대입
    # tmp 값은 동일한 접두사의 길이
    tmp = check(b[i][1], b[i+1][1])
    # 최장 접두사 길이 갱신
    maxlength = max(maxlength, tmp)
    
    # b[i][0]은 문자가 입력된 순서, 즉 인덱스
    # length 에 입력된 순서에 자기 접두사 길이를 저장
    # max 함수로 이전 값하고 현재 값하고 비교하여 집어넣음
    length[b[i][0]] = max(length[b[i][0]], tmp)
    length[b[i+1][0]] = max(length[b[i+1][0]], tmp)
    # length = [4, 0, 0, 0, 0, 4, 0, 0, 0, 0]
    
first = 0
for i in range(n):
    # 입력된 순서대로 접두사의 길이 비교
    if first == 0:
        # 만약 현재 접두사의 길이가 최장접두사라면
        if length[i] == max(length):
            # 제일 먼저 입력된 문자 출력
            first = a[i]
            print(first)
            pre = a[i][:maxlength]
    else:
    	# 다음으로 입력되었된 값들 중 최장 접두사 출력후 종료
        if length[i] == max(length) and a[i][:maxlength] == pre:
            print(a[i])
            break

 

📎문제링크: https://www.acmicpc.net/problem/2179