[백준 / Java] 10815번 : 숫자 카드

https://www.acmicpc.net/problem/10815

10815번: 숫자 카드

 

---

◎ 문제

 

 

---

◎ 코드 및 풀이

 

첫번째 이분탐색 풀이

 

import java.io.*;
import java.util.*;
 
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
 
        StringTokenizer st;
 
        // n입력
        st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
 
        // aList
        st = new StringTokenizer(br.readLine());
        List<Integer> nList = new ArrayList<>();
 
        for (int i = 0; i < n; i++) {
            nList.add(Integer.parseInt(st.nextToken()));
        }
        Collections.sort(nList);
 
 
        // m입력
        st = new StringTokenizer(br.readLine());
        int m = Integer.parseInt(st.nextToken());
 
        // bList
        st = new StringTokenizer(br.readLine());
        List<Integer> mList = new ArrayList<>();
 
        for (int i = 0; i < m; i++) {
            mList.add(Integer.parseInt(st.nextToken()));
        }
 
        for (int i = 0; i < m; i++) {
            int left = 0;
            int right = n-1;
            int mid;
 
            while(left<=right) {
                mid = (right+left)/2;
 
                if (nList.get(mid) > mList.get(i)) {
                    right = mid-1;
 
                } else if (nList.get(mid) < mList.get(i)) {
                    left = mid +1;
 
                } else {
                    sb.append(1+" ");
                    break;
                }
 
                if(right < left){
                    sb.append(0+" ");
                }
 
            }
        }
        System.out.println(sb);
    }
}

 

핵심 풀이 내용은 탐색할 리스트의 가장 왼쪽과 오른쪽의 인덱스를 지정해두고 중간값 인덱스를 탐색마다 변경 시켜주는것이다. 이때 right이나 left를 그냥 mid로 해주면  두가지 문제점이 발생한다. 첫째는 탐색시 마지막 인덱스가 반복되어 무한 루프를 타게된다는 점이고 두번째는 이미 탐색한 부분을 한번 더 탐색하게 되는 비효율성이다.

이 모든 문제점을 mid에 +1 과 -1 을 해주어 해결했다.

 

---

 

두번째 Map을 이용한 풀이

 

import java.io.*;
import java.util.*;
 
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
 
        StringTokenizer st;
 
        // n 입력
        st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
 
        Map<String,Integer> nMap = new HashMap<>();
 
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            nMap.put(st.nextToken(),0);
        }
 
 
        // m 입력
        st = new StringTokenizer(br.readLine());
        int m = Integer.parseInt(st.nextToken());
 
 
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < m; i++) {
            if(nMap.containsKey(st.nextToken())) {
                sb.append(1+" ");
            } else {
                sb.append(0+" ");
            }
        }
 
        System.out.println(sb);
 
    }
}

 

다른 문제를 풀다가 여기에도 적용 가능하지 않을까 해서 제출해봤다. Map을 이용하니 풀이도 간단해지고 시간도 훨씬 줄었다. 

---

◎ 기록

 

첫번째 풀이는 이분 탐색(Binary Search) 이었다. 처음엔 contains 함수로 쉽게 접근했다가 시간초과를 맛보고 굉장히 오래 고민했다... for문 안에 contatins 함수는 시간복잡도를 O(N^2)으로 만든다. 하지만 이분 탐색을 이용하면 시간복잡도가 O(log2N)로 줄어든다. 시간을 줄여주도록 효율성있게 코드를 짜는것은 매우 중요해보인다.

 

두번째 풀이는 Map을 이용한 풀이였다. 전까진 List, Array를 고집해왔었는데 Map을 처음 공부해보고 사용해보니 활용도가 높은거 같다! 알고리즘 풀이에 굉장히 많이 쓰일거 같다.