[백준] 5052 : 전화번호 목록 (startsWith 메소드) - JAVA

백준 알고리즘 분류 (정렬)

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

 

# 문제

전화번호 목록이 주어진다. 이때, 이 목록이 일관성이 있는지 없는지를 구하는 프로그램을 작성하시오.

전화번호 목록이 일관성을 유지하려면, 한 번호가 다른 번호의 접두어인 경우가 없어야 한다.

예를 들어, 전화번호 목록이 아래와 같은 경우를 생각해보자

• 긴급전화: 911
• 상근: 97 625 999
• 선영: 91 12 54 26

이 경우에 선영이에게 전화를 걸 수 있는 방법이 없다. 전화기를 들고 선영이 번호의 처음 세 자리를 누르는 순간 바로 긴급전화가 걸리기 때문이다. 따라서, 이 목록은 일관성이 없는 목록이다.

 

# 예제

입력 : 첫째 줄에 테스트 케이스의 개수 t가 주어진다. (1 ≤ t ≤ 50) 각 테스트 케이스의 첫째 줄에는 전화번호의 수 n이 주어진다. (1 ≤ n ≤ 10000) 다음 n개의 줄에는 목록에 포함되어 있는 전화번호가 하나씩 주어진다. 전화번호의 길이는 길어야 10자리이며, 목록에 있는 두 전화번호가 같은 경우는 없다

2
3
911
97625999
91125426
5
113
12340
123440
12345
98346

 

출력 : 각 테스트 케이스에 대해서, 일관성 있는 목록인 경우에는 YES, 아닌 경우에는 NO를 출력

NO
YES

 

 

# 필요개념

이 문제를 푸는 절차는 다음과 같다.

• 한줄씩 받아 공백을 제거한다. ( 91 12 54 26 이런 입력을 91125426 이렇게 바꿔준다)
• 문자열에 다른 문자열이 포함되는지 확인한다.

 

공백제거

공백제거를 위해 String의 replace메소드를 사용하였다. replace(olderStr, newStr) 로 사용할 수 있다.

 

포함여부 확인

처음에는 이 문제를 substring을 이용하여 풀려고 했다. 각 문자열의 길이순으로 정렬하여 이중for문을 사용하면 될 것이라고 생각했었는데, 역시나 시간초과가 걸렸다. 이 문제는 시간복잡도가 O(N^2)을 넘어가면 시간초과 위험이 있어보였다. 

게다가 substring의 시간복잡도가 O(N)이라 삼중반복을 한 것이나 다름없게 되었다 😂 

 

이후 코드를 보며 substring의 대체제를 찾아 split을 사용해보았으나 여전히 시간초과 문제가 생기는 것을 확인할 수 있었다. 그래서 접근을 다르게 가져보았다.

 

정렬을 문자열 길이가 아닌 문자의 오름차순 정렬로 하는 것이다. 아래 예시를 보자.

 

만약 [ab, abdd, acd,aadd] 라는 배열이 있다고 가정할 때, 문자의 오름차순 정렬을 하게 되면 [aadd, ab, abdd, acd] 이라는 결과가 나온다. 이 경우 비슷한 구성의 문자열끼리 줄세워질 수밖에 없기 때문에, i번째 문자열과 i+1번째 문자열만 봐주면 된다. 즉, 이중반복문을 쓰지 않아도 된다. i+1의 문자열이 i문자열로 시작하는지 여부만 판단하면 문제를 해결할 수 있다.

 

이때 substring을 쓰지 말고, startsWith() 를 사용한다.

 

 

boolean startsWith(String pre)

• 비교대상 문자열이 pre 값으로 시작되는지 여부를 bool 타입으로 반환한다.
• 비슷한 메소드로는 endsWith(String end) 가 있고, 이는 end 값으로 끝나는지 여부를 반환한다.

 

# Code

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

import static java.lang.Math.*;

public class Main{
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        int n = Integer.parseInt(br.readLine());
        for (int i = 0 ; i < n ; i++) {
            int m = Integer.parseInt(br.readLine());
            List<String> lst = new ArrayList<>();
            for (int j = 0 ; j < m ; j++) {
                String s = br.readLine().replace(" ", "");
                lst.add(s);
            }
            Collections.sort(lst);

            boolean b = false;
            for (int j = 0 ; j < m  - 1; j++) {
                if (lst.get(j + 1).startsWith(lst.get(j))) {
                    b = true;
                    break;
                }
            }
            if (b) sb.append("NO").append("\n");
            else sb.append("YES").append("\n");
        }
        System.out.println(sb);
    }
}

 

# 결과