[Programmers] 숫자게임

1. 문제

문제링크

문제 설명

xx 회사의 2xN명의 사원들은 N명씩 두 팀으로 나눠 숫자 게임을 하려고 합니다. 두 개의 팀을 각각 A팀과 B팀이라고 하겠습니다. 숫자 게임의 규칙은 다음과 같습니다.

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

전체 사원들은 우선 무작위로 자연수를 하나씩 부여받았습니다. 그다음 A팀은 빠르게 출전순서를 정했고 자신들의 출전 순서를 B팀에게 공개해버렸습니다. B팀은 그것을 보고 자신들의 최종 승점을 가장 높이는 방법으로 팀원들의 출전 순서를 정했습니다. 이때의 B팀이 얻는 승점을 구해주세요.
A 팀원들이 부여받은 수가 출전 순서대로 나열되어있는 배열 A와 i번째 원소가 B팀의 i번 팀원이 부여받은 수를 의미하는 배열 B가 주어질 때, B 팀원들이 얻을 수 있는 최대 승점을 return 하도록 solution 함수를 완성해주세요.

제한사항

• A와 B의 길이는 같습니다.
• A와 B의 길이는 1 이상 100,000 이하입니다.
• A와 B의 각 원소는 1 이상 1,000,000,000 이하의 자연수입니다.

2. 접근방법

주어진 문제를 해결하기 위해 다음과 같은 접근 방식을 생각했습니다. 먼저 A 배열은 이미 순서가 정해져 있다고 하였으나 내림차순으로 정렬하였습니다. 그리고 B 배열도 내림차순으로 정렬하였습니다.
이제 A 배열을 순회하면서, 현재 B 배열에서 가장 큰 수와 비교합니다. 만약 현재 B 배열의 가장 큰 수가 A 배열의 현재 수보다 크다면, 그 수를 사용하여 승점을 획득할 수 있으므로 승점을 증가시키고, B 배열에서 해당 수를 제거합니다. 그리고 다음 A 배열의 요소를 비교합니다.
만약 B 배열의 가장 큰 수가 A 배열의 현재 수보다 작다면, 다음 비교에서 사용해야 승점을 획득할 확률을 높일 수 있을 것입니다.
이러한 방식으로 문제를 해결하면, A 배열의 순회와 B 배열에서 요소 제거를 통해 모든 요소를 한 번씩만 처리하면서 승점을 얻을 수 있는 최대 개수를 구할 수 있습니다.

아래의 방법으로 정답을 구할 수 있었습니다.
하지만 효율성 부분에서 점수를 얻지 못했습니다.

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

원인으로는 B.shift(); 부분에서 배열의 요소를 제거한 후에는 배열의 모든 요소가 한 칸씩 앞으로 이동해야 하기 때문에 대량의 요소를 처리해야 할 때는 성능 문제가 발생할 수 있으므로 다른 방법을 고려하는 것이 좋습니다.

B배열의 요소를 제거하는 방법이 아닌
조건에 충족한다면 다음 요소를 선택하는 방법을 택하여 해결할 수 있습니다.
해당 방법은 Stack을 활용하는 문제에도 유용하게 사용할 수 있을 것 같습니다.

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