https://www.acmicpc.net/problem/2179

접두사가 가장 비슷한 문자열을 찾는 문제이다.
문자열을 index와 함께 저장하고, 정렬한 후에 앞뒤로 문자열을 비교하면서 가장 큰 문자열을 찾는 방식을 사용했다.

Python

1차 실패

import sys

input = sys.stdin.readline

n = int(input())

words = list(enumerate(list(input().strip() for _ in range(n))))
origin = words[:]
words.sort(key=lambda x:(x[1], x[0]))

maxCnt = 0
answer = (-1, -1)
pre = ""

for i in range(n-1):
    idx = 0
    cnt = 0

    ai, a = words[i]
    bi, b = words[i+1]

    if a == b:
        continue

    while idx < len(a) and i < len(b):
        if a[idx] == b[idx]:
            cnt += 1
        else:
            break
        idx += 1
    if maxCnt < cnt:
        maxCnt = cnt
        answer = (min(ai, bi), max(ai, bi))

pre = origin[answer[0]][1][:maxCnt]

printcount = 0
print1 = ""
for o in origin:
    if printcount == 2:
        break

    if o[1][:maxCnt] == pre and print1 != o[1]:    
        print(o[1])
        printcount += 1
        print1 = o[1]

단어를 정렬하고 앞뒤로 비교하면서 가장 큰 접두사의 길이와 해당 단어들을 기억했다.
그리고 마지막에 해당 접두사를 가진 단어들을 앞에서부터 탐색하면서 두 번 출력했다. 그리고 3%에서 실패했다.

https://www.acmicpc.net/board/view/143309

여기 글의 테스트케이스를 실행했다.

input:
8
a
acd
ab
abc
ace
abd
acf
ade

output:
acd
ace

1차 코드의 출력은 ab, abc가 나왔다. 순서상으로는 acd가 나와야하는데 정렬하면 ab가 먼저 나와서 pre에 ab가 저장된 것 같다.

2차

import sys
input = sys.stdin.readline

n = int(input())

ip = []
for i in range(n):
  ip.append((input().strip(), i))
  
  
words = sorted(ip)

ans = [0] * (n)
maxCnt = 0
for i in range(n-1):
    cnt = 0
    a = words[i][0]
    b = words[i+1][0]
    
    for x in range(min(len(a), len(b))):
      if a[x] == b[x]:
        cnt += 1
  
    maxCnt = max(cnt, maxCnt)
    
    ans[words[i][1]] = max(ans[words[i][1]], cnt)
    ans[words[i+1][1]] = max(ans[words[i+1][1]], cnt)

chk = -1
pre = ""
for i in range(n):
  if chk == -1 and ans[i] == maxCnt:
    chk = i
    print(ip[i][0])
    pre = ip[i][0][:maxCnt]
  elif ans[i] == maxCnt and (maxCnt == 0 or pre == ip[i][0][:maxCnt]):
    print(ip[i][0])
    break
    

그래서 단어별로 최대 접두사의 길이를 저장하고 전체 접두사의 최대 길이를 maxCnt에 저장했다. 그리고 마지막에 maxCnt에 해당하는 단어들 중에서 처음 나오는 단어의 pre를 저장하고, 출력한 후 그 다음 단어들 중에서 pre로 시작하는 첫 번째 단어를 출력했다.

그러나 50%에서 계속 틀렸다. 코드를 살펴봐도 아무런 문제가 없어보였었다.

나중에 다시 보니까 문자열을 비교하는 과정에서 접두사가 같은 구간이 끝나면 멈춰야하는데 멈추지 않고 끝까지 비교해서 발생한 문제 같았다.

import sys
input = sys.stdin.readline

n = int(input())

ip = []
for i in range(n):
  ip.append((input().strip(), i))
  
  
words = sorted(ip)

ans = [0] * (n)
maxCnt = 0
for i in range(n-1):
    cnt = 0
    a = words[i][0]
    b = words[i+1][0]
    
    for x in range(min(len(a), len(b))):
      if a[x] == b[x]:
        cnt += 1
      else:
        break
    maxCnt = max(cnt, maxCnt)
    
    ans[words[i][1]] = max(ans[words[i][1]], cnt)
    ans[words[i+1][1]] = max(ans[words[i+1][1]], cnt)

chk = -1
pre = ""
for i in range(n):
  if chk == -1 and ans[i] == maxCnt:
    chk = i
    print(ip[i][0])
    pre = ip[i][0][:maxCnt]
  elif ans[i] == maxCnt and (maxCnt == 0 or pre == ip[i][0][:maxCnt]):
    print(ip[i][0])
    break
    

중간에 달라지면 멈추도록 break를 넣어주니까 정상적으로 동작했다.