[프로그래머스] Swift - 숫자 게임

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

프로그래머스

 

2023.07.03 기준 Level 3

 

알고리즘 공부용으로 풀고 기록하는 글입니다!
참고만 해주시고 더 좋은 풀이법이 있다면 알려주세요!

 

아이디어

A팀의 순서가 정해져 있다는 것은 속임수입니다.

어차피 B팀의 순서를 우리 마음대로 정할 수 있기 때문에 A팀의 정해진 순서도 의미가 없습니다.

B팀이 최대한 많이 이기기 위해서는 A팀에서 낸 숫자보다 최대한 작은 차이로 큰 숫자를 내서 이기는 것이 가장 많이 이기는 방법입니다.

 

➡️ A와 B를 정렬해서 A에서 가장 큰 수를 내면 B에서도 가장 큰 수를 내도록 합니다.

 

만약 A에서 가장 큰 수와 B에서 가장 큰 수를 비교했을 때 A 쪽이 더 크다면 어차피 B쪽에 남은 카드로는 그 수를 이길 수 없기 때문에 해당 라운드는 진 것으로 판단하고 넘어갑니다.

 

즉, 계속 남아 있는 카드들 중에서 서로 가장 큰 수 끼리 비교하면 되는 문제입니다.

 

풀이

fileprivate func solution(_ a:[Int], _ b:[Int]) -> Int {
    let a = a.sorted()
    var b = b.sorted()
    var result = 0
    
    for i in stride(from: a.count-1, through: 0, by: -1) {
        let num = a[i]
        let last = b.last!
        if last > num {
            _ = b.popLast()
            result += 1
        }
    }
    
    return result
}

a, b를 오름차순으로 정렬합니다.

내림차순으로 하지 않은 이유는 Swift에서 removeFirst는 O(n)인 반면 popLast나 removeLast는 O(1)이기 때문입니다.

 

가장 큰 수 끼리 비교하기 위해 stride를 사용하여 배열의 뒤부터 검사합니다.

a와 b 팀에서 각각 큰 수 끼리 비교해서 b 쪽이 더 크다면 b팀의 승점(result)를 1 더해주는 방식입니다!

 

 

마무리

3단계 문제로 분류되어 있지만 사실 2단계 정도가 적합하지 않나 생각됩니다..!

A팀의 순서가 주어졌다는 사실에 집착하지 않고 문제의 핵심인 B팀이 가장 많이 이기게 하는 시나리오를 구하는 것에 집중해야 했던 문제였습니다.