프로그래머스 - 숫자게임

숫자게임 : https://school.programmers.co.kr/learn/courses/30/lessons/12987

---

Problem

---

Solve

A와 B의 값을 비교해서 B가 큰 수의 최대 개수를 찾는 문제입니다.

A와 B를 비교하기 위해 A와 B를 오름차순 정렬해줍니다. (크기를 비교하는데 순서의 조건이 없기 때문)
그리고 A에서 가장 작은 값 부터 순차적으로 돌면서 A의 해당값보다 B의 특정값이 큰 경우 개수를 카운트해주는 방식을 사용해주었습니다.

A : [1,3,5,7], B : [2,2,6,8]을 비교해보겠습니다.

1. 먼저 A의 첫번째값 1과 B의 첫번째값 2를 비교합니다.
2. B의 값이 크기 때문에 A와 B를 둘다 다음 값과 비교합니다.
3. A의 두번째값 3과 B의 두번째값 2는 A가 더 크거나 같기 때문에 B의 다음값과 비교합니다.
4. A의 두번째값 3과 B의 세번째값 6은 B가 더 크기 때문에 카운트해주고, A와 B의 다음값을 비교하여줍니다.
5. 이를 B가 모든 값을 비교할때까지 반복해줍니다.

이렇게 비교해준다면 각 배열을 하나씩 비교할수 있기 때문에 O(N)의 시간복잡도로 해결할 수 있습니다.

---

Code

import java.util.Arrays;
class Solution {
    public int solution(int[] A, int[] B) {
        int answer = 0;
        int N = A.length;
        Arrays.sort(A);
        Arrays.sort(B);
        
        int indexA = 0;
        int indexB = 0;
        
        while(indexB < N){
            while(indexB < N && A[indexA]>=B[indexB]) indexB++;
            
            if(indexB<N && A[indexA]<B[indexB]) answer++;
            
            indexA++;
            indexB++;
        }
        
        return answer;
    }
}

---

Result

---

Reference