JAVA - 숫자카드 (백준, 10815)

문제

문제의 요구사항은 결국 길이 (갯수)N 의 카드와 길이 (갯수)M 의 카드를 비교해 일치하는 index 는 1 아니면 0을 출력한다.

 

맨처음엔 이분탐색 문제인지도 모르고 그냥 단순히 완전탐색으로 찾으려고만 했다..

 

import java.util.*;

public class main {
    
    public void card() {
        List<Integer> aList = new ArrayList<>();
        List<Integer> bList = new ArrayList<>();
        String result = "";
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        int n = Integer.parseInt(br.readLine());
        for(int i=0; i<n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine(), " ");
            int s = Integer.parseInt(st.nextToken());
            aList.add(s);
        }
        
        int m = Integer.parseInt(br.readLine());
        for(int i=0; i<m; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine(), " ");
            int s = Integer.parseInt(st.nextToken());
            bList.add(s);
        }
        
        for(int i =0; i<bList.size(); i++){
            for(int j=0; j<aList.size(); j++){
                if(bList.get(i) == aList.get(j)) {
                result += (" "+(String)bList.get(i));                    
                }
            }
        }
        System.out.println(result);
        
    }
    
    
}

졸려서 그랬나...?  부끄럽지만 말도안되는 코드로 정답역시 엉터리로 제출하려고 했다.

그러다가 문제를 차근차근 읽어보니, 이분탐색을 해야하고, 정답도 1 과 0 으로 출력해야하는걸 다시 알고 후다닥 고쳤다..

 

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

        int N = Integer.parseInt(br.readLine());
        int[] arr = new int[N];

        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        
        for(int i=0; i<N; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }
        Arrays.sort(arr);

        int M = Integer.parseInt(br.readLine());
        st = new StringTokenizer(br.readLine(), " ");
        StringBuilder sb = new StringBuilder();
        for(int i=0; i<M; i++) {
            int s = Integer.parseInt(st.nextToken());
            sb.append(upper(arr,s) - lower(arr,s)).append(' ');
        }
     
        System.out.println(sb);
        
    }
    
    private static int lower(int[] arr, int key) {
        int low = 0;
        int hi = arr.length;
        while(low < hi) {
            int mid = (low+hi)/2;
            if(key<=arr[mid]) {
                hi = mid;
            } else {
                low = mid + 1;
            }
        }
        return low;
    }
    
    private static int upper(int[] arr, int key) {
        int low = 0;
        int hi = arr.length;
        while(low<hi) {
            int mid = (low+hi)/2;
            if(key<arr[mid]){
                hi=mid;
            } else {
                low=mid+1;
            }
        }
        return low;
    }
    
}

그래도 생각보다 안되네.. 싶어서 결국 구글링 찬스... 정답코드들을 보고 정리해 보았다.

 

arr[] = N만큼의 길이를 가진 배열로 선언하고, StringTokenizer 로 이를 배열에 담는다.

그리고 Arrays.sord(arr) 로 배열을 정렬한다.

M 역시 똑같이 StringTokenizer 로 담는데, StringBuilder 에 담을 때, 이분탐색함수 lower, upper 로 배열을 탐색해 담는다.

 

어떻게 보면 쉽다고 생각하고 풀었지만, 아직 어렵다.. 자료구조와 알고리즘에 내가 얼마나 무지한상태인지 부끄럽지만..

남겨본다.