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

문제 링크

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

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

풀이

전체적인 풀이 과정은 다음과 같다.

 

1. 주어진 A, B 배열을 오른차순 정렬할 수 있는 각각의 우선순위 큐(pqA, pqB) 생성 후 A와 B 배열의 요소를 모두 삽입
2. 이후 pqB의 숫자들이 모두 없어질 때까지 pqA와 pqB 숫자를 뽑아 비교
   1. 만약 뽑은 숫자에서 pqB 쪽이 더 크면 답 + 1
   2. 그렇지 않다면 pqB 쪽에서 뽑은 숫자가 더 클때까지 pqB에서 계속 뽑는다.

 이 문제의 경우 일어날 수 있는 가지수를 모두 생성한 다음 비교하는 경우 배열의 최대 길이가 100,000 이기에 시간 초과가 발생할 수 있다. 또한 이 경우 최선의 수가 작은 값들에서 발생할 수 있기 때문에 이들을 정렬한 다음 무작정 최대값끼리만 비교할 수는 없다.

 그렇다면 쉽게 값을 비교하기 위해 특수적인 상황을 부여해야 한다. 예를 들어 A 배열과 B 배열 속 값들을 오름차순 정렬하고 나열하면 다음과 같이 된다.

 a0 <= a1 <= a2 <= a3 <= a4 <= a5 <= ....

 b0 <= b1 <= b2 <= b3 <= b4 <= b5 <= ....

 이런 상황에서 해당 수열 속 최선의 경우들이 (b1, a1), (b3, a3), (b4, a4) ... 라 할 경우, a쪽 배열의 값들을 한 쪽으로 밀어 값을 일반화((b1, a0), (b3, a1), (b4, a2) ....)할 수 있다. 이는 a 배열 속 값들이 정렬되어 있기 때문에 더 작은 수들이 존재한다면 값을 (bn > an의 상황을 bn > am의 경우로 대체 가능) 바꿔도 문제가 없기에, 이처럼 a쪽 배열들을 오름차순으로 정렬한 상태에서 순차적으로 값을 뽑고, 이보다 클 수 있는 b배열의 요소를 찾기만 하면 된다.

 결국 a배열와 b배열을 우선순위 큐(pqA, pqB)를 통해 오름차순 정렬 후 pqA와 pqB에서 숫자를 뽑아 비교하며, 만약 pqB쪽 숫자가 크다면 답 + 1을 하고 그렇지 않다면 pqA 쪽의 숫자보다 큰 숫자가 나올 때까지 pqB에서 숫자를 뽑으면 된다. 이후 누적된 답을 반환하면 된다.

 

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

        PriorityQueue<Integer> pqA = new PriorityQueue<>();
        PriorityQueue<Integer> pqB = new PriorityQueue<>();

        for (int i = 0; i < A.length; i++) { //주어진 숫자 오름차순 정렬
            pqA.add(A[i]);
            pqB.add(B[i]);
        }

        while (!pqB.isEmpty()) {//모든 수열 B 속 숫자들에 대하여
            tempA = pqA.poll();
            tempB = pqB.poll();

            if (tempA < tempB) {//각각 뽑은 숫자에 대해 B 쪽이 더 크면
                ++answer;
            } else {//안되면 B쪽이 클때까지 반복 
                while (!pqB.isEmpty()) {
                    tempB = pqB.poll();

                    if (tempA < tempB) {
                        ++answer;
                        break;
                    }
                }
            }
        }

        return answer;
    }
}

결과