[99클럽 코테 스터디 TIL 26일차] 백준 4158번 CD 해설 및 풀이 (Java)

 

백준 4158번 CD

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

---

 

 

---

문제 유형

자료 구조 이분 탐색 해시를 사용한 집합과 맵 두 포인터

 

풀이 방법 도출

 

두 사람이 각각 오름차순으로 정렬된 CD 번호를 가지고 있고, 공통으로 소유한 CD 개수를 구하는 문제이다.

 

1. 두 배열 모두 오름차순이므로, 투 포인터를 사용해서 동시에 순회합니다.
2. sungkyun[i] == sunyoung[j]이면 공통 CD이기 때문에 cnt를 증가시킵니다.
3. 한쪽 값이 작으면 포인터를 증가시킵니다.

 

 

시간 복잡도

• O(N + M)

---

핵심 코드 삽입 및 설명

 

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        // 빠른 입력을 위해 BufferedReader 사용
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        while (true) {
            // 한 줄에서 N, M 값을 읽어옴
            st = new StringTokenizer(br.readLine());
            int n = Integer.parseInt(st.nextToken()); // 상근이의 CD 개수
            int m = Integer.parseInt(st.nextToken()); // 선영이의 CD 개수

            // 종료 조건
            if (n == 0 && m == 0) break;

            int[] a = new int[n]; // 상근이의 CD 목록
            int[] b = new int[m]; // 선영이의 CD 목록

            // 상근이의 CD 번호 입력 받기
            for (int i = 0; i < n; i++) {
                a[i] = Integer.parseInt(br.readLine());
            }

            // 선영이의 CD 번호 입력 받기
            for (int i = 0; i < m; i++) {
                b[i] = Integer.parseInt(br.readLine());
            }

            // 투 포인터 알고리즘을 이용하여 공통 CD 개수 계산
            int i = 0, j = 0, cnt = 0;

            while (i < n && j < m) {
                if (a[i] == b[j]) {
                    // 두 CD가 같으면 공통 CD이기 때문에 cnt 증가
                    cnt++;
                    i++;
                    j++;
                } else if (a[i] < b[j]) {
                    // a[i]가 작으면 a의 포인터 증가
                    i++;
                } else {
                    // b[j]가 작으면 b의 포인터 증가
                    j++;
                }
            }

            // 결과 출력
            System.out.println(cnt);
        }
    }
}