자바(백준) 1764 듣보잡

오답 노트 & 새로 알게 된 점

듣보잡 문제는 이분 탐색 문제이지만, 다루는 자료형이 String형이다. 이 문제를 풀면서 문자열에 관한 메소드를 많이 알아가게 됐다.

1. Arrays.sort는 배열을 오름차순으로 정렬해주는 메소드

2. Collections.sort는 List형을 오름차순으로 정렬해주는 메소드이다. 

 

compareTo 메소드를 볼 수 있다. 처음에는 구글링을 잘못하여 compareTo 메소드를 사용하면서 반환하는 숫자가 0 , -1, 1밖에 없다고 생각한 것이다. 그러나 compareTo 메소드는 

A.compareTo(B) 일 때, A가 B보다 앞선다면 음수가 나온다. 물론 정확한 어떤 숫자가 반환되는지는 알 수 있다. 아스키코드를 이용하여, 포함되어 있는 문자에서 빼주면 되는데 이 부분은 다음에 알아갈 것이다. 

 

"a".compareTo("b")를 하게 되면 음수가 나온다. 즉 사전 순으로 a가 앞선다는 뜻이다.

a b c d e에서 우리가 d를 찾고 싶다고 생각해보자.

그러면 처음에 mid는 c일텐데, 여기서 c와 d를 compareTo하게 되면 음수가 나온다. 그래서 d를 찾고 싶으면

s를 늘려줘야한다.

 

---

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.StringTokenizer;
 
public class Main {
    static int L, S;
    static String La[], Sa[];
    static ArrayList<String> al = new ArrayList<>();
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
 
        L = Integer.parseInt(st.nextToken());
        S = Integer.parseInt(st.nextToken());
 
        La = new String[L];
        Sa = new String[S];
 
        for (int i = 0; i < L; i++) {
            La[i] = br.readLine();
        }
 
        for (int i = 0; i < S; i++) {
            Sa[i] = br.readLine();
        }
 
        Arrays.sort(Sa);
        //La를 타겟으로 하고 이게 Sa에 있는지 확인하자
        for (int i = 0; i < L; i++) {
            binarySearch(La[i]);
        }
 
        Collections.sort(al);
 
        StringBuilder sb = new StringBuilder();
        sb.append(al.size()).append("\n");
        for (String s : al) {
            sb.append(s).append("\n");
        }
 
        System.out.println(sb);
    }
    static void binarySearch(String target){
        int s = 0, e = S-1, mid = 0;
 
        while (s <= e) {
            mid = (s + e) / 2;
 
            if(Sa[mid].compareTo(target) < 0) s = mid + 1;
            else if(Sa[mid].compareTo(target) == 0){
                al.add(target);
                return;
            }
            else e = mid - 1;
        }
    }
}