[12987] 숫자 게임

✔ 숫자 게임

[프로그래머스 12987]

문제 분석하기

최대 힙인 우선순위 큐에 두 배열의 값을 저장한 후, 두 큐에서 값을 꺼내와

B의 최대 값이 A의 최대값을 이길 수 있다면 B 팀원들이 얻을 수 있는 최대 승점을 증가시킨 후 A와 B의 원소를 제거시켜줌

B의 최대 값이 A의 최대값을 이길 수 없다면 A의 원소를 제거시켜줌

 

예) A = [5, 1, 3, 7], B = [2, 2, 6, 8]

	apq	bpq	apq.peek()	bpq.peek()	answer
1	[5, 1, 3, 7]	[2, 2, 6, 8]	7	8	0 → 1
2	[5, 1, 3]	[2, 2, 6]	5	6	1 → 2
3	[1, 3]	[2, 2]	3	2	2
4	[1]	이전 라운드에서는 무조건 지므로 더 뒤에서 이길 수 있는 경우를 위해 2를 제거하지 않음 [2, 2]	1	2	2 → 3

손으로 풀어보기

1. 최대 힙인 우선순위 큐에 두 배열의 값을 저장
2. 두 큐에서 값을 꺼내와
   B의 최대 값이 A의 최대값을 이길 수 있다면 B 팀원들이 얻을 수 있는 최대 승점을 증가시킨 후 A와 B의 원소를 제거시켜줌
   B의 최대 값이 A의 최대값을 이길 수 없다면 A의 원소를 제거시켜줌

슈도코드 작성하기

A(A 팀원들이 부여받은 수)
B(B 팀원들이 부여받은 수)
answer(B 팀원들이 얻을 수 있는 최대 승점)
apq(A를 저장할 최대값 우선순위 큐)
bpq(B를 저장할 최대값 우선순위 큐)
for(i -> B의 길이만큼) {
    apq와 bpq에 A, B 배열 값 저장
}
for(i -> B의 길이만큼) {
    a(apq의 최대값)
    b(bpq의 최대값)
    if(b가 a보다 크다면) {
        answer 증가
        bpq에서 b 제거
    }
    apq에서 a 제거
}
answer 반환

코드 구현하기

/**
 * 12987) 숫자_게임
 */
public class L015_12987 {
    // A(A 팀원들이 부여받은 수)
    // B(B 팀원들이 부여받은 수)
    public int solution(int[] A, int[] B) {
        // answer(B 팀원들이 얻을 수 있는 최대 승점)
        int answer = 0;
        // apq(A를 저장할 최대값 우선순위 큐)
        PriorityQueue<Integer> apq = new PriorityQueue<>(Collections.reverseOrder());
        // bpq(B를 저장할 최대값 우선순위 큐)
        PriorityQueue<Integer> bpq = new PriorityQueue<>(Collections.reverseOrder());
        // apq와 bpq에 A, B 배열 값 저장
        for (int i = 0; i < B.length; i++) {
            apq.add(A[i]);
            bpq.add(B[i]);
        }
        for (int i = 0; i < B.length; i++) {
            // a(apq의 최대값)
            int a = apq.peek();
            // b(bpq의 최대값)
            int b = bpq.peek();
            // b가 a보다 크다면
            if (a < b) {
                // answer 증가
                answer++;
                // bpq에서 b 제거
                bpq.remove();
            }
            // apq에서 a 제거
            apq.remove();
        }
        // answer 반환
        return answer;
    }

    // 테스트 케이스
    public static void main(String[] args) {
        L015_12987 solution = new L015_12987();

        int[] A = { 5, 1, 3, 7 };
        int[] B = { 2, 2, 6, 8 };

        int result = solution.solution(A, B);

        System.out.println(result);
    }
}