문제 : https://www.acmicpc.net/problem/1746

풀이방법

일단 총 세가지 방법을 시도해보았습니다. List를 이용한 두 번의 시도와 Set을 이용한 한 번의 시도를 했습니다.

List를 이용한 방법

시간 초과 뜸! 아마 for문이 중첩되어 있어서 시간 초과가 나는 것으로 예상됨!

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

public class BOJ1764 {

    public static void main(String[] args) throws IOException {
        BufferedReader bf=  new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st= new StringTokenizer(bf.readLine()," ");
        List<String> noEarList = new ArrayList<>();
        List<String> noEyeList = new ArrayList<>();
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());

        for(int i=0;i<N;i++)
            noEarList.add(bf.readLine());
        for(int i=0;i<M;i++)
            noEyeList.add(bf.readLine());
        int count=0;
        StringBuilder sb = new StringBuilder();
        for(int i=0;i<N;i++){
            String person = noEarList.get(i);
            for(int j=0;j<M;j++){
                if(noEyeList.get(j).equals(person)){
                    count++;
                    sb.append(noEyeList.get(j)+"\n");
                }
            }
        }

        System.out.println(count);
        System.out.println(sb.toString());

    }
}

List를 이용한 다른 방법

두 번째로 시도한 방법은 List를 사용하지만, 다른 방식입니다. 이것은 처음에 N개를 입력 받고 List에 추가한 후에, 두 번째 M을 입력받을 때 바로 List에 포함되어 있는지 검사를 진행합니다. 검사를 진행해서 포함이 되어 있는 String 값은 result라는 배열에 저장하게 됩니다. 하지만, List에 저장할 때 정렬된 상태가 아니기 때문에 결과를 출력하기 전에 Collections.sort()를 이용해서 출력하는 과정을 거칩니다.

하지만, 이렇게 푸는 방식도 시간 초과가 납니다… 그래서 다른 사람들의 풀이를 비교해보니 List를 사용하지 않고 Set을 사용하는 것을 볼 수 있었습니다. Set은 List와 유사하지만, 중복된 값을 허용하지 않고 순서가 없는 자료구조 입니다. 세 번째 방법에서는 똑같은 풀이에서 List를 Set으로 바꾼 차이만 존재합니다.

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

public class BOJ1764 {

    public static void main(String[] args) throws IOException {
        BufferedReader bf=  new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st= new StringTokenizer(bf.readLine()," ");
        List<String> noEarSett = new ArrayList<>();
        List<String> result = new ArrayList<>();


        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());

        for(int i=0;i<N;i++) {
            noEarSett.add(bf.readLine());
        }


        for(int i=0;i<M;i++){
            String person = bf.readLine();
            if(noEarSett.contains(person)){
                result.add(person);
            }
        }
        StringBuilder sb= new StringBuilder();
        Collections.sort(result);
        sb.append(result.size()+"\n");
        for (String str :
                result) {
            sb.append(str+"\n");

        }

        bw.write(sb.toString());
        bw.flush();
        bw.close();

    }
}

Set을 이용한 방법

List -> Set으로 바꾼 차이 밖에 없지만, 왜 시간초과가 나지 않고 통과하는지 잘 모르겠습니다… 아마 자료 구조에 대한 공부를 조금 더 해보고 성능 상으로 차이를 확인해봐야 할 것 같습니다.

구글링을 통해서 List와 Set의 성능 차이를 검색해보았습니다. 그랬더니 약간의 차이를 보이는 것을 확인할 수 있습니다.

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

public class BOJ1764 {

    public static void main(String[] args) throws IOException {
        BufferedReader bf=  new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st= new StringTokenizer(bf.readLine()," ");
        Set<String> noEarSett = new HashSet<>();
        List<String> result = new ArrayList<>();


        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());

        for(int i=0;i<N;i++) {
            noEarSett.add(bf.readLine());
        }


        for(int i=0;i<M;i++){
            String person = bf.readLine();
            if(noEarSett.contains(person)){
                result.add(person);
            }
        }
        StringBuilder sb= new StringBuilder();
        Collections.sort(result);
        sb.append(result.size()+"\n");
        for (String str :
                result) {
            sb.append(str+"\n");

        }

        bw.write(sb.toString());
        bw.flush();
        bw.close();

    }
}

배운점

정답률에 비해 문제가 그리 어려운 편은 아니었지만, 왜 이렇게 List와 Set에서 차이가 나는지 알 수 없었습니다. 그러다가 구글에서 List의 contains가 시간복잡도가 조금 걸린다는 것을 알게되었고, 이 부분에서 데이터가 많을 경우에는 Set이 오히려 낫다는 걸 알게되었습니다. 하지만, 데이터가 그리 많지 않은데 이런 시간초과가 나는 것은 추후에 더 알아봐야 할 것 같습니다.

그리고 N,M 두 개의 테스트 케이스를 입력 받는데, 하나는 입력 받아 Set에 저장하고 다른 테스트 케이스는 입력 받으면서 바로 Set과 비교하는 방식을 진행하였습니다. 이런 방식을 사용하는 것이 익숙치 않아서 더 풀어보면서 익숙해져야 할 것 같습니다.

[1746] 듣보잡

풀이방법

배운점

VictoryWoo