숫자 게임 (level3)

링크

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

문제

회사의 사원들은 N명씩 두 팀으로 나눠 숫자 게임을 하려고 한다. 두 개의 팀을 각각 A팀과 B팀이라고 할 때, 숫자 게임의 규칙은 다음과 같다.

1. 먼저 모든 사원이 무작위로 자연수를 하나씩 부여받는다.
2. 각 사원은 딱 한 번씩 경기를 한다.
3. 각 경기당 A팀에서 한 사원이, B팀에서 한 사원이 나와 서로의 수를 공개한다. 그때 숫자가 큰 쪽이 승리하게 되고, 승리한 사원이 속한 팀은 승점을 1점 얻게 된다.
4. 만약 숫자가 같다면 누구도 승점을 얻지 않는다.

A팀이 B팀에게 대진표를 미리 공개했을 때, B팀이 얻을 수 있는 점수의 최대를 얼마일지 구하라.

예제로 이해

A = [5,1,3,7]
B = [2,2,6,8]

위와 같이 플레이하면 최대 승점을 구할 수 있다.

코드

function solution(A, B) {
    let result = 0
    let aHead = 0
    let bHead = 0
    
    A.sort((a, b) => b - a)
    B.sort((a, b) => b - a)
    
    for(let i = 0; i < A.length; i++) {
        if(A[aHead] < B[bHead]) {
            aHead++
            bHead++
            result++
        } else {
            aHead++
        }
    }
    
    return result
}

코드 풀이

이 문제는 자신이 점수를 얻을 수 없다면 A팀 대진표의 최대값을 팀의 최소값으로 제거하는 방식으로 풀이가 되어야한다.

A팀의 대진표가 공개되어있기 때문에 그 숫자가 나올 자리를 알고 있는 것이 되므로 숫자의 순서가 바뀌어도 괜찮다는 전제하에 먼저 정렬을 진행한다. 두 팀 모두 내림차순으로 정렬을 진행한다.

정렬이 완료되면 A팀과 B팀의 가장 앞에서부터 숫자의 크기를 비교한다. 만약 B팀이 더 크다면 두 팀의 현재 index를 가리키는 변수의 값을 모두 +1씩 진행하며, A팀이 더 크다면 A팀의 현재 index 변수에만 +1을 진행한다.

A팀에서 현재 나올 큰 수를 B팀이 가지고 있는 가장 작은 숫자로 제거한다는 개념을 적용하기 때문에 A팀의 현재 index에만 +1을 진행한다. 가장 작은 숫자는 어차피 B팀의 가장 마지막에 위치하기 때문에 따로 코드에서 명시를 해주지 않아도 무관하다. (A팀이 더 큰 수가 있게 될 경우에 B팀의 마지막 숫자로 해당 경기를 지겠다는 식인데, 어차피 for문의 반복 횟수는 정해져 있기 때문에 B팀의 마지막 숫자까지 B팀의 현재 index를 가리키는 변수가 도달하지 못하기 때문에 코드에서 명시를 하지 않아도 된다. 단, while문으로 반복을 진행할 경우에는 가장 뒤의 숫자를 가리키는 변수가 필요해진다.)

이 과정이 A팀의 마지막 번호를 가리킬때까지, 즉 배열의 길이만큼 진행 후에 B팀이 더 컸던 경우를 카운트해서 반환하도록 한다.

이 문제는 pop, shift를 사용해서 경기에 사용된 숫자들을 삭제하는 방식으로도 함수를 구현할 수 있지만, shift와 pop은 index 변수의 값을 +1씩 증가시키는 방법보다 오랜 시간이 걸리므로 프로그래머스 효율성에서 시간초과를 받게된다.