[프로그래머스, C++] 숫자 게임

문제 링크

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

 

 

 

풀이

주어진 문제가 구하는 것은 "최대 승점"이다.

A팀의 점수보다 큰 B팀의 점수 중에서 최소 값으로 1경기씩 나간 것이 "최대 승점"이다.

그래서 sort로 정렬해서 할까하다가 priority_queue에 넣고 (넣은 방향 기준)내림차순 정렬로 하나씩 빼면서 승점을 올렸다.

 

// 요약

1) 우선순위 큐에 push

 

2) 승점 추가(A팀의 점수보다 큰 B팀의 점수 중 최소 값을 결정)

반복문(B팀원의 수가 없을 때까지)

{

    A팀원 숫자

    반복문(B팀원의 수가 없을 때까지)

    {

        A팀원의 숫자보다 클 경우 승점 추가 및 break;

    }

}

 

 

#include <string>
#include <vector>
#include <queue>
#include <iostream>

using namespace std;

// 모든 사원이 무작위 자연수 하나씩
// 각 사원은 딱 한 번 경기
// A팀, B팀에서 한 사원씩 나와 숫자 공개
// 숫자가 큰 쪽이 승리, 승점 +1점
// 숫자가 같다면 무승부, 아무도 승점 X

// A 팀원들의 출전 순서대로의 숫자 배열 A
// B팀의 i번 팀원이 부여받은 수 B

int solution(vector<int> A, vector<int> B) {
    int answer = 0;
    int size = A.size();
    priority_queue<int, vector<int>, greater<int>> teamA;      // default: 오름차순(나오는 방향 기준)
    priority_queue<int, vector<int>, greater<int>> teamB;
    
    for(int i=0; i<size; i++){
        teamA.push(A[i]);
        teamB.push(B[i]);
    }
    
    // A의 점수보다 큰 B팀의 점수중 최소
    while(!teamB.empty()){          // B 팀의 수를 다 썼을 경우
        int numA = teamA.top();
        teamA.pop();
        // printf("numA(%d)\n", numA);
        while(!teamB.empty()){
            int numB = teamB.top();
            teamB.pop();
            // printf("numB(%d)\n", numB);
            if(numA < numB){
                answer++;
                break;
            }
        }
    }
    
    
    return answer;              // B 팀의 최대 승점
}