해당 포스팅은 백준 5052번 전화번호 목록 풀이를 다룬다. 문제 링크
코드는 javascript로 작성하였다.
문제
1. 문제 설명
전화번호 목록이 주어진다. 이때, 이 목록이 일관성이 있는지 없는지를 구하는 프로그램을 작성하시오.
-
전화번호 목록이 일관성을 유지하려면,
한 번호가 다른 번호의 접두어인 경우가 없어야한다. -
예제:
아래 번호는 긴급전화 911이 선영의 번호의 접두어이다.
따라서 이 목록은 일관성이 없는 목록이다.긴급전화:
911
상근:97 625 999
선영:91 12 54 26
2. 입력
- [첫째 줄]: 테스트 케이스의 개수 t (1 ≤ t ≤ 50)
- [각 테스트 케이스]:
- [테스트 케이스 첫째 줄]:
- 전화번호의 수 n (1 ≤ n ≤ 10000)
- [테스트 케이스 n개의 줄]:
- 목록에 포함되어 있는 전화번호가 하나씩 주어진다.
- 전화번호의 길이는 길어야 10자리이며, 목록에 있는 두 전화번호가 같은 경우는 없다.
- [테스트 케이스 첫째 줄]:
3. 출력
각 테스트 케이스에 대해서, 일관성 있는 목록인 경우에는 YES, 아닌 경우에는 NO를 출력한다.
풀이
처음에는 각 전화번호에 대해 2중 loop를 돌려 모든 전화번호들과 비교를 해주었다. 해당 문제는 n이 10000 이하이므로 그렇게 풀어도 괜찮으나, 실제 문제들은 그렇지 않으므로 다른 풀이를 생각해보아야 한다.
다른 사람들의 풀이를 보니 sort로 오름차순으로 정렬한다음 단일 loop를 하는 좋은 풀이가 있었다 (참고 사이트). 따라서 어떻게 해당 문제를 sort와 단일 loop를 통해 이용해 풀 수 있는지 설명하겠다.
1. 로직
예제인 아래 전화번호 목록으로 설명하겠다.
긴급전화:
911
상근:97 625 999
선영:91 12 54 26
-
전화번호를 사전순으로 정렬하자.
- [911, 91125426, 97625999]
-
사전순으로 정렬하면 [0]의 값이 [2]의 값의 접두어인지 확인할 필요가 없다.
- [0]이 [2]의 접두어라면 [1]도 [2]의 접두어임을 보장하기 때문이다.
-
[1]의 값이 [0]의 접두어인지 확인할 수는 없다.
-
정렬했기 때문에 [0]이 [1]의 접두어일 수 있다.
→911은91125426의 접두어다. -
하지만 [1]은 [0]의 접두어일 수 없다.
사전순 sort를 할 때 [1]이 [0]의 접두어가 되려면 [1]과 [0]이 같은 값이어야 한다. 하지만 문제에서목록에 있는 두 전화번호가 같은 경우가 없다고 했으므로 불가능하다.→
91125426는911의 접두어가 될 수 없다.
-
-
따라서 단일 loop를 돌면서 el[i-1]가 el[i]의 접두어인지를 판별하면 답을 구할 수 있다.
2. 예제
예제를 통해 해당 로직을 설명하겠다.
아래 전화번호 목록은 일관성 없는 목록이다.
113
12340
123405
12345
98346
- 오름차순 정렬을 한다.
- [113, 12340, 123405, 12345, 98346]
- 단일 loop를 돌리면서 el[i-1]가 el[i]의 접두어인지를 판별하자.
12340은123405의 접두어이므로 일관성이 없는 목록이다.
전체 코드
const input = require('fs').readFileSync('/dev/stdin').toString().split('\n').slice(0, -1);
const t = +input.shift();
const tests = [];
while (input.length !== 0) {
const n = Number(input.shift());
const test = input.splice(0, n).sort();
let result = "YES";
for (let i = 1; i < test.length; i++) {
if (test[i].startsWith(test[i-1])) {
result = "NO";
break;
}
}
tests.push(result);
}
console.log(tests.join("\n"));(ref)
