프로그래머스 3단계/효율성 : [숫자 게임] Java 풀이

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

코딩테스트 연습 - 숫자 게임

 

 

팀 A의 카드 배열 [ 5, 1, 3, 7 ]
팀 B의 카드 배열 [ 2, 2, 6, 8 ]

여기서 팀 B가 최대로 점수를 많이 가져가는 방법은
 
1 : 2 승리
3 : 6 승리
7 : 8 승리
5 : 2 패배

3점 일것입니다. 

문제 난이도는 쉽지만, 3단계 문제답게 효율성 테스트가 까다로운 문제입니다. 

 

정답 코드

import java.util.*;

class Solution {
    public int solution(int[] A, int[] B) {
        int answer = 0;

        Queue<Integer> heap = new PriorityQueue<>();
        Queue<Integer> heap2 = new PriorityQueue<>();

        for (int i : A) heap.offer(i);
        for (int i : B) heap2.offer(i);


        while (!heap.isEmpty() && !heap2.isEmpty()) {

            int left = heap.poll();
            int right = heap2.poll();

            while(left >= right){
                if (! heap2.isEmpty()) right = heap2.poll();
                else return answer;
            }
            answer++;
        }

        return answer;
    }
}

 

 

 

저는 이 문제를 heap을 이용해서 풀었습니다. 

heap 두개를 만들어서 인자를 offer해줍니다.

heap1은 A팀의 카드가 오름차 순으로 들어가고, heap2는 B팀의 카드가 오름차순으로 들어갑니다. 

변수 left는 A팀의 카드, 변수 right는 B팀의 카드 일것입니다.

만약 right가 left를 이기지 못한다면 right에서 그 다음 카드를 계속 꺼내줍니다.

여기서 while문은 heap2가 비어있을땐 게임이 끝나버리니 heap1의 뒷 카드 (높은 숫자)는 게임이 끝날 때까지 사용할 수 없습니다.

 

다른 풀이

class Solution {
    public int solution(int[] A, int[] B) {
    int win = 0;

        Arrays.sort(B);
        Arrays.sort(A);


        Stack<Integer> stackA = new Stack<Integer>();
        Stack<Integer> stackB = new Stack<Integer>();

        for(int j=0; j<A.length; j++) {
            stackA.push(A[A.length-1-j]);
            stackB.push(B[A.length-1-j]);
        }
        for(int i = 0; i<A.length; i++) {
            if(stackA.peek()<stackB.peek()) {
                win++;
                stackA.pop();
                stackB.pop();
            } else {
                stackB.pop();
            }
            if(stackA.isEmpty() || stackB.isEmpty()) {
                break;
            }
        }

        return win;
}
}