[Java] 백준(실버-4) 1764번 - 듣보잡

문제 풀이

---

이번 문제는 N명의 듣도 못한 사람과 M명의 보도 못한 사람 중에서 중복되는 사람의 명수와 사람을 나열해서 출력해야 한다.
입출력 테스트케이스를 유심히 보면 첫째줄엔 듣보잡의 수와 명단을 사전순으로 출력해야 함을 주의해야 한다.

아이디어 도출

• 이분탐색을 활용하여 N명과 M명의 사람중에서 중복된 사람을 찾는다.
• 중복된 사람을 별도의 리스트로 저장해두고, 오름차순(사전순)으로 정렬한다.
• 리스트의 길이와 리스트 명단을 차례대로 출력한다.

문제에 적혀있는대로 아이디어를 생각하였고, 쉽게 풀 수 있는 문제이다.

그럼 코드를 작성해보자.

StringTokenizer st = new StringTokenizer(br.readLine());
int N = Integer.parseInt(st.nextToken());
int M = Integer.parseInt(st.nextToken());
String[] arr = new String[N];

for(int i=0; i<N; i++) {
    arr[i] = br.readLine();
}

N과 M을 공백으로 입력받아 각각 저장하고, N명의 명단을 담을 String 배열 arr를 선언하자.
그리고 N만큼 반복하며 arr 배열에 N명의 듣도 못한 사람들을 저장한다.

Arrays.sort(arr);
ArrayList<String> list = new ArrayList<>();

for(int i=0; i<M; i++) {
    String s = br.readLine();
    if(Arrays.binarySearch(arr, s) >= 0) list.add(s);
}

N명의 돋도 못한 사람들을 저장했으니 이분탐색을 활용하기 위해 사전에 정렬해준다.
그리고 듣도 보도 못한 사람들(중복된 사람들)을 저장할 ArrayList도 하나 선언한다.
M만큼 반복하면서 M번째 보도 못한 사람들 중에서 듣도 못한 사람에 속해있는지 확인하고 듣도 보도 못한 사람이라면 list에 저장한다.

Collections.sort(list);
bw.write(list.size()+"\n");
for(String str : list) {
    bw.write(str+"\n");
}

사전순으로 듣도 보도 못한 사람들의 명단을 출력해야 하기에 Collections.sort() 메서드로 list를 오름차순으로 정렬해준다. 마지막으로 사람의 수를 출력하기 위해 list의 길이를 출력하고, list의 명단을 차례대로 출력하면 된다.

작성코드

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

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));

        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        String[] arr = new String[N];

        for(int i=0; i<N; i++) {
            arr[i] = br.readLine();
        }

        Arrays.sort(arr);
        ArrayList<String> list = new ArrayList<>();

        for(int i=0; i<M; i++) {
            String s = br.readLine();
            if(Arrays.binarySearch(arr, s) >= 0) list.add(s);
        }

        Collections.sort(list);
        bw.write(list.size()+"\n");
        for(String str : list) {
            bw.write(str+"\n");
        }

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

회고

• 중복된 데이터들을 별도의 ArrayList에 담아서 사전순으로 정렬하여 문제의 요구사항을 충족할 수 있었다.