난이도

Gold 4

풀이 참고 유무

x

막힌 부분

1.첫 풀이 틀림
2.시간 초과로 인해 pypy사용

문제

문제 바로가기
N개의 영단어들이 주어졌을 때, 가장 비슷한 두 단어를 구해내는 프로그램을 작성하시오.

두 단어의 비슷한 정도는 두 단어의 접두사의 길이로 측정한다. 접두사란 두 단어의 앞부분에서 공통적으로 나타나는 부분문자열을 말한다. 즉, 두 단어의 앞에서부터 M개의 글자들이 같으면서 M이 최대인 경우를 구하는 것이다. "AHEHHEH", "AHAHEH"의 접두사는 "AH"가 되고, "AB", "CD"의 접두사는 ""(길이가 0)이 된다.

접두사의 길이가 최대인 경우가 여러 개일 때에는 입력되는 순서대로 제일 앞쪽에 있는 단어를 답으로 한다. 즉, 답으로 S라는 문자열과 T라는 문자열을 출력한다고 했을 때, 우선 S가 입력되는 순서대로 제일 앞쪽에 있는 단어인 경우를 출력하고, 그런 경우도 여러 개 있을 때에는 그 중에서 T가 입력되는 순서대로 제일 앞쪽에 있는 단어인 경우를 출력한다.

입력

첫째 줄에 N(2 ≤ N ≤ 20,000)이 주어진다. 다음 N개의 줄에 알파벳 소문자로만 이루어진 길이 100자 이하의 서로 다른 영단어가 주어진다.

출력

첫째 줄에 S를, 둘째 줄에 T를 출력한다. 단, 이 두 단어는 서로 달라야 한다. 즉, 가장 비슷한 두 단어를 구할 때 같은 단어는 제외하는 것이다.

예제 입력

9
noon
is
lunch
for
most
noone
waits
until
two

예제 출력

noon
noone

문제 검토

범위가 20,000이길래 O(n2)은 풀리지 않을 것 같아서 자료구조를 최대한 활요한 풀이로 접근했다.

풀이(python)

Python - 첫 풀이(오답)

#첫 풀이
from collections import defaultdict,deque
n=int(input())
srr=[input() for _ in range(n)]
cnt=0
#알파벳 딕셔너리 생성
alpha=defaultdict(list)
for x in range(97,122):
    alpha[chr(x)].append(0)

q=deque(srr)
maxlen=0
#최장 길이를 구함
for x in range(n):
    maxlen=max(len(srr[x]),maxlen)
cnt=0
tmp=[]
#최장 길이만큼 반복
for y in range(maxlen):
    check=0 
    #큐의 크기(단계를 거쳐낸 문자열들)만큼 반복 진행
    while q:
        s=q.popleft()
        #해당 번째 알파벳에 같은 것이 있으면 append
        for x in range(97,122):
            if len(s)>cnt:
                if s[cnt]==chr(x):
                    alpha[chr(x)].append(s)
    #알파벳중 밸류가 2보다 큰 것(0과 문자열 2개)은 단계를 통과한 것이므로
    for z in alpha.values():
        if len(z)>2:
            #check
            check+=1
    #check가 없다면 단계 통과 실패니까 break            
    if check==0:        
        break
    #이번 단계도 실패하지 않았다면 한번 더 측정을 위해 tmp를 초기화
    tmp=[]             
    #단계를 통과한 문자열들을 q에 append함
    for z in alpha.values():
        if len(z)>2:            
            tmp.append(z)
            for i in z:
                if i !=0:
                    q.append(i)
    #alpha 딕셔너리도 초기화
    alpha=defaultdict(list)
    for x in range(97,122):
        alpha[chr(x)].append(0)
    #다음번째 문자를 검사하기 위해 cnt를 +1해준다                    
    cnt+=1    
print(tmp)
if not tmp:
    print(srr[0])
    print(srr[1])
else:
    print(tmp[len(tmp)-1][1])
    print(tmp[len(tmp)-1][2]) 

어떻게 풀었는지도 기억이 안날정도로 바로 바로 필요한 부분을 고쳐나갔다.
테스트케이스와 다른 사람들이 막힌 테스트 케이스를 다 통과했지만, 37퍼 정도에서 오답처리가 되었다.

이 문제에 대한 정보가 많지 않아 어떤 반례가 있는 알아내지 못했고 결국 O(n2)의 시간을 써서 아래 풀이를 만들었다.

PyPy - O(n2) 풀이 - 정답

n=int(input())
srr=[input() for _ in range(n)]
for x in enumerate(srr):
    srr[x[0]]=x
def check(x,y):
    cnt=0
    min_len=min(len(x),len(y))    
    for i in range(min_len):
        if x[i]==y[i]:
            cnt+=1
        else:
            return cnt
    return cnt
maxlen=[-1,-1,0]        
for x in range(n):
    for y in range(x+1,n):    
        cur=check(srr[x][1],srr[y][1])            
        if maxlen[2] < cur:
            maxlen[0]=x
            maxlen[1]=y
            maxlen[2]=cur          
print(srr[maxlen[0]][1])
print(srr[maxlen[1]][1])

보시다시피 코드도 훨씬 짧아졌고 난이도도 내려간 느낌이다.
이 문제에서 핵심은 maxlen[2]<cur이다.
n의 범위를 입력된 순으로 처음부터 반복하기 때문에 가장 처음에 들어온 가장 긴 접두사가 그대로 정답이 된다.

python으로 제출하면 시간 초과로 오답처리가 되기 때문에 pypy로 제출해 정답을 얻어냈다.
하지만 문제에서 요구한 알고리즘이 아닌 것 같다고 생각이 되어 풀이를 보고 다시 풀어보았다.

Python - O(nlogn) 풀이 (정렬 알고리즘의 수행속도) - 정답

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

주석이 잘 되어 있는 코드를 가져왔다.
문자열을 정렬하게 되면 바로 앞 문자열과 비교했을 때 가장 긴 접두사의 길이를 낼 수 있어서 2개씩 n번만 반복하면 된다.

수행시간과 메모리를 대폭 줄일 수 있다.
이런 아이디어는 어떻게 얻는 건지 아직 모르겠다.

enumerate로 원래 가지고 있던 인덱스를 보유한채 정렬되게 된다.

걸린 시간

1:10:04 (첫 풀이 ~ O(n2) 풀이로 정답을 받았을 때 까지 기준)

총평

문자열을 정렬시키면 가장 긴 접두사를 갖고 있는 문자끼리 붙게 된다는 아이디어를 떠올리지 못했다.

구현은 아이디어를 잘 떠올려야 하는데 더 연습이 필요해보인다.