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

문제 설명

https://school.programmers.co.kr/learn/courses/30/lessons/12987

문제 풀이

• 그리디스러운 아이디어가 필요한 문제이다.
• 아이디어는 다음과 같다. (각 A원소에 대해 가장 가까운 큰 수 찾기)

  우선 A, B를 각각 정순으로 정렬한다.
  A배열을 순회하며 생각해보자

  • 특정 A원소에 대해 B인덱스를 점점 증가시켜가며 A원소보다 큰 B인덱스를 찾는다. (점수 획득)
  • 이후 다음 A원소에 대해 판별할 때 이전 B인덱스 포함 그 이하 인덱스는 필요가 없어진다.
    (현재 A원소는 이전 A원소보다 큰 값이며 이전 B인덱스 포함(이미 사용) 그 이하 인덱스는 이전 A원소에게 사용할 수 없었기 때문에 사용이 불가능해진다.)

소스 코드 (JAVA)

import java.util.*;

class Solution {
    public int solution(int[] A, int[] B) {
        //두 배열 정렬
        Arrays.sort(A);
        Arrays.sort(B);

        //가장 가까운 큰 수 선택
        int result = 0;
        int ind = 0;
        for (int i = 0; i < A.length; i++) {
            while(A[i] >= B[ind]) {
                if (++ind == A.length - 1)
                    return result;
            }
            if (++ind == A.length - 1)
                return result;
            result++;
        }

        return 0;
    }
}