[Python] BOJ(백준) 5052번 - 전화번호 목록

링크

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

난이도(solved.ac 참고)

골드4

풀이(오답)

처음에 접근을 잘못해서 여러번 틀렸다. sort를 한 뒤 처음 값을 기준으로 그 다음 값들부터 접두사에 처음 값이 들어가는지 여부로 판단을 했는데, 그렇게 하면 두번째 접두어가 세번째 입력의 접두어로 들어가있을 수 있기 때문에 접근이 잘못되었다.

1010
1234
12345

이런 경우가 있다고 해보면, 1010을 기준 값으로 잡고 1234부터 반복문을 진행하게 되는데, 이 경우 전부 1010이 들어가지는 않지만 1234는 12345에 들어가기때문에 NO가 나오는 게 정답이다. 근데 이전 코드대로 따르면 YES가 나왔다.

풀이(정답)

위와 같은 반례가 있을 수 있기 때문에, 저 예시의 경우 1010과 1234를 비교, 그 다음 1234와 12345를 비교, 이런 식으로 진행이 되도록 바꾸었다. 이렇게 되면 sort를 했으므로 인접한 두 값은 만약 더 긴 값이 더 짧은 값을 포함하고 있다면 무조건 NO가 나올수밖에 없다.