백준 1764 듣보잡 (Java)

1. 문제 링크

1764번: 듣보잡

 

2. 문제 및 입출력예제

 

3. 문제 풀이

처음에는 반복문을 N과 M만큼 돌면서 ArrayList에 추가하고 다른 for문으로 검사를 했다.

그러나 시간초과라는 결과가 발생했고 검사하는 과정을 M번 도는 반복문에 추가했다.

 

그래도 시간초과가 나온다.

그 이유는 List에서 탐색이 오래 걸리기 때문이었고, 중복이 없다는 전제가 있어 Set으로 변경했다.

그 결과 성공적인 결과가 나왔다.

 

4-1 코드 제출 후 맞았습니다!!가 나왔지만

사전순으로 출력해야 한다는게 이루어진건지 모르겠어서

정렬하는 코드를 넣은 4-2 코드를 제출했는데 똑같이 맞았습니다!!가 나왔다.

 

혹시 4-1코드도 정렬이 된 상태인지.. 혹은 왜 정답인지 아는 분은 댓글로 알려주세요.

 

4-1. 코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;

public class Main {

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		String[] NM = br.readLine().split(" ");
		int N = Integer.parseInt(NM[0]);
		int M = Integer.parseInt(NM[1]);
		String temp;

		Set<String> hear = new HashSet<>();
		for (int n = 0; n < N; n++) {
			hear.add(br.readLine());
		}
		ArrayList<String> no = new ArrayList<>();
		for (int n = 0; n < M; n++) {
			temp = br.readLine();
			if(hear.contains(temp))
				no.add(temp);
		}
		Collections.sort(no);
		temp="";
		sb.append(no.size()+"\n");
		for(String str: no) {
			sb.append(str+"\n");
		}
		System.out.println(sb);
	}

}

 

4-2. 코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashSet;
import java.util.List;
import java.util.Scanner;
import java.util.Set;

public class Main {

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		String[] NM = br.readLine().split(" ");
		int N = Integer.parseInt(NM[0]);
		int M = Integer.parseInt(NM[1]);
		String temp;

		Set<String> hear = new HashSet<>();
		for (int n = 0; n < N; n++) {
			hear.add(br.readLine());
		}
		Set<String> see = new HashSet<>();
		for (int n = 0; n < N; n++) {
			see.add(br.readLine());
		}

		hear.retainAll(see);
		
		List<String> no = new ArrayList<String>(hear); //HashSet -> List
		Collections.sort(no);
		
		temp="";
		sb.append(no.size()+"\n");
		for(String str: no) {
			sb.append(str+"\n");
		}
		System.out.println(sb);
	}

}