Programmers - 숫자 게임

---

title: Programmers - 숫자 게임
date: 2022-08-20
tags:

• Algorithm

---

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

문제 요약

A팀과 B팀은 각 N명씩 존재하며, 각 사람들은 1G 이하의 자연수를 받는다.
A팀의 자연수 순서가 정해졌을 때, B팀은 해당 수보다 큰 수를 제출할 때 승리한다. 이 때 얻을 수 있는 최대 승리 횟수를 retrun한다.

문제 풀이

Level 3에 어울리지 않는 너무 쉬운 문제이다.
A의 순서가 주어진다는 것은 A가 제출하는 수에 맞추어 원하는 수를 제출할 수 있다는 뜻이다.
A의 순서를 고정할 필요 없이, A와 B를 정렬하여 풀면 된다.


A,B 모두 오름차순으로 정렬한다.
B는 앞에서부터 순서대로 A와 비교를 시작한다.
B가 클 경우 승리하므로 A의 앞에서 없애며, 반대의 경우 승리하지 못하므로 A의 가장 큰 수를 소모시켜야 하기에 A의 뒤에서부터 없앤다.


효율성 테스트를 포함하여 최대 약 11ms의 성능을 확인할 수 있었다.

프로그램

#include <vector>
#include <algorithm>

using std :: vector ;
using std :: sort ;

int solution ( vector < int > A , vector < int > B )
{
    int answer = 0 ;
    int iHumanSize = A.size () ;
    int iALeftIndex = 0 ;
    int iARightIndex = iHumanSize - 1 ;



    sort ( A.begin () , A.end () ) ;
    sort ( B.begin () , B.end () ) ;

    for ( int i = 0 ; i < iHumanSize ; ++i )
    {
        if ( A [ iALeftIndex ] < B [ i ] )
        {
            ++ iALeftIndex ;
            ++ answer ;
        }
        else
        {
            -- iARightIndex ;
        }
    }


    return answer ;
}