[Summer/Winter Coding(~2018)] 숫자 게임

[Summer/Winter Coding(~2018)] 숫자 게임

🙋‍♂️ 들어가며

이번 문제는 그리디를 생각해보았는데 그게 아니더라

그리디가 아닌 이유로 반례는 다음과 같다

A = {8, 8, 2, 2};
B = {1, 1, 8, 8};
res = 2;

이건 two-pointer 로 풀 수 있겠다

✅ 코드

import java.util.Arrays;

class Solution {
    public int solution(int[] A, int[] B) {
        int answer = 0;
        
        Arrays.sort(A);
        Arrays.sort(B);
        int N = B.length;
        
        // A 시작점
        // B 시작점
        int s1 = 0;
        int s2 = 0;
        while (true) {
            if (s1 >= N) break;
            if (s2 >= N) break;
            
            if (A[s1] >= B[s2]) s2++;
            else if (A[s1] < B[s2]) {
                s1++;
                s2++;
                answer++;
            }
        }
        return answer;
    }
}