[백준] 5052 전화번호 목록

📖 문제

---

🧑🏻‍💻 풀이 과정

1) 문제 이해 및 접근

번호가 짧은 것을 기준으로 하여 긴 문자열의 접두사에 포함되는지 파악하기 위해서 정렬을 시도하였습니다.

정렬은 앞글자가 일치하는 순서대로, 길이 순서대로 정렬하였습니다.

 

짧은 글자를 순서대로 기준으로 하여 가장 앞자리를 비교하며 일치하는지 여부를 판별하였습니다.

만약 현재 비교한 자리의 숫자가 더 큰숫자가 있다면 기준의 뒤의 다른 문자들은 모두 일치하지 않으므로 반복문을 종료하고 기준 숫자를 변경해주었습니다.

2) 알고리즘

• 정렬
• 문자열 비교

3) 풀이 코드

사용 언어 - Python

import sys
sys.stdin = open('input.txt')

T = int(sys.stdin.readline())                   # 테스트 케이스 개수

for _ in range(T):
    N = int(sys.stdin.readline())               # 전화번호의 개수
    li = list(sorted([sys.stdin.readline().strip() for _ in range(N)]))     # 전화번호를 숫자 순으로, 길이 순으로 정렬
    answer = False                                  # 일관성 있는 목록인지 판별 여부, 일관성이 없는 경우 True 가 됨

    for i in range(N):                              # 앞에 번호들부터 순서대로 반복
        next_num = False                            # 다음 숫자를 탐색하는지 판별하는 신호 변수
        for j in range(i+1, N):                     # 비교하는 기준 숫자의 다음 번호부터
            if next_num:
                break

            for k in range(len(li[i])):             # 가장 앞 글자의 숫자부터 비교
                if int(li[i][k]) < int(li[j][k]):   # 현재 비교하는 숫자가 비교하는 번호가 더 크다면, 기준 번호를 다음 번호로 넘김
                    next_num = True
                    break
                elif int(li[i][k] > li[j][k]):      # 현재 비교하는 숫자가, 기준 숫자가 더 크다면
                    break                           # 비교하는 번호 다음 번호로 이동
            else:                                   # 일관성 있는 숫자인 경우
                answer = True                       # 이후 탐색 모두 종료
        
        if answer:              # 출력
            print('NO')
            break
    else:
        print('YES')

---

📝 결과 및 학습한 내용

1) 어려웠던 내용

처음에 단순하게 2중 반복문으로 문자열을 비교하였으나, 비교의 횟수가 매우 많아서 시간초과가 발생했습니다.

시간 초과를 해결하기 위해 문자열 비교를 위한 규칙을 발견하기 어려웠습니다.

2) 새롭게 학습한 내용

- 특별히 없습니다.

---

🔗 문제 링크

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

5052번: 전화번호 목록

 

 

※ 오류 및 오타, 다른 의견이 있는 경우 댓글을 남겨주시면 감사하겠습니다