백준 #2179 비슷한 단어

 

문제를 너무 단순하게 생각했었다

반례 보면서 열심히 수정함

 

내가 간과한 것들

1. 길이는 같지만 문자는 다른 접두어가 여러개 있을 수 있음

2. 나는 단어들을 sort 하고 오로지 인접한 단어만 있다고 생각했는데, 세개 이상 같은 경우일 수도 있음

ex) aaa aac aab 이 경우 sort하면 aaa aab aac 순서이지만 우선순위는 원본 순서이기 때문에 정답은 aaa aac가 된다

 

그래서 prefix_arr 에 최장길이의 접두어들을 저장해놓고(한개일수도 있고 여러개일수도 있음)

다시 원본 리스트에서 각 접두어를 포함하는 단어를 접두어별로 구분해서 index 모아놓음

그 중 제일 작은 index 포함하고 있는 리스트에서 맨 앞 두개가 정답이다

 

n = int(input())
arr1 = []
for _ in range(n):
    arr1.append(input())
prefix_max = 0  #최장 접두어길이
finalarr = []   #최종후보리스트
prefix_arr = [] #최장 접두어 리스트

arr = list(set(arr1))   #중복제거 
arr.sort()

for i in range(n-1):
    prefix_len = 0    #이번 접두어길이
    leng = min(len(arr[i]),len(arr[i+1]))

    for j in range(leng):
        if arr[i][j] == arr[i+1][j]:
            prefix_len += 1
        else:
            break

    if prefix_len > prefix_max: #이번 접두어가 기존 접두어보다 길다면
        prefix_max = prefix_len #갱신
        prefix_arr = [arr[i][0:prefix_len]] #접두어 문자열 리스트에 추가

    elif prefix_len == prefix_max:  #이번 접두어가 기존 접두어와 같은 길이면
        if arr[i][0:prefix_len] not in prefix_arr:  #길이만 같고 다른 문자열이면 리스트에 추가
            prefix_arr.append(arr[i][0:prefix_len])


for prefix in prefix_arr:  #접두어 리스트 순회
    wordidx = []
    for i in range(n):  #원본 arr 리스트 순회
        if prefix == arr1[i][:prefix_max]: #단어가 이 접두어 포함하고 있다면
            wordidx.append(i)   # tempidx에 이 단어의 index 추가, 여기는 어차피 오름차순으로 append됨

    if len(wordidx) != 0:   # tempidx가 비어있지 않다면
        finalarr.append(wordidx)    #최종후보에추가


finalarr.sort() #작은 index우선

print(arr1[finalarr[0][0]])
print(arr1[finalarr[0][1]])