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

문제 요약

A팀의 출전 순서는 이미 정해져 있고, B팀은 출전 순서를 자유롭게 정할 수 있다.

B팀 선수가 A팀 선수보다 큰 숫자를 낼 때만 1점을 얻는다. B팀이 얻을 수 있는 최대 승점을 구한다.

핵심 아이디어

실제 출전 순서보다 어떤 숫자가 어떤 숫자를 이기는지가 중요하다. 따라서 A와 B를 모두 오름차순 정렬한다.

B의 작은 숫자부터 확인하면서, 아직 이기지 않은 A 숫자 중 가장 작은 숫자를 이길 수 있는지 확인한다.

• B의 숫자 > A의 가장 작은 미매칭 숫자: 이 A 선수를 이기고 승점을 얻는다.
• 그렇지 않다: 이 B 선수는 어떤 남은 A 선수도 이길 수 없으므로 승점 없이 넘긴다.

이길 수 있는 B 선수를 더 큰 A 숫자에 쓰면 더 작은 A 숫자를 이길 기회를 잃을 수 있다. 따라서 가능한 가장 작은 A 숫자와 매칭하는 선택이 항상 최적이다.

풀이 과정

1. A와 B를 오름차순 정렬한다.
2. A에서 아직 이기지 않은 가장 작은 숫자의 인덱스를 a_index로 둔다.
3. 정렬된 B를 앞에서부터 확인한다.
4. 현재 B 숫자가 A[a_index]보다 크면 승점을 1 늘리고 a_index를 다음 A 선수로 옮긴다.
5. 모든 B 선수를 확인한 뒤 승점을 반환한다.

Python 코드

def solution(A, B):
    A.sort()
    B.sort()

    score = 0
    a_index = 0

    for b_number in B:
        # 현재 B 선수가 가장 작은 미매칭 A 선수를 이길 수 있다.
        if a_index < len(A) and b_number > A[a_index]:
            score += 1
            a_index += 1

    return score

예시

A = [5, 1, 3, 7] -> [1, 3, 5, 7]
B = [2, 2, 6, 8] -> [2, 2, 6, 8]

B 숫자	이길 A 숫자	승점
2	1	1
2	이길 수 없음	1
6	3	2
8	5	3

따라서 B팀은 최대 3점을 얻는다.

시간 복잡도

N을 팀 인원 수라고 하자.

• A, B 정렬: O(N log N)

• B 배열 순회: O(N)

• 시간 복잡도: O(N log N)

• 공간 복잡도: 정렬 구현에 따라 O(N)

정리

이길 수 있는 B 숫자는 남은 A 숫자 중 가장 작은 수를 이기는 데 사용한다. 이 단순한 그리디 기준을 정렬된 두 배열에 적용하면 B팀의 최대 승점을 구할 수 있다.