BOJ 5052
위 문제는 백준 사이트의 알고리즘 5052 문제에 관한 설명입니다.
문자열 처리 연습용 문제입니다.
전화번호 목록
전화번호 목록이 주어진다. 이때, 이 목록이 일관성이 있는지 없는지를 구하는 프로그램을 작성하시오.
전화번호 목록이 일관성을 유지하려면, 한 번호가 다른 번호의 접두어인 경우가 없어야 한다.
예를 들어, 전화번호 목록이 아래와 같은 경우를 생각해보자
- 긴급전화: 911
- 상근: 97 625 999
- 선영: 91 12 54 26
이 경우에 선영이에게 전화를 걸 수 있는 방법이 없다.
전화기를 들고 선영이 번호의 처음 세 자리를 누르는 순간 바로 긴급전화가 걸리기 때문이다.
따라서, 이 목록은 일관성이 없는 목록이다.
입력
첫째 줄에 테스트 케이스의 개수 t가 주어진다.
(1 ≤ t ≤ 50) 각 테스트 케이스의 첫째 줄에는 전화번호의 수 n이 주어진다.
(1 ≤ n ≤ 10000) 다음 n개의 줄에는 목록에 포함되어 있는 전화번호가 하나씩 주어진다.
전화번호의 길이는 길어야 10자리이며, 목록에 있는 두 전화번호가 같은 경우는 없다.
출력
각 테스트 케이스에 대해서, 일관성 있는 목록인 경우에는 YES, 아닌 경우에는 NO를 출력한다.
소스코드
package day0913;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Comparator;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int t = Integer.parseInt(br.readLine());
for (int i = 0; i < t; i++) {
int n = Integer.parseInt(br.readLine());
String[] numberList = new String[n];
boolean flag = true;
for (int j = 0; j < n; j++) {
numberList[j] = br.readLine();
}
Arrays.sort(numberList, new Comparator<String>() {
@Override
public int compare(String o1, String o2) {
return o1.compareTo(o2);
}
});
for (int j = 1; j < n; j++) {
if (numberList[j].startsWith(numberList[j - 1])) {
flag = false;
break;
}
}
System.out.println(flag ? "YES" : "NO");
}
}
}
해당 문제는 문자열 처리를 하는 문제였습니다.
처음엔 간단하게 생각해서 완전탐색처럼 구성해서, 하나하나 확인했는데 시간초과가 났습니다.
그래서 다른방법(startsWith( ))을 사용했습니다.
순차적으로 코드를 따라가 봅시다.
numberList에 전화번호들을 넣어줍시다.
이후 문자열을 어순에 맞게 정렬시켜 줍니다.
98346
12340
113
12345
123440
위의 입력이 들어갔을 때 Arrays.sort를 위처럼 사용하면
113
12340
123440
12345
98346
위와 같은 순서로 정렬이 됩니다.
startsWith()를 알아봅시다.
String함수에 있는 boolean startsWith(String prefix)는
비교 대상의 문자열이 입력된 문자열(prefix) 값으로 시작되는지 여부를 boolean값으로 반환시켜줍니다.
예를들어 911의 값이 91145와 비교했을때 911이 안에 들어가기 때문에 이것은 포함이 됩니다.
순차적으로 앞에서부터 비교할 것이기 때문에 정렬이 필요했고, 이러한 이유로 sort시켜 줬었습니다.
이제 비교를 하고 값을 반환하면 됩니다!