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

문제 풀이 아이디어

삼사법

삼사법이라는 고사를 아시나요? 손빈병법이라는 병법서에서 나온 말로 알고 있는데요. 말 3마리씩 각각 경주를 시킬 때 강 vs 강, 중 vs 중, 약 vs 약으로 경주를 시키는 대신, 강 vs 약, 중 vs 강, 약 vs 중으로 각각 경주를 시켜서 2:1의 승리를 노리는 전략입니다. 즉 약한 말을 버리는 카드로 사용해서 나머지 2판을 가져오는 전략입니다. 지금 우리가 풀어 있는 문제가 바로 이 삼사법을 활용해서 풀어야 하는 문제입니다.

즉 B 팀이 최대한 많은 점수를 얻기 위해서는 A팀을 약한 선수부터 나열한 다음 그 선수를 이길 수 있는 가장 “약한” 선수를 내보내야 합니다. 즉 현재 가장 약한 선수를 이길 수 없는 선수는 차라리 강한 선수와 붙여서 지게하는 것이 나은 방법입니다.

O(N)의 시간복잡도를 가진 코드를 사용해야 한다!

문제를 처음에 풀 때는 이중반복문을 통해서 A팀과 B팀의 선수를 비교하면서 점수를 세는 방법을 떠올렸습니다. 하지만 배열의 길이가 최대 100,000입니다. O(N^2)인 이중반복문을 사용하게 되면 시간초과입니다. O(N^2)의 시간복잡도를 가진 코드를 제출한 결과 정확성 테스트는 모두 통과했지만 효율성 테스트는 통과하지 못했습니다.

Stack을 활용하자

제가 떠올린 방법은 stack을 활용하는 것입니다. 위에서 설명한대로 A팀의 선수가 나왔을 때 B팀에서는 그 선수를 이길 수 있는 가장 약한 선수가 나와야 합니다. a팀과 b팀을 가장 약한 선수가 위로 오도록 해서 stack으로 만듭니다. stackA에서 pop을 해서 현재 가장 약한 선수 a 를 뽑습니다. 그리고 stackB에서 그 선수를 이길 수 있는 선수가 나올 때까지 pop을 합니다. 이 때 a를 이길 수 없는 선수는 어차피 승리를 할 수 없는, 삼사법에서 약한 말에 해당하는, 버리는 카드입니다.

stackB에서 a를 이길 수 있는 선수가 나오면 B팀에 1점을 추가합니다. 그리고 다시 stackA에서 그 다음 약한 선수를 뽑고 stackB에서 그 선수를 이길 수 있는 선수가 나올 때까지 pop을 하면 됩니다. 이 작업을 stackA 과 stackB가 빌 때까지 진행하면 됩니다.

Stack을 활용하는 경우의 시간 복잡도

아래 코드를 참고해주세요. 코드를 보시면 while문 안에 while문이 있는 이중반복문이 있는 것을 볼 수 있습니다. 하지만 이는 무늬만 이중반복문일 뿐 실제로는 O(2N) 즉 O(N)의 시간복잡도를 가지는 코드입니다. 반복문은 stackA와 stackB에서 모든 원소가 pop되면 종료되기 때문입니다.

코드

func solution(_ a:[Int], _ b:[Int]) -> Int {
    // a, b를 stack으로 만들기 (약한 선수가 위로 오도록)
        //👉 array로 stack을 구현하는 경우 내림차순으로 정렬해야 약한 선수가 위로 오게됨.
    var stackA = a.sorted(by: >)
    var stackB = b.sorted(by: >)
    // B팀이 이기는 횟수
    var ans = 0

    while !stackA.isEmpty {
        let a = stackA.popLast()! //👉 현재 a에서 가장 약한 선수
        while !stackB.isEmpty {
            let b = stackB.popLast()! //👉 현재 b에서 가장 약한 선수
            if b > a { //👉 b에서 가장 약한 선수가 a에서 가장 약한 선수를 이길 수 있을 때까지 pop
                ans += 1 //👉 이기면 점수 +1
                break
            }
        }
    }
    return ans
}