[백준] 10815 - 숫자 카드 (JAVA/ 자바)

10815번 문제

 

이번 문제도 틀린 코드로 시작한다ㅎㅎ... VSCode에서는 잘 돌아가는데 백준에 올리니 시간 초과 에러가 발생하였다.

❗️❗️ 틀린 코드

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

public class Main{
public static void main(String[] args)throws IOException{
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringBuilder sb = new StringBuilder();
    int N = Integer.parseInt(br.readLine());
    int[] list = new int[N];

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

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

    int[] result = new int[M];
    while(true){
        for(int i=0; i<M; i++){
            for(int j=0; j<N; j++){
                if(list2[i] == list[j]){
                    result[i] += 1;
                }
                else if(list2[i] != list[j]){
                    result[i] += 0;
                }
            }
        }
        break;
    }
    for(int i=0; i<M; i++){
        sb.append(result[i] + " ");
    }
    System.out.print(sb);
}
}

 

 

알고보니 이진 탐색을 이용해서 풀어야하는 문제라고 한다.

https://charles098.tistory.com/133

[ 알고리즘 ] 이분탐색(Binary Search), upper_bound, lower_bound (C++)

이 분의 블로그를 참고하여 이진 탐색에 대해 공부하였다.

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

public class Main{
public static void main(String[] args)throws IOException{
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringBuilder sb = new StringBuilder();
    int N = Integer.parseInt(br.readLine());
    int[] check = new int[N];

    StringTokenizer st = new StringTokenizer(br.readLine(), " ");
    for(int i=0; i<N; i++){
        check[i] = Integer.parseInt(st.nextToken());
    }
    
    Arrays.sort(check);
    int M = Integer.parseInt(br.readLine());
    st = new StringTokenizer(br.readLine(), " ");
    for(int i=0; i<M; i++){
        int num = Integer.parseInt(st.nextToken());
        sb.append(binarySearch(check, num) + " ");
    }
    System.out.print(sb);
}
public static int binarySearch(int[] check, int num){
    //배열 시작점
    int first = 0;
    //배열 끝점
    int end = check.length-1;
    
    while(first <= end){
        int mid = (first+end)/2;
 
        if(check[mid] < num){
            first = mid + 1;
        }else if(num < check[mid]){
            end = mid - 1;
        }else{//num값을 찾으면 1 반환
            return 1;
        }
    }
    return 0;

}
}

하는 와중에 1 0 0 1 0 0 0 0 결과가 나와서 당황했는데, Arrays.sort(check); 를 안해서 생긴 문제였다...

이분탐색은 정렬된 배열에 적용 가능한 탐색 기법이니 정렬을 꼭 해줘야한다...

 

단계 제목이 집합과 맵이라고 해서 처음엔 맵으로 푸는 거라고 생각해서 풀었는데 내가 생각한 방식으로는 결과가 제대로 도출되지 않아서 포기했었다. 문제를 푼 후에 찾아보니 HashMap을 이용해서 푸신 분이 계셨다!!!

 

https://velog.io/@leetaekyu2077/%EC%9E%90%EB%B0%94-HashMap-%EC%82%AC%EC%9A%A9%ED%95%B4%EB%B3%B4%EA%B8%B0-BOJ-10815-%EC%88%AB%EC%9E%90-%EC%B9%B4%EB%93%9C

[Java] HashMap 사용해보기 (BOJ-10815 숫자 카드)

HashMap을 이용해서 푸는 방법을 알고 싶으신 분은 이 분의 글을 참고해보시면 될 것 같다.