BOJ_4158 : CD

👉 문제링크

4158번: CD

---

---

🔸 문제 분석 🔸

• n과 m이 입력되면 n개의 수와 m개의 수가 입력되고 겹치는 숫자의 개수를 출력한다.
  • 오름차순 정렬된 수가 입력되므로 투 포인터 알고리즘을 사용해 풀이한다.
• 0 0이 입력 될 때까지 반복한다.

🔸 코드 🔸

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        while (true) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int n = Integer.parseInt(st.nextToken());
            int m = Integer.parseInt(st.nextToken());
            if (n == 0 && m == 0)
                break;

            int[] arr_n = new int[n];
            int[] arr_m = new int[m];
            for (int i = 0; i < n; i++) {
                arr_n[i] = Integer.parseInt(br.readLine());
            }
            for (int i = 0; i < m; i++) {
                arr_m[i] = Integer.parseInt(br.readLine());
            }

            int count_n = 0, count_m = 0, answer = 0;
            while (count_n < n && count_m < m) {
                if (arr_n[count_n] > arr_m[count_m])
                    count_m++;
                else if (arr_n[count_n] < arr_m[count_m])
                    count_n++;
                else {
                    answer++;
                    count_m++;
                    count_n++;
                }
            }
            System.out.println(answer);
        }
    }
}

🔸 코드 해석 🔸

• arr_n, arr_m 두 배열을 순회하며 다음과 같은 규칙으로 인덱스를 증가시킨다.
  • 두 배열열의 값이 같으면, 정답을 +1하고 두 인덱스값도 1 증가시킨다.
  • 두 배열의 값이 다르면, 값이 작은 쪽의 인덱스를 1 증가시킨다.

---

🔸 end 🔸

• 처음에는 하나의 배열로 체크하거나 비트마스킹으로 체크해야 했는데 값이 너무 커서 어려웠다.
• 투 포인터가 너무 최적의 방법인 것 같아 선택했는데, 해시 맵이나 이분 탐색으로도 풀이가 되는 것 같다.