[BOJ] 2179 비슷한 단어

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

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

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
    

처음에는 이렇게 했는데 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를 넣어주니까 정상적으로 동작했다.