[백준/파이썬] 5052번 전화번호 목록

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

5052번: 전화번호 목록

문제

---

문제 해석

전화번호 목록이 주어진다.

전화번호 목록이 일관성을 유지하는 것이 이 문제의 목표이다.

일관성이란 원하는 전화번호를 누를 때 원하는 전화번호가 정상적으로 누르도록 작동하는 것이다.

즉, 911이라는 전화번호가 존재하고, 91125426이라는 전화번호가 존재하면 두번째 전화번호를 누르면 911이 전화가 걸리기 때문에 조건에 어긋난다.

---

코드

input = __import__('sys').stdin.readline

def check(a, b):
    if a > b:
        l, s = a, b
    else:
        s, l = a, b
    if s == l[:len(s)]: return 0
    return 1

t = int(input())
ans = ["YES"] * t
for case in range(t):
    # Input
    n = int(input())
    arr = []
    for i in range(n): arr.append(input().strip())
    # 일관성 비교를 위한 내림차순 정렬
    arr = sorted(arr, reverse = 1)
    
    # 비교
    stack = []
    for i in range(n):
        if not stack:
            stack.append(arr[i])
        else:
            # 길이가 작을때만 비교
            if len(arr[i]) < len(stack[-1]):
                for j in range(len(stack)):
                    flag = check(arr[i], stack[j])
                    if not flag: ans[case] = "NO"
                    stack.append(arr[i])
            # 길이가 작지 않다면 이전 값들을 더이상 비교할 필요가 없음
            else:
                stack = [arr[i]]
# Output
for k in ans: print(k)

---

테스트 케이스

---

4. 문제 풀이

3번의 시도를 통해 문제를 해결했다.

먼저 입력시마다 주어진 조건을 확인하는 방식으로 구현을 했다.

 

전화번호가 입력될 때마다. 입력되기전에 이미 입력된 전화번호와 비교를 해주었다.

최대한 시간을 줄이기 위해 전화번호의 끝이 일치해야 전화번호가 같은지 탐색하도록 해주었다.

하지만 당연하게도 시간초과가 발생했다.

 

그러던 중 문제를 다시 읽어보았다.

일관성 규칙에는 다른 번호의 접두어가 없어야 했다.

즉 12345 전화번호와 123 전화번호는 123이란 접두어가 존재하지만

212345와 123은 앞부분에 2가 존재하기에 123이 접두어가 되지 못한다.

 

하지만 이를 수정한다고 시간초과를 해결할 순 없었다.

시간을 줄일 방법이 생각나지 않아 규칙을 찾아보려고 여러수를 넣어 보았다.

14452
133546
12345 
123 
122 
12

다음의 수들은 내림차순으로 정렬된 모습이다.

첫번째 14452 이후 오는 133546의 값은 길이 더 길기 때문에 어떠한 경우에도 접두어가 될 수 없다.

두번째 12345와 133546은 접두어가 될 길이는 만족하지만 수는 만족하지 않는다.

세번째 123은 12345의 접두어이다.

네번째 122는 122가 와야만 접두어가 가능하다. 하지만 이 경우는 문제에서 없다고 주어졌기때문에 길이가 같은 경우에는 접두어가 될 수 없다.

다섯번째 12는 122의 접두어가 될 수 있다.

 

즉 내림차순으로 정렬했을때

어떠한 값 이후에 오는 값의 길이가 더 길거나 같다면 이전값의 접두어가 절대 될 수 없다.

따라서 이를 구현하기위해 스택을 사용했다.

 

Stack의 최상단 값과 비교하여 해당 값보다 길이 더 작다면 비교를 한다.

접두어의 결과가 어떻든 다음 오는 값 또한 같을 경우가 존재하기에 이 경우엔 스택에 계속 집어 넣는다.

만약 더 길거나 같은 값이 오게된다면 절대 스택안에 존재하는 값은 접두어 관계가 될 수 없다.

따라서 스택을 초기화해주고 현재 비교한 값만 스택에 넣어준다.

 

이를 반복하며 접두어가 존재할때마다 ans 배열의 YES값을 NO 바꾸어주며 해결했다.