[Algorithm] 5052 - 전화번호 목록

목차

---

1. 문제 설명

2. 접근 방식

3. 코드

 

 

 

 

 

1. 문제 설명

---

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

 

 

전화번호 목록이 주어질 때, 목록에 일관성이 있는가를 검사하는 문제이다.

일관성은 한 번호가 다른 번호의 접두어가 되는가를 기준으로 평가한다. 

• 한 번호가 다른 번호의 접두어가 된다. → 일관성 X
  • 긴급전화 : 911
  • 선영 : 91 12 54 26
• 한 번호가 다른 번호의 접두어가 아니다. → 일관성 O
  • 긴급전화 : 911
  • 수연 : 91 22 54 26

 

 

2. 접근 방식

---

일관성이 없는 경우는 접두어가 같다는 조건을 활용하기 위해 정렬 을 떠올렸다. 

입력값이 다음과 같이 주어졌을 때 

911

910

9112

912

9113

 

 

전화번호 목록을 String을 기준으로 정렬하면 아래와 같은 순서가 된다. 

910

911

9112

9113

912

 

이때 911, 9112, 9113은 접두어가 911로 같기 때문에 일관성이 없다고 할 수 있다. 

💡💡💡 즉, 정렬 뒤 전화번호[i + 1]가 전화번호[i]로 시작한다면 일관성이 없는 목록인 것이다. 💡💡💡

 

다만, input값을 유의해야한다. 

 

예제 입력1은 우리를 낚기 위해서 전화번호 목록을 공백 없는 아름다운 숫자로 보여주고 있다.

하지만 아름다움에 속아 전화번호 목록을 입력받은 그대로 사용하면 그대로 나락행에 빠진다.

 

 

문제를 자세히 읽어보면 예제 전화번호는 공백이 있는 것을 확인할 수 있다.

ex) 상근, 선영의 전화번호

따라서 입력값을 그대로 활용하지 말고, 공백을 제거한 문자열을 활용하자.

 

이를 코드로 구현하면 다음과 같다. 

 

 

3. 코드

---

import java.io.*;
import java.util.Arrays;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int t = Integer.parseInt(br.readLine()); // 테스트 케이스의 개수

        for(int i = 0; i < t; i++) {
            int n = Integer.parseInt(br.readLine()); // 전화번호의 수

            String[] phones = new String[n];
            for(int j = 0; j < n; j++) {
                phones[j] = br.readLine().replace(" ", "");
            }

            bw.write(isConsistent(phones) + "\n");
        }

        bw.flush();
        bw.close();
        br.close();
    }

    public static String isConsistent(String[] phones) {
        // 오름차순 정렬
        Arrays.sort(phones);

        // i + 1번째 i번째 포함한다면 일관성이 없는 것
        for(int i = 0; i < phones.length - 1; i++) {
            if(phones[i + 1].startsWith(phones[i])) return "NO";
        }

        return "YES";
    }
}

 

코드를 자세히 살펴보자. 

 

① replace 메소드

String[] phones = new String[n];
for(int j = 0; j < n; j++) {
    phones[j] = br.readLine().replace(" ", "");
}

 

전화번호 목록을 입력받을 때는 공백을 제거해주기 위해 replace 메소드를 활용했다. 

" "을 ""로 대체 = 공백을 제거한 문자열을 phones[j]에 담는다. 

 

② startsWith 메소드

// i + 1번째 i번째 포함한다면 일관성이 없는 것
for(int i = 0; i < phones.length - 1; i++) {
    if(phones[i + 1].startsWith(phones[i])) return "NO";
}

 

일관성이 없는가를 판단하기 위해 i + 1번째가 i번째로 시작하는지를 검사했다.

이때 접두어를 확인해야하므로 startsWith 메소드를 활용했다.