[백준] 4158번 : CD – JAVA [자바]

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

4158번: CD

 

---

• 문제

 

 

---

• 문제 풀이

백준 4158번 CD는 실버 5 난이도의 자료 구조 및 두 포인터 문제이다. 이 문제에서는 상근이가 가지고 있는 CD의 수 N, 선영이가 가지고 있는 CD의 수 M이 주어진다. 이때 두 사람이 동시에 가지고 있는 CD의 개수를 출력하면 된다.

 

우선 int형 배열 두 개에 상근이가 가지고 있는 CD 번호와 선영이가 가지고 있는 CD 번호들을 입력받는다. 문제에서 주어지는 CD 번호들은 이미 오름차순으로 정렬이 되어 있기 때문에 따로 정렬을 해줄 필요는 없다. 

 

추가로, 문제에서 주어진 바로는 상근이와 선영이가 같은 CD를 여러 장 가지고 있는 경우는 없다. 따라서, 똑같은 CD 번호는 한 번만 확인해 주면 된다.

 

두 배열에 입력을 받은 후에는 두 배열을 하나씩 비교하면서 공통된 번호를 찾고, 공통된 번호들의 개수를 구하면 된다. 

 

첫 번째 배열을 arr1, 두 번째 배열을 arr2라고 하겠다. 그리고 arr1의 인덱스를 i, arr2의 인덱스를 j라고 하겠다. 이때 경우는 3가지로 나눌 수 있다.

 

1. arr1 [i] = arr2 [j] 이면 count를 증가시켜 주고 i와 j 둘 다 1씩 증가시켜 준다. 

 

2. arr1 [i] > arr2 [j] 이면 arr2의 CD 번호가 더 작으므로 j를 증가시켜 준다.

 

3. arr1 [i] < arr2 [j] 이면 arr1의 CD 번호가 더 작으므로 i를 증가시켜 준다.

 

이렇게 두 배열을 순회하면서 한 배열이 끝나면 loop을 종료해 준다. 그리고 count를 출력해 주면 된다.

 

자세한 코드는 아래에 있는 코드를 참고하면 되겠다.

 

---

• 코드

 

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));
        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) { // 입력의 마지막 줄에는 0 0이 주어지면 반복문 종료
                break;
            }
            int[] arr1 = new int[n]; // 상근이가 가지고 있는 CD 번호 배열
            int[] arr2 = new int[m]; // 선영이가 가지고 있는 CD 번호 배열
            for (int i = 0; i < n; i++) {
                arr1[i] = Integer.parseInt(br.readLine()); // 상근이의 CD 번호 입력 받기
            }
            for (int i = 0; i < m; i++) {
                arr2[i] = Integer.parseInt(br.readLine()); // 선영이의 CD 번호 입력 받기
            }
            int i = 0 ;
            int j = 0;
            int count = 0; // 두 사람이 동시에 가지고 있는 CD의 개수를 저장할 변수
            while (i != n && j != m) { // 두 리스트를 동시에 하나씩 비교하여 공통된 번호를 찾기 위한 반복문
                if (arr1[i] == arr2[j]) { // 공통된 번호를 찾으면
                    count++; // 개수 증가
                    i++; // 두 리스트의 다음 원소를 비교하기 위해 인덱스 증가
                    j++;
                }
                else if (arr1[i] > arr2[j]) { // 상근이의 번호가 더 크면 선영이의 번호를 늘림
                    j++;
                } else { // 선영이의 번호가 더 크면 상근이의 번호를 늘림
                    i++;
                }
            }
            System.out.println(count); // 두 사람이 동시에 가지고 있는 CD의 개수 출력
        }
    }
}