[백준] 2179 파이썬

문제

---

• 백준 2179 (골드 4)

백준 2179

n가지 단어가 주어질 때, 같은 접두사를 가진 두 가지 단어중에서 그 접두사의 길이가 최대인 두 단어를 출력하는 문제였다.
여기서 접두사의 길이가 최대인 경우가 여러 개일때에는 입력되는 순서대로 앞쪽에 있는 단어가 출력되도록 해야 했다.

내 코드

---

따로 알고리즘을 사용하기보다는 단순 구현으로 문제를 풀어봤다.
이중 for문을 돌면서 두가지 단어를 뽑아서 이를 처음부터 비교하는 형식으로 코드를 작성해 보았다.
접두사의 길이가 최대일 때마다 정답을 갱신하면서 진행하는 방식으로 구현하였다.

import sys
input = sys.stdin.readline

n = int(input())
words = [input().strip() for _ in range(n)]

ans_len=0
ans=[]
for i in range(n):
    for j in range(i+1,n):
        word1, word2 = words[i], words[j]
        min_len = min(len(word1), len(word2))
        max_len, length = 0, 0
        for k in range(min_len):
            if word1[k] != word2[k]:
                max_len = max(max_len, length)
                break
            else:
                length += 1
        if length == min_len:
            max_len = max(max_len, length)
        if ans_len < max_len:
            ans = [word1,word2]
            ans_len = max_len

print(ans[0])
print(ans[1])

파이썬으로 제출하니 시간초과가 발생하여서 혹시 몰라서 PyPy3로 다시 제출하였는데 통과하였다.
아마 파이썬으로도 통과할 수 있는 코드가 있을 것 같은데 알고리즘을 고민하고 다시 풀어봐야할 것 같다.