문제 링크

문제 풀이 아이디어

문제는 크게 2가지 작업을 수행해야 합니다. 먼저 인센티브를 받지 못하는 사람을 찾고 그 사람을 제외한 사람들 중에 완호의 순위를 찾아내야 합니다.

인센티브를 못 받는 사람 찾기

일단 N이 최대 100,000입니다. 따라서 이중 반복문을 사용해서는 안됩니다. 가장 간단하게 생각하면 이중 반복문을 통해서 서로 비교하고 두 점수 모두 낮은 사람을 찾아내면 명단에서 제외하는 것이 가장 쉬운 방법이지만 O(N^2)은 시간초과이므로 불가능합니다.

따라서 반복문은 O(N), 즉 1번의 순회만으로 인센티브를 받지 못하는 사람을 찾아내야 합니다.

정렬 하기

스위프트의 정렬은 O(NlogN)의 시간복잡도를 가지므로 N의 최댓값을 감안했을 때 사용 가능합니다. 일단 점수는 두 개로 구성됩니다. 각각 근무태도 (index 0)을 근태, 동료평가 (index 1)을 동평이라고 줄여서 부르겠습니다. 일단 주어진 배열 scores를 근태의 내림차순으로 정렬합니다. 다만 같은 근태의 경우 동평을 오름차순으로 정렬합니다. 코드는 아래와 같습니다.

var sorted = scores.sorted(by: { s1, s2 in
    if s1[0] != s2[0] {
        return s1[0] > s2[0]
    } else {
        return s1[1] < s2[1]
    }
})

그리고 순회하기

그리고 정렬된 배열을 순회합니다. 근태에 대해서는 내림차순으로 정렬되어 있기 때문에 뒷사람은 무조건 앞사람 보다 근태가 같거나 작습니다. 같거나 작은 케이스에 대해서 각각 구분해서 살펴보도록 하겠습니다.

1. 만약에 앞사람과 뒷사람이 근태가 같다면, 같은 근태에서는 동평은 오름차순으로 정렬이 되어 있으므로, 뒷사람은 무조건 앞사람보다 동평이 높거나 같습니다.
2. 앞사람과 뒷사람이 근태가 다르다면, 즉 앞사람의 근태보다 뒷사람의 근태가 낮다면, 뒷사람은 동평이 앞사람은 동평보다 낮다면 뒷사람은 인센티브를 받지 못합니다.

1번 케이스의 경우 근태가 동일하므로 뒷사람은 무조건 인센티브를 받을 수 있습니다. 우리가 신경써야하는 부분은 2번 케이스입니다.

2번 케이스에서 뒷사람이 인센티브를 받기 위해서는 앞사람보다 동평이 높거나 같아야 합니다. 아래 그림을 참고해보시면 이해가 빠를 겁니다.

따라서 우리는 순회하면서 현재까지 가장 높은 동평의 값을 변수에 가지고 있어야 합니다. 뒷사람의 동평이 앞사람까지 동평의 최댓값보다 높거나 같을 경우 이 변수를 업데이트하면 됩니다. 이 경우 1번 케이스의 경우 동평이 내림차순으로 정렬되어 있으므로 변수는 항상 업데이트 됩니다. 그리고 2번 케이스의 경우 뒷사람은 동평이 현재까지 가장 높은 동평보다 크거나 같은 경우 (= 변수가 업데이트 되는 경우)에만 인센티브를 부여합니다.

이렇게 하면 이 변수를 업데이트 시킬 수 있는 사람만이 인센티브를 받을 수 있는 사람이 됩니다.

완호의 순위 정하기

이제 인센티브를 받을 수 있는 사람들을 골라냈으므로 완호의 순위를 정하면 됩니다. 문제의 조건처럼 공동순위가 있는 경우 (나보다 점수가 높거나 같은 사람의 수 + 1)이 순위가 됩니다. 처음에 1위로 해두고 순회하면서 나보다 점수가 높거나 같은 사람이 나오면 +1하면 됩니다.

만약 순회하면서 완호보다 두 점수가 모두 높은 상황, 즉 완호가 인센티브를 받지 못하는 상황이 오면 -1을 리턴합니다.

인센티브 필터링 + 순위 정하기 한번에 하기

위 두 작업은 각각의 반복문을 사용해도 되지만 같은 반복문 안에서 한번에 처리가 가능합니다. 먼저 완호가 인센티브를 받을 수 있는지 확인하고 해당 사람이 인센티브를 받을 수 있는지 확인한 후 인센티브를 받을 수 있다면 완호보다 총점이 높은지 확인해서 순위를 정하면 됩니다.

코드

func solution(_ scores:[[Int]]) -> Int {

    // 완호 점수와 총점
    let wanho = scores[0], wanhoScore = wanho.reduce(0, +)
    
    // 정렬 하기: 근태 내림차순, 같은 근태의 경우 동평 오름차순
    var sorted = scores.sorted(by: { s1, s2 in
        if s1[0] != s2[0] {
            return s1[0] > s2[0]
        } else {
            return s1[1] < s2[1]
        }
    })

    // 완호의 순위 (1등에서 시작하고 점수 높은 사람 나올 때마다 +1)
    var ans = 1
    // 지금까지 순회한 동평 중에 가장 높은 값
    var highestPeer = 0

    for score in sorted {
        // 완호가 어떤 사람보다 두 점수 모두 떨어지는 경우
        if score[0] > wanho[0] && score[1] > wanho[1] {
            return -1 // 완호 인센티브 없음
        }

        // 최대 동평값을 업데이트 = 인센티브 받을 수 있음
        if highestPeer <= score[1] {
            highestPeer = score[1]
            // 인센티브를 받은 사람 중에서 완호보다 총점이 높은 경우
            if score.reduce(0, +) > wanhoScore {
                ans += 1 // 완호 순위 밀림
            }
        }
    }

    return ans
}