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

 

 

https://school.programmers.co.kr/learn/courses/30/lessons/12987?language=swift

프로그래머스

 

내 답안

import Foundation

func solution(_ A: [Int], _ B: [Int]) -> Int {
    let ASort = A.sorted()
    let BSort = B.sorted()
    
    var aIndex = 0
    var bIndex = 0
    var score = 0
    
    while aIndex < ASort.count && bIndex < BSort.count {
        if BSort[bIndex] > ASort[aIndex] { // B팀이 A팀을 이길때
            score += 1
            aIndex += 1  // A팀 다음 선수로
        }
        bIndex += 1  // B팀은 다음 선수로 (이기든 지든)
    }
    
    return score
}

---

Review

일단 효율성 테스트 + 배열의 길이가 100,000 이 되는 것을 보고 O(N^2)은 넘으면 안 된다고 생각했습니다.

처음에는 어떻게 푸는 게 가장 효율적 일지 몰라서, 투포인터나, 흔한 그리디(정렬) 방법을 생각해 냈습니다.

B만 정렬할 때는 자꾸 예외케이스가 생겨 틀렸는데, A까지 정렬을 하니 문제가 풀렸습니다.

 

실제 A : [5, 1, 3, 7], B : [2, 2, 6, 8]  배열로 예시를 들어보겠습니다.

1. B정렬과 A 정렬된 배열을 아래처럼 표현했습니다.
bIndex = 0 aIndex = 0을 비교해 봅니다. 2가 1보다 더 크니까 score를 올려주고 둘 다 index를 올려주어 다음 비교로 넘어갑니다.

score = 1

2. bIndex = 1, aIndex = 1을 비교해 봅니다. 2 보다는 3이 더 크니까 aIndex는 그대로 두고 bIndex만 올려줍니다.

score = 1

3. bIndex = 2 aIndex = 1을 비교했습니다. 6이 3보다 더 크니까 두 개의 index를 모두 올려줍니다.

score = 2

4. bIndex = 3 aIndex = 2를 비교해줍니다. 8이 5보다 더 크니까 이번에도 두 개의 index를 모두 올려줍니다.

score = 3

5. bIndex = 4 aIndex = 3, 이미 모든 index를 탐색했으니, while 문을 종료합니다.

 

저는 투포인터를 활용해서 풀었지만, 다시 생각해 보니 투포인터를 사용할 필요가 없었습니다..! 

아래는 좋아요가 가장 많은 코드입니다. 문제를 풀고, 다른 사람의 풀이를 보니 확실히 많이 배워 갑니다.

import Foundation

func solution(_ a:[Int], _ b:[Int]) -> Int {

    let sA = a.sorted()
    let sB = b.sorted()
    var index = 0

    for e in sB {
        if e > sA[index] {
            index += 1
        }
    }

    return index
}