12주차 : 정렬 문제1

✔ BOJ_1764

일단 Arraysort로 NotHear,NotSee 배열을 정렬하고, 더 작은 배열을 tmp에 두고, 더 긴 배열을 pair에 둔 뒤 이진탐색을 진행하는 코드로 작성했습니다.

package BaekJoon.Sort;

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

public class BOJ_1764 {

    static String notHear[];
    static String notSee[];
    static String tmp[];
    static String pair[];

    // 듣도 보도 못한 사라므이 명단 구하기
    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());
        // 돋도 못한 사람 배열
        notHear =new String[n];
        for(int i=0;i<n;i++){
            notHear[i] = br.readLine();
        }
        // 보도 못한 사람 배열
        notSee = new String[m];
        for(int i=0;i<m;i++){
            notSee[i] = br.readLine();
        }
        // 이름은 띄어쓰기 없이 소문자로만 이루어진다.

        Arrays.sort(notHear);
        Arrays.sort(notSee);

        tmp = (notHear.length > notSee.length)?notSee:notHear;
        pair = (notHear.length > notSee.length)?notHear:notSee;
        ArrayList<String> ans = new ArrayList<>();
        for(int i=0;i<tmp.length;i++){
            if(binarySearch(tmp[i],0,pair.length-1)){
                ans.add(tmp[i]);
            }
        }
        System.out.println(ans.size());
        for (String an : ans) {
            System.out.println(an);
        }

    }

    private static boolean binarySearch(String target, int low, int high) {
//        System.out.println("target = " + target);
        int mid = (low+high)/2;
//        System.out.println(pair[mid]);
//        System.out.println("low = " + low);
//        System.out.println("mid = " + mid);
//        System.out.println("high = " + high);
//        System.out.println();
        if(low > high) {return false;}
        else{
            if(target.equals(pair[mid])) {
//                System.out.println("찾았다");
                return true;}
            // 좌측값이 큰 경우
            else if(target.compareTo(pair[mid])>=1){
//                System.out.println("target이 더 크다");
                low=mid+1;
                return binarySearch(target,low, high);}
            // 우측값이 큰 경우
            else if(target.compareTo(pair[mid]) <= -1) {
//                System.out.println("target이 더 작다");
                high = mid-1;
                return binarySearch(target,low, high);}
        }
        return false;
        }

    }

좀 효율적이지 못한 것 같아서 찾아보니 .. HashSet을 선언하고(중복값이 없으므로) 다음 것을 받을 때 내부에 똑같은 값이 있으면 result에 포함하는 아주 쉬운.. 코드가 있었습니다.출처

package BaekJoon.Sort;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashSet;
import java.util.StringTokenizer;

public class BOJ_1764_adv {
    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());

        HashSet<String> set = new HashSet<>();
        for(int i =0;i<n;i++){
            set.add(br.readLine());
        }
        ArrayList<String> result = new ArrayList<>();
        for(int i=0;i<m;i++){
            String tmp = br.readLine();
            if(set.contains(tmp)){
                result.add(tmp);
            }
        }
        Collections.sort(result);

        //쉽네
        System.out.println(result.size());
        for (String s : result) {
            System.out.println(s);
        }

    }
}

해당 코드가 정렬에 속하는 이유가 무엇인지는 잘 모르겠지만.. :(