BOJ : 4158

1. 문제

 

2. 문제 설명 및 알고리즘 설계

 

두 사람이 동시에 갖고 있는 CD의 개수를 구해야 한다.

나는 우선 배열로 양쪽의 CD를 받은 후 정렬을 하고 한개씩 확인하다가 둘 중 같으면 cnt++, 둘 중에 작은 수의 index를 증가시켜 주면서 풀었다.

 

00받으면 끝나는걸 잊고있었다.

 

3. 코드

package week9;

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

public class Q4158_boj {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        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){
                System.out.println(sb);
                break;
            }

            int sang[] = new int[N];
            int sun[] = new int[M];

            for (int i = 0; i < N; i++) {
                sang[i] = Integer.parseInt(br.readLine());
            }

            for (int i = 0; i < M; i++) {
                sun[i] = Integer.parseInt(br.readLine());
            }
            Arrays.sort(sang);
            Arrays.sort(sun);

            int cnt=0 ,sang_index = 0, sun_index = 0;

            while (sang_index != N && sun_index != M) {
                if (sang[sang_index] == sun[sun_index]) {
                    cnt++;
                    sang_index++;
                    sun_index++;
                } else if (sang[sang_index] > sun[sun_index]) {
                    sun_index++;
                } else {
                    sang_index++;
                }
            }

            sb.append(cnt+"\n");
            cnt=0;
        }
    }
}

 

4. 시간 복잡도

O(N)

 

5. 결과

문제 종료조건이 걸려있는것을 못봤네요ㅜㅠ 슬프농