[문자열/백준] 2179번 : 비슷한 단어

- 문제 : https://www.acmicpc.net/problem/2179

 

문제 이해 

- 문제 자체는 이해하기 어렵지 않았던 것 같다. 주어진 단어들 중에서 두 개의 단어의 접두사가 가장 긴 케이스를 찾고, 해당 단어 두 개를 출력하는 문제다. 

- 처음에는 3중 for문으로 일일히 가장 긴 접두사 찾고, 또 그거에 해당되는 단어들을 모두 찾았는데 그렇게 하니 메모리 초과가 발생했다. 

- 그래서 해시보다는 문자의 인덱스와 인덱스에 해당하는 최대 접두사 길이를 1차 배열에 저장해서 진행하면 된다.

 

풀이 로직

- enumerate를 이용해 입력된 단어들을 사전순으로 정렬하고, 인덱스도 같이 저장해준다. (인덱스, 단어) -> (1, 'for')

 

- 정렬된 단어를 순차 진행하면서 바로 옆에 있는 단어와 한글자씩 비교해 가면서 접두사의 길이가 최대인 경우를 찾는다.

   이때 접두사의 길이를 인덱스로 가지는 length 배열을 이용한다. (예시: length[3]은 인덱스 3 문자의 최대 접두사 길이를 의미한다)

 

- 접두사의 길이가 최대(max(length))이면서 가장 먼저 입력된 단어를 출력한다. 

  총 두 개의 문자열을 출력해야하는데, 첫번째 단어와 두번째 단어 구별은 first 변수로하고, 두번째 단어를 찾았을 때 첫번째 단어와 같은 접두사인지 확인하기 위해 pre 변수를 이용한다.

 

- 그래서 first == 0 인 경우는 첫번째 단어이므로, 바로 출력해주고, first와 pre를 출력한다.

 

- 두번째 단어는 first !=0 인 경우이고, 이때 최대 접두사의 길이를 가지고, 접두사가 일치할 때 해당 문자를 출력하고 끝내면 된다.

  

 

정답 풀이 

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

b = sorted(list(enumerate(a)), key = lambda x : x[1])

def check(a, b):
    count = 0
    for i in range(min(len(a), len(b))):
        if a[i] == b[i]:
            count += 1
        else:
            break
    return count

length = [0] * (n + 1)
max_length = 0

for i in range(n - 1):
    temp = check(b[i][1], b[i + 1][1])
    max_length = max(max_length, temp)
    
    length[b[i][0]] = max(length[b[i][0]], temp)
    length[b[i + 1][0]] = max(length[b[i + 1][0]], temp)
    
first = 0
for i in range(n):
    if first == 0:
        if length[i] == max(length):
            first = a[i]
            print(first)
            pre = a[i][:max_length]
    else:
        if length[i] == max(length) and a[i][:max_length] == pre:
            print(a[i])
            break

 

참고한 블로그 : https://lazypazy.tistory.com/26