본문 바로가기

알고리즘 공부 및 문제 풀이/프로그래머스(PRO)

[pro] 프로그래머스 level3 12987 숫자 게임 (Java) - 그리디, 투포인터

[문제]

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

 

프로그래머스

코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.

programmers.co.kr

 

[풀이]

A의 각 값들을 B의 값이 최소한의 차이로 이기도록 하면 B의 최종 승점을 가장 높이는 방법이 될 것이다.

이를 위해 A와 B 배열을 모두 정렬한 후 포인터 2개를 두고 각 배열을 가리키도록 한다. A 값보다 B 값이 더 크다면(A와 B 배열을 모두 오름차순 정렬했으므로 가장 근소하게 A보다 B가 더 큰 경우가 될 것임) 승점을 높이고, A 인덱스와 B 인덱스 모두 증가시킨다. 

 

[코드]

 

import java.util.*;

class Solution {
    public int solution(int[] A, int[] B) {
        int answer = 0;
        //B 팀원들이 얻을 수 있는 최대 승점을 return

        Arrays.sort(A);
        Arrays.sort(B);
        
        //1 3 5 7
        //2 2 6 8 
        int aidx = 0;
        int bidx = 0;
        while(bidx < B.length){
            if(A[aidx] < B[bidx]){
                answer++;
                aidx++; 
            }
            bidx++;
        }
        
        return answer;
    }
}