코딩테스트 연습 스터디 진행중 입니다. ✍✍✍
Notion : https://www.notion.so/1c911ca6572e4513bd8ed091aa508d67

문제

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

[나의 풀이]

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.StringTokenizer;

public class Correct {
    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;

        st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
		
        // 중복되는 값을 찾게되는 시간을 줄이기 위해
        // Map 자료구조의 key값으로 접근하는 방식 선택!
        Map<String,Integer> not_be_heard_seen = new HashMap<>();

        for (int i = 0; i < N; i++) {
            not_be_heard_seen.put(br.readLine(),1);
        }

        for (int i = 0; i < M; i++) {
            String input = br.readLine();
            if(not_be_heard_seen.keySet().contains(input))
            not_be_heard_seen.put(input,2);
        }

        List<String> ANS = new ArrayList<>();
		
        // Map 자료구조는 Entry로 분해해서 for문을 돌릴 수도 있다!
        for(Map.Entry<String, Integer> entry : not_be_heard_seen.entrySet()){
            if(entry.getValue()==2){
                ANS.add(entry.getKey());
            }
        }
        bw.write(ANS.size() + "\n");

        Collections.sort(ANS);

        for (int i = 0; i < ANS.size(); i++) {
            bw.write(ANS.get(i) + "\n");
        }

        bw.flush();

    }

}

이번 문제는 굉장히 쉬운 문제라고 생각했지만 여러번의 시간 초과 때문에 생각보다 오래 걸렸습니다...🐷🐷🐷

문제에서 요구하는 핵심 아이디어는 자료형 안의 원하는 요소 값을 찾는 시간을 줄이기 위해 Map 자료형을 활용하는 것이였고 순차적인 인덱스 접근이 아닌 Key or Value값으로 빠르게 탐색하는 방식으로 풀어야했습니다.🧐🧐🧐

아래 코드들은 이 요점을 파악하지 못하여 시간 초과가 난 두가지 풀이입니다.

// 1. 원하는 요소를 찾고자 Contains를 활용한 것이 원인이였습니다.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Collections;
import java.util.LinkedList;
import java.util.StringTokenizer;

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

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

        LinkedList<String> be_heard = new LinkedList<>();
        for(int i=0;i<N;i++){
            be_heard.add(br.readLine());
        }

        Collections.sort(be_heard);

        int cnt = 0;
        for(int i=0;i<M;i++){
            String be_seen = br.readLine();
            if(be_heard.contains(be_seen)){
                bw.write(be_seen);
                bw.newLine();
                cnt++;
            }
        }

        System.out.println(cnt);

        bw.flush();
        
    }
    
}

// 2. 리스트1.removeAll(리스트2)을 활용하여 꽤 참신한 풀이라고 
// 생각했지만 이 또한 시간초과가 났습니다.

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

public class Try_remove_all {
    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;

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

        List<String> not_be_heard = new ArrayList<>();
        List<String> not_be_heard_origin = new ArrayList<>();
        for (int i = 0; i < N; i++) {
            String input = br.readLine();

            not_be_heard.add(input);
            not_be_heard_origin.add(input);
        }

        List<String> not_be_seen = new ArrayList<>();
        for (int i = 0; i < M; i++) {
            not_be_seen.add(br.readLine());
        }

        not_be_heard.removeAll(not_be_seen);
        not_be_heard_origin.removeAll(not_be_heard);

        Collections.sort(not_be_heard_origin);

        int n = not_be_heard_origin.size();

        bw.write(n+"");
        bw.newLine();

        for(int i=0;i<n;i++){
            bw.write(not_be_heard_origin.get(i));
            bw.newLine();
        }

        bw.flush();

    }

}

이 정도 쉬운 문제도 파훼하는데에 오래 걸리는 것을 보면 한참 중에 한참 멀었다는 생각이 듭니다. 그래도 꿈이 있으니 화이팅 해보겠습니다!

감사합니다!💐💐💐