[프로그래머스, 12987] 숫자 게임 (java)

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

프로그래머스

728x90

---

메모리: 63.1 MB, 시간: 112.35 ms

사용 알고리즘: 정렬

 

A와 B의 점수를 모두 오른차순으로 정렬한 후, A 배열을 순회하며 항상 최선의 경우를 찾는다.

항상 최선의 경우란, 아직 출전하지 않은 B팀의 점수 중 현재 확인 중인 A팀의 점수보다 큰 수 중 가장 작은 점수가 출전하는 것이다.

만약 그런 점수를 찾을 수 없다면, 아직 확인하지 않은 남은 A팀의 점수들도 찾을 수 없다는 뜻이므로 break 해준다.

(A 배열을 오름차순 정렬했기 때문에 남은 A팀의 점수들은 현재 확인 중인 점수보다 모두 크다. 그런데 현재 확인 중인 점수보다 큰 수도 찾지 못했는데 남은 A팀의 점수들보다 큰 점수를 찾을 수는 없다.)

import java.util.*;

class Solution {
    
    public int solution(int[] A, int[] B) {

        // A, B팀이 부여받은 점수 정렬
        Arrays.sort(A);
        Arrays.sort(B);
        
        int answer = 0;
        int bi = 0; // B의 인덱스
        for(int i = 0; i < A.length; i++) {
            // A[i]보다 큰 수 중 가장 작은 수 찾기
            while(bi < B.length && A[i] >= B[bi]) bi++;
            
            // A[i]보다 큰 수가 없다면 더 이상 확인하지 않음
            if(bi == B.length) break;
            
            // A[i]보다 큰 수 중 사용 가능한 가장 작은 수를 찾은 경우
            if(A[i] < B[bi]) {
                bi++;
                answer++;
            }
        }
        
        return answer;
    }
}