[프로그래머스/Level 3] 숫자 게임 (C++)

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

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

제가 제일 어려워하는 유형 중 하나인 그리디 문제였습니다. 사실 다 약함

 

일단 입력값의 크기가 최대 100,000 이라서 완전탐색으로는 TLE가 발생합니다. 그래서 DP, 이분탐색, 힙, 그리디 다양하게 생각해봤는데 도저히 문제를 해결하지 못해서 풀이를 참고했습니다. A팀의 출전 순서가 이미 공개되어 A 배열은 고정 시켜야 한다는 고정관념에 사로잡혀 문제를 해결하는데 어려움을 겪었던 것 같습니다.

 

풀이

1. A배열과 B배열을 오름차순으로 정렬

2. A인덱스와 B인덱스를 따로 선언과 초기화

3. A[aIdx]와 B[bIdx]를 비교 (B의 인덱스가 B의 크기가 되면 종료)

   3-1. A[aIdx] < B[bIdx] 면 두 인덱스 모두 증가

   3-2. A[aIdx] >= B[bIdx] 면 B의 인덱스만 증가, answer 값 증가 (해당 카드는 버리는 카드로 쓰겠다는 의미)

 

#include <string>
#include <vector>
#include <algorithm>
using namespace std;

int solution(vector<int> A, vector<int> B) {
    int answer = 0, aIdx = 0, bIdx = 0;
    sort(A.begin(), A.end());
    sort(B.begin(), B.end());
    
    while(1) {
        if(bIdx == B.size()) break;
        if(A[aIdx] < B[bIdx]) {
            aIdx++;
            bIdx++;
            answer++;
        } else {
            bIdx++;
        }
    }
    
    return answer;
}