[백준] 1764 듣보잡

문제보기

단순하게 선형비교해주면 시간초과 뜬다 (나는 항상 이래.. ㅎ)

그래서 애초에 그냥 리스트 두개 만들어서 사전순으로 정렬 해준 뒤에

비교하면서 인덱스를 이동시켜주면서 비교하면 O(N)으로 해결 가능하다

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

public class Main{

  public static void main(String []args) throws IOException{
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer st = new StringTokenizer(br.readLine());
    int n = Integer.parseInt(st.nextToken());
    int m = Integer.parseInt(st.nextToken());

		// 듣지 못한 리스트 담을 변수
    List<String> list1 = new ArrayList<>();
    // 보지 못한 리스트 담을 변수
    List<String> list2 = new ArrayList<>();
		
    // 잘 담아줍니다
    for(int i = 0 ; i < n ; i++ ){
      list1.add(br.readLine());
    }
    for(int i = 0 ; i < m ; i++ ){
      list2.add(br.readLine());
    }
    // 사전순으로 배열하기
    Collections.sort(list1);
    Collections.sort(list2);
    // 갯수도 출력하라고 해서 필요해진 변수
    int cnt = 0;
    // 스트링은 여기에 담을 예정
    StringBuilder sb = new StringBuilder();
		
    // 둘다 스타트는 0번부터~
    int idx1 = 0;
    int idx2 = 0;
    
    while(idx1 < n && idx2 < m){
      String s1 = list1.get(idx1);
      String s2 = list2.get(idx2);
      
      // compareTo 메서드는 s1 이 s2보다 사전순으로 뒤일 경우 양수를 반환한다. 앞이면 음수, 같으면 0 반환
      int res = s1.compareTo(s2);
       
      if(res==0){
        cnt++;
        sb.append(list1.get(idx1) + "\n");
        idx1++;
        idx2++;
      }else if(res>0){
        idx2++;
      }else{
        idx1++;
      }
    }

    System.out.println(cnt + "\n" + sb);

  }
}