[Baekjoon] 백준 5052번: 전화번호 목록 (JAVA)

백준 5052

5052번: 전화번호 목록

[ 문제 풀이 ]

프로그래머스에도 있는 문제로, 2가지 방법으로 풀 수 있습니다. 먼저 HashSet<>을 활용하여 String 클래스에 있는 substring()을 이용하여 풀어보겠습니다.

HashSet<>에 전화번호를 저장하고, String[] 에도 저장하여 저장한 번호들을 하나씩 순회하며 0번째 인덱스부터 문자열을 잘라가며 잘린 앞부분의 문자열과 같은 문자열이 있는지 확인하면 됩니다.

String[] phonesArr = new String[n];
for (int j = 0; j < n; j++) {
    String phoneNumber = br.readLine();
    phones.add(phoneNumber);
    phonesArr[j] = phoneNumber;
}

for (int j = 0; j < n; j++) {
    for (int k = 0; k < phonesArr[j].length(); k++) {
        if (phones.contains(phonesArr[j].substring(0, k))) {
            flag = false;
            break;
        }
    }
}

 

두 번째 방법은 문자열을 정렬하는 것입니다. 문자열로 정렬하면 숫자가 큰 순이 아니라, 문자열의 앞부터 차례대로 순서에 따라 정렬하게 됩니다.
ex) ["123", "37", "125", "1244"] => ["123", "1244", "125", "37"]

따라서, 정렬을 한 후 startsWith()을 활용하여 해당 접두어가 있는지 확인해주면 됩니다.

private static boolean check(int n, String[] str) {
    for (int i = 0; i < n-1; i++) {
        if (str[i+1].startsWith(str[i])) {
            return false;
        }
    }

    return true;
}

 

[ 코드 ]

1) HashSet<> 활용

import java.io.*;
import java.util.HashSet;

public class Main {
    private static HashSet<String> phones;

    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());
            phones = new HashSet<>();
            boolean flag = true;

            String[] phonesArr = new String[n];
            for (int j = 0; j < n; j++) {
                String phoneNumber = br.readLine();
                phones.add(phoneNumber);
                phonesArr[j] = phoneNumber;
            }

            for (int j = 0; j < n; j++) {
                for (int k = 0; k < phonesArr[j].length(); k++) {
                    if (phones.contains(phonesArr[j].substring(0, k))) {
                        flag = false;
                        break;
                    }
                }
            }

            if (flag) bw.write("YES");
            else bw.write("NO");

            bw.newLine();
        }

        bw.flush();
    }
}

 

2) 정렬, startsWith() 활용

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[] phonesArr = new String[n];
            for (int j = 0; j < n; j++) {
                String phoneNumber = br.readLine();
                phonesArr[j] = phoneNumber;
            }

            Arrays.sort(phonesArr);
            bw.write(check(n, phonesArr) ? "YES" : "NO");
            bw.newLine();
        }

        bw.flush();
    }

    private static boolean check(int n, String[] str) {
        for (int i = 0; i < n-1; i++) {
            if (str[i+1].startsWith(str[i])) {
                return false;
            }
        }

        return true;
    }
}