프로그래머스 - 숫자게임(Java, LV3)

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

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

풀이

처음 풀었던 풀이

• A 팀과 B 팀을 전부 오름 차순으로 정렬한다.
• 앞에서부터 A팀의 패를 이길 수 있는 B팀의 패를 찾는다.
• 이길 수 있는 패를 찾았을 경우, B팀 내에서 이번 대결의 상대를 탐색하는 것은 중단한다. 
• 이길 수 있는 패를 찾았을 경우, INF 상수를 통해 마킹하여 다음 대결에 사용하지 않는다.

 

이 때, 오름차순 정렬으로 되어있기에, 앞에서부터 최소 비용으로 이길 수 있는 상대를 찾을 수 있다.

(단, 이때 대결에 나선 B팀의 멤버는 제외해주기 위해 INF 상수를 활용)

import java.util.*;

class Solution {
    public static final int INF = -1;
    public int solution(int[] A, int[] B) {
        int answer = 0;
        
        // sort 
        Arrays.sort(A);
        Arrays.sort(B);
        
        // A를 이길 수 있는 B 찾기
        for(int i=0;i < A.length; i++){
            boolean check = false;
            for(int j=0; j< B.length; j++){
                if (check)
                    break;
                
                // 낮은 것 중 이기는 거
                if(A[i] < B[j]){
                    B[j] = INF;
                    check = true;
                    answer++;
                }
            }
        }
    
        return answer;
    }
}

그런데 이렇게 풀면 시간효율성에 문제가 생긴다.

이중 for문을 돌기에 O(N^2) 의 시간복잡도로 효율성을 통과하지 못한다.

효율성을 위해 생각해보다 떠오르지 않아서 다른 사람이 푼 풀이를 참조했다.

 

풀이의 핵심은 다음과 같다.

• 앞에서부터 양팀의 패를 보는 게 아닌 뒤에서부터 양팀의 패를 본다
• B팀의 경우 이길 수 없는 상대일 경우 굳이 다음 패를 사용하지 않아도 된다. 돌려말해 어차피 질 거면, 제일 안좋은 패를 사용한다고 치고 index를 더 내리지 않는다.
• 그렇게 A팀의 전체 상대만 비교해서 이길 수 있는 상황을 count 해주면 된다.

import java.util.*;

class Solution {
    public static final int INF = -1;
    public int solution(int[] A, int[] B) {
        int answer = 0;
        
        // sort 
        Arrays.sort(A);
        Arrays.sort(B);
        
        // A를 이길 수 있는 B 찾기 (끝에서부터)
        int i_b = A.length-1; 
        for(int i_a=A.length-1; i_a >=0; i_a--){
            // 이기는 패
            if (B[i_b] > A[i_a]){
                answer++;
                i_b--;
            }
        }
    
        return answer;
    }
}