백준 10816 숫자 카드 2[JAVA]

Ga0·2023년 5월 14일

baekjoon

목록 보기

47/125

문제 해석

먼저, 상근이가 가진 카드의 개수(N)를 입력받고, N개 만큼 숫자 카드를 입력받고, 그 다음에는 비교할 대상의 카드의 개수(M)개를 입력받고, 비교할 카드를 M개 만큼 입력받는다.
입력을 다 받았다면, 상근이가 가진 카드목록에 비교할 대상의 카드들의 숫자들을 몇개씩 가지고 있는지 출력하면 된다.

틀린 코드

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));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int N = Integer.parseInt(br.readLine()); //상근이의 카드의 개수

        int[] sangeunArray = new int[N];//상근이의 카드들을 입력받는

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

        int M = Integer.parseInt(br.readLine()); //비교할 대상의 카드의 개수

        st = new StringTokenizer(br.readLine());
        for(int i = 0; i < M; i++){ //비교할 대상의 카드의 숫자 하나씩
            int count = 0; //같으면 count++할 용도
            int compare = Integer.parseInt(st.nextToken());
            for(int j = 0; j < N; j++){ //상근이의 카드 개수만큼 반복을 계속 돌림
                if(compare == sangeunArray[j]){ // 만약 같다면
                    count++; //증가
                }
            }
            bw.write(count +" ");
        }
        br.close();

        bw.flush();
        bw.close();
    }

}

틀린 결과

문제를 풀면서도... 뭔가 시간초과가 날 것 같았다.
정말 시간초과😞

정리

위의 경우는 찾으려는 값의 첫번째 인덱스(중복시)를 찾는 경우이다.

이런식으로 마지막 인덱스를 찾는다.
즉, 찾으려는 값의 마지막 인덱스+1 - 첫번째 인덱스을 하면 개수를 구할 수 있다.
직관적으로 보면, 로직으로 이런 방식이지만 middle가 뒤로 한칸씩 밀린다.
처음 right는 배열 요소 마지막을 가르키는 것이 아니라 마지막 요소의 그 다음 인덱스를 가르키기 때문이다. (없는 요소)

코드

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));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int N = Integer.parseInt(br.readLine());

        int[] sangeunArray = new int[N];

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

        int M = Integer.parseInt(br.readLine());
        
        Arrays.sort(sangeunArray); //이진/이분 탐색을 위한 정렬

        st = new StringTokenizer(br.readLine());
        for(int i = 0; i < M; i++){
            int value = Integer.parseInt(st.nextToken()); //찾으려는 값
            bw.write(findEndIndex(sangeunArray,value) - findStartIndex(sangeunArray, value) + " ");
        }
        br.close();
        bw.flush();
        bw.close();
    }
    //찾으려는 값 첫번째 인덱스 구하는 함수
    private static int findStartIndex(int[] array, int value) {
        int left = 0;
        // 마지막 인덱스가 아니라 array.length을 한 이유는 개수를 구하기 위해서는 +1을 해줘야하기 때문
        // -10 2 3 3 6 7 10 10 10 => 일때 10의 개수는 3인 것을 볼 수 있다.
        // 10의 인덱스는 7 8 9이다. (배열은 인덱스는 0부터 시작하기 때문에)
        // 만약 마지막 인덱스 9에서 첫번째 인덱스 7를 빼면 2가 된다. => 하지만, 10의 개수는 3개이다.
        // 그렇기 때문에 +1을 해줘야하는데 array.length은 배열의 마지막 인덱스가 아닌 배열의 요소의 수이기 때문에 
        // 개수를 구할 수 있게 된다.
        int right = array.length;

        while (left < right) {
            int middle = (left + right) / 2;
            if (value <= array[middle]) {
                right = middle;
            }
            else {
                left = middle + 1;
            }
        }
        return left;
    }

    //찾으려는 값 마지막 인덱스를 구하는 함수
    private static int findEndIndex(int[] array, int value) {
        int left = 0;
        int right = array.length; 

        while (left < right) {
            int middle = (left + right) / 2;
            if (value < array[middle]) {
                right = middle;
            }
            else {
                left = middle + 1;
            }
        }
        return left;
    }

}