[Algorithm] 프로그래머스 - 숫자 게임

문제

[프로그래머스] 숫자 게임
(Summer/Winter Coding(~2018))

사용 알고리즘

- 투 포인터 (two pointer) / Greedy

- 시간복잡도 O(N logN)

해결방법

• A, B를 모두 오름차순 정렬
• A의 각 원소에 대해, B에서 A보다 큰 숫자를 찾아 이긴 횟수를 증가시킨다

소스코드

사용언어 : java

import java.util.*;

class Solution {
    public int solution(int[] A, int[] B) {
        int answer = 0;
        
        // A, B 오름차순 정렬
        Arrays.sort(A);
        Arrays.sort(B);
        
        
        int j = 0; // B index
        for (int a : A) {
            while (j < B.length && B[j] <= a) {
                j++;
            }
            
            if (j >= B.length) break;
            
            answer++;
            j++;
        }
        
        return answer;
    }
}

 

 

한줄평

처음엔 B의 인덱스를 조절할 생각을 못하고, B자체를 큐로 변환해, 각 a에 대해 큰 값이 나올대 까지 poll하는 방식으로 구현했는데, (물론 이렇게 해도 정답이었다)

지피티 선생님이 이 문제는 투포인터를 활용하는 문제라고 정정해주셔서 다시 풀었다. (ㅋㅋ)