[알고리즘 문제풀이] 백준 1764 듣보잡

오늘 푼 문제는 백준 1764 - 듣보잡 입니다.

문제

김진영이 듣도 못한 사람의 명단과, 보도 못한 사람의 명단이 주어질 때, 듣도 보도 못한 사람의 명단을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 듣도 못한 사람의 수 N, 보도 못한 사람의 수 M이 주어진다. 이어서 둘째 줄부터 N개의 줄에 걸쳐 듣도 못한 사람의 이름과, N+2째 줄부터 보도 못한 사람의 이름이 순서대로 주어진다. 이름은 띄어쓰기 없이 영어 소문자로만 이루어지며, 그 길이는 20 이하이다. N, M은 500,000 이하의 자연수이다.

듣도 못한 사람의 명단에는 중복되는 이름이 없으며, 보도 못한 사람의 명단도 마찬가지이다.

출력

듣보잡의 수와 그 명단을 사전순으로 출력한다.

예제

입력

3 4
ohhenrie
charlie
baesangwook
obama
baesangwook
ohhenrie
clinton

출력

2
baesangwook
ohhenrie

풀이 방법

문자열 처리를 활용하는 문제지만 사실 핵심은 두 리스트에 중복된 값을 어떻게 빠르게 찾을 것이냐이다. 단순하게 리스트를 구성하고, contains를 사용하면 n번동안 m크기의 리스트를 탐색하는 과정을 계속해야 하는데, 존재하지 않거나 끝쪽에 존재한다면 아주 시간복잡도가 안 좋아지기 때문이다. 특히 각 50만이 범위이므로 이건 아니다 판단했다.

이것을 해결할 방법에 대해서 몇 가지 풀이법을 떠올렸다.

• 자료구조 잘 활용하기
  특정 값을 빨리 찾을 수 있는 자료구조에 듣도 못한 명단을 입력받는 동시에 저장하고, 보도 못한 명단을 입력받으며 바로 이 값이 자료구조에 있는지 찾는 것이다. 이 때 사용할 수 있는 자료구조로 Map이 떠올랐지만 정확하게 어떻게 자료구조를 구성할지, 즉 뭘 key-value로 하지라는 고민이 들었다. 그 와중에 다음 방법이 떠올랐다.
• 탐색을 빠르게 하면 되지 !
  결국 탐색 속도가 문제인 거니까 빠른 탐색을 할 수 있는 방법을 찾아볼까 하는 것이었다. binary search를 이용한다거나, 첫 알파벳을 기준으로 해시 테이블처럼 자료구조를 구성한다던가 등등.. 다양한 고려를 하던 중에 다음 방법이 떠올랐다.
• 정렬을 이용하자 !
  최종적으로 이 방법을 사용했기 때문에 아래 자세히 설명하겠다.

처음 정렬을 이용하겠다고 떠오른 옅은 방법은 두 개의 리스트를 각각 정렬하고 비교하는 방법이었다. 그치만 구체화하려 고민을 시작하자 맨 앞의 원소가 같지 않으면 두 리스트 중에서 어떤 값의 인덱스를 증가시키지..? 둘 다..? 이거 아니잖아 싶었다.

그럼 이걸 어떻게 해결하지의 답으로 두개의 리스트가 아니라 두 명단을 한 리스트에 저장하고 정렬하는 것이었다. 그러면 같은 값은 연달아 있을 수 밖에 없으니까 ! 이거닷 ! 그래서 두 명단을 같은 리스트에 입력받고 정렬한 후, 쭉 탐색하며 바로 뒤에 같은 값이 있는지 판단해서 있다면 결과 리스트에 넣어주는 방식으로 구현하였다. 이 방법은 입력 받는 동시에 리스트에 두고, m+n사이즈의 리스트를 정렬, 탐색하는 시간이면 된다 ! 심지어 정렬된 상태로 탐색하기 때문에 결과 리스트에도 정렬되어 들어가게 되기때문에 사이즈와 원소를 바로 출력해주면 된다.

처음에 말했듯 스트링 처리가 중요한 문제도 아니고 아이디어만 떠올리면 되는 문제인데, 그걸 떠올리는 과정도 구구절절 적었지만 사실 스르륵 자연스럽게 과정이 연결되면서 바로 떠올랐다. 뭐 사실 두 리스트에서 같은 값이 있는지 찾는 문제이기 때문에 쉽게 떠올릴 수 있는 아이디어다. 심지어 구현도 아주 간단하므로 아주 쉬운 문제였다고 생각한다 !

코드

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

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

        st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        String[] list = new String[n+m];
        for(int i=0; i<n+m; i++){
            list[i] = br.readLine();
        }
        Arrays.sort(list);
        ArrayList<String> result = new ArrayList<>();
        for(int i=0; i<list.length-1; i++){
            if(list[i].equals(list[i+1])){
                result.add(list[i++]);
            }
        }
        bw.write(result.size()+"\n");
        for (String s : result) bw.write(s + "\n");

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