[JS] 숫자 게임 - 비겼을 때 처리를 해주자!

옛날 문제를 자꾸 풀게 되는데,뭔가 창의력을 요구한달까..

 

요즘은 유형이 어느정도 나뉘잖아요. 오히려 접근이 편한데 옛날 문제는 약간 창의력을 보네요.이 문제는 엣지 케이스 처리만 잘해주면 크게 어려운 건 없습니다.

(17, 18번이 문제이신 분들은 비겼을 때만 처리해주면 되거든요...!) 

---

문제 요약

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 이하의 자연수입니다.

테스트케이스

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

테케 1 참고

접근 방법

다들 나름대로 자신만의 방법이 있겠습니다만,

전 뭔가 이런 number 형식의 1차원 데이터는 꼭 이진탐색을 써야할 것 같은 기분이 들더라구요.

 

A팀의 정보를 정렬한 다음, 그 값보다 큰 B팀의 인원이 몇 명인지 세면 금방 해결할 수 있습니다.

 

예를 들어 테스트케이스#1 의 경우

 

7 이상인 B 팀 => 1명
5 이상인 B 팀 => 2명
3 이상인 B 팀 => 2명
1 이상인 B 팀 => 4명

 

이렇게 되면 쭉 순회하면서 정답을 세 주면서 계산해주면 됩니다.

 

다만, 언제나 중복값이 있는 경우(테케 #17, #18)는 생각해줘야겠죠. 이건 이진탐색에서 처리해주면 됩니다.

자세한 건 아래에서 이야기하죠!

 

정답 코드

function bsearch(target, arr) {
    let [left, right] = [0, arr.length - 1];
    let mid = Math.floor(right / 2);
    while (left <= right) {
        if (arr[mid] === target) {
            while (arr[mid] === target) {
                mid++;
            }
            return mid;
        }
        if (arr[mid] < target) left = mid + 1;
        else right = mid - 1;
        mid = Math.floor((left + right) / 2);
    }
    return left;
}

function solution(A, B) {
    const canWinMap = [];
    const n = A.length;
    A.sort((a, b) => a - b);
    B.sort((a, b) => a - b);
    
    A.forEach((v, i) => {
        canWinMap[n - i - 1] = n - bsearch(v, B);
    });
    
    let answer = 0;
    
    for (const possibleNum of canWinMap) {
        if (possibleNum - answer > 0) {
            answer++;
        }
    }
    
    return answer;
}

 

팁 1. 이진 탐색의 활용법

A.forEach((v, i) => {
    canWinMap[n - i - 1] = n - bsearch(v, B);
});

 

이진 탐색은 정확한 타깃 값의 index를 return해줍니다.

배열이 정렬되어있다는게 보장되어 있기 때문에 다음 수식을 만족합니다.

 

A 팀의 특정 점수 이상인 B 팀 인원 = B 팀의 전체 인원(n) - 타깃의 index

 

만약 해당 target의 값이 없어도 left를 return 해주면 해당 값 이상인 index를 return 해줍니다.

다만, 여기서 문제가 되는게 중복값인데요.

 

팁 2. index를 끝 쪽으로 맞춰주는 이진 탐색

function bsearch(target, arr) {
    let [left, right] = [0, arr.length - 1];
    let mid = Math.floor(right / 2);
    while (left <= right) {
        if (arr[mid] === target) {
            while (arr[mid] === target) {
                mid++;
            }
            return mid;
        }
        if (arr[mid] < target) left = mid + 1;
        else right = mid - 1;
        mid = Math.floor((left + right) / 2);
    }
    return left;
}

 

중복값이 나온다면 중복값의 가장 끝 쪽의 index를 return 해줘야합니다.

 

예를 들어,

[1, 1, 1, 1, 1, 2, 3, 4, 5] 배열의 target이 1이라면, 5를 return 해줘야겠죠.

 

그 처리를 위해서 조건 문 안에서 index를 끝쪽으로 맞춰주기 위한 while문을 한 번 더 돌려줍니다.

---

쉬운데 약간의 예외 케이스만 생각해주면 더 쉽네요.

그럼 이만!