프로그래머스

프로그래머스 숫자 게임 풀이: 정렬과 그리디 매칭

작성·코드 검증: solve together · 작성 언어: Python

0. 문제 링크와 출처

  • 문제: 숫자 게임
  • 출처: 프로그래머스, Summer/Winter Coding(~2018)
  • 자체 판단 난이도: Level 3

B팀은 A팀의 출전 순서를 미리 알고 있으므로, 자신의 숫자들을 원하는 순서로 배치할 수 있다. 매 경기마다 이길 수 있는 가장 작은 숫자를 선택하는 그리디 기준을 세우고, 정렬된 두 배열에서 사용한 숫자를 관리해야 하므로 Level 3으로 판단한다.

1. 문제 요약

A팀과 B팀에 각각 N개의 자연수가 주어진다. 모든 사원은 한 번씩 경기를 치르고, 각 경기에서 더 큰 숫자를 낸 팀이 1점을 얻는다. 같은 숫자라면 어느 팀도 점수를 얻지 못한다.

A팀의 출전 순서가 배열 A로 주어질 때, B팀은 배열 B의 원소를 원하는 순서로 배치해 얻을 수 있는 최대 승점을 구해야 한다. B팀 숫자는 반드시 A팀 숫자보다 커야 승리할 수 있다.

  • A, B의 길이는 같고 최대 100,000이다.
  • 각 숫자는 1 이상 1,000,000,000 이하다.
  • B팀의 숫자는 한 경기에서 한 번만 사용할 수 있다.

예를 들어 A = [5, 1, 3, 7], B = [2, 2, 6, 8]이면 B팀은 8, 2, 6, 2 순서로 출전해 세 경기를 이길 수 있다.

2. 문제 해결에 사용되는 알고리즘이나 자료구조 설명

그리디 선택 기준

A팀과 B팀의 숫자를 각각 오름차순으로 정렬한다. 가장 작은 A팀 숫자부터 확인하면서, 현재 숫자를 이길 수 있는 B팀의 숫자 중 가장 작은 것을 선택한다.

  • B팀의 현재 숫자가 A의 숫자보다 작거나 같으면 이 경기에서 이길 수 없으므로 버린다.
  • B팀의 현재 숫자가 더 크면 이 숫자로 승리하고 다음 B팀 숫자로 이동한다.

현재 A팀 숫자를 이길 수 있는 B팀 숫자 중 가장 작은 숫자를 사용하면, 더 큰 B팀 숫자를 아껴 둘 수 있다. 남은 A팀 숫자는 현재보다 크거나 같으므로, 작은 숫자로 이길 수 없는 상대는 이후에도 이길 수 없다.

이길 수 있는 가장 작은 수를 먼저 배정하기

B팀이 현재 A팀 숫자를 이길 수 있다면, 더 큰 B팀 숫자를 사용해도 얻는 점수는 동일하게 1점이다. 따라서 가장 작은 승리 숫자를 선택해야 이후 더 큰 A팀 숫자에 대응할 수 있는 큰 숫자를 보존할 수 있다.

반대로 B팀의 가장 작은 남은 숫자가 현재 A팀 숫자보다 작거나 같다면, 이 숫자는 현재 상대도 이기지 못하고 앞으로 확인할 더 큰 A팀 숫자도 이길 수 없다. 이 숫자를 버리는 것은 어떤 승리 기회도 잃지 않는다.

그리디 선택이 안전한 이유

현재 가장 작은 A팀 숫자를 a, 이를 이길 수 있는 가장 작은 B팀 숫자를 b라고 하자. 어떤 최적 배치가 a를 더 큰 숫자 c로 이기고 있었다고 해도 b와 c를 바꿀 수 있다.

  • b가 사용되지 않았다면 a에 b를 배치해 같은 승점을 유지할 수 있다.
  • b가 다른 A팀 숫자 a'를 이기고 있었다면, c는 b보다 크므로 a'도 계속 이긴다. 따라서 a에는 b, a'에는 c를 배치해 승점 수를 유지할 수 있다.

이 교환이 가능하므로 현재 A팀 숫자에 가장 작은 승리 숫자를 선택해도 최적해를 잃지 않는다.

오답 접근과 반례

각 A팀 숫자에 대해 항상 B팀의 최댓값을 배치하면 당장 이길 수는 있지만 큰 숫자를 낭비하게 된다.

A = [1, 2]
B = [2, 3]

첫 번째 A팀 숫자 1에 B팀의 최댓값 3을 사용하면 남은 2로는 A팀의 2를 이길 수 없어 1점만 얻는다. 반면 1에는 2, 2에는 3을 배치하면 2점이다. 이 문제에서는 이길 수 있는 가장 작은 B팀 숫자를 선택해야 한다.

숫자가 같을 때는 승리하지 못한다. A = [2], B = [2]에서는 B[0] > A[0]가 아니므로 정답은 0이다.

시간·공간 복잡도

두 배열을 정렬하는 데 O(n log n) 시간이 필요하고, 정렬된 배열을 한 번 순회하는 데 O(n) 시간이 필요하다. 따라서 전체 시간 복잡도는 O(n log n)이다.

코드에서는 두 배열을 제자리 정렬하고 인덱스 하나만 추가로 사용하므로 알고리즘 관점의 추가 공간은 O(1)이다. 다만 Python의 내부 정렬 구현은 정렬 과정에서 입력 크기에 비례하는 보조 메모리를 사용할 수 있다.

3. 문제 해결 코드 (Python)

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

    score = 0
    b_index = 0

    for a_value in A:
        while b_index < len(B) and B[b_index] <= a_value:
            b_index += 1

        if b_index == len(B):
            break

        score += 1
        b_index += 1

    return score

A를 작은 값부터 확인하고 B도 작은 값부터 순서대로 확인한다. B[b_index]가 현재 A팀 숫자보다 작거나 같으면 승리할 수 없으므로 다음 B팀 숫자를 확인한다.

승리 가능한 숫자를 찾으면 점수를 1 증가시키고 해당 B팀 숫자를 사용 처리한다. 한 번 사용한 B팀 숫자는 b_index를 증가시켜 다시 사용하지 않는다.

복사해 실행할 테스트

아래 검사를 풀이 코드 아래에 붙여 python 파일명.py로 실행하면 이길 수 있는 상대를 순서대로 배정하는지 확인할 수 있다.

assert solution([5, 1, 3, 7], [2, 2, 6, 8]) == 3
assert solution([1, 1, 1], [1, 1, 1]) == 0

4. 공식 예제와 추가 검증

공식 예제와 경계 조건, 큰 입력을 Python 코드로 실행해 확인했다.

공식 예제

입력 기대 출력 확인 결과
A = [5, 1, 3, 7], B = [2, 2, 6, 8] 3 통과
A = [2, 2, 2, 2], B = [1, 1, 1, 1] 0 통과

추가 검증 1: 한 번 이길 수 있는 경우

입력: A = [1], B = [2]
기대 출력: 1
확인 결과: 통과
검증 목적: 최소 입력에서 B팀의 승리를 세는지 확인

추가 검증 2: 숫자가 같은 경우

입력: A = [1], B = [1]
기대 출력: 0
확인 결과: 통과
검증 목적: 같은 숫자를 승리로 계산하지 않는지 확인

추가 검증 3: 작은 승리 숫자를 먼저 사용하는 경우

입력: A = [1, 2], B = [2, 3]
기대 출력: 2
확인 결과: 통과
검증 목적: 큰 B팀 숫자를 아껴 두는 그리디 선택 확인

추가 검증 4: 제한에 가까운 입력

입력: A = [1, 2, 3, ..., 10000]
B = [2, 3, 4, ..., 10001]
기대 출력: 10000
확인 결과: 통과
검증 목적: 10,000개 원소를 정렬하고 모든 경기에서 승리하는지 확인

5. 다른 풀이 방식 검색 및 비교

B팀 숫자를 정렬한 뒤 현재 A팀 숫자를 이길 수 있는 가장 작은 값을 선택하는 방식은 사용 가능한 숫자를 효율적으로 보존한다. 다른 구현에서는 최대 힙이나 두 배열의 양끝을 사용할 수도 있지만, 숫자 범위와 승리 조건을 고려하면 오름차순 정렬과 단일 포인터만으로 충분히 구현할 수 있다.

마무리

숫자 게임은 모든 경기를 직접 배치해 보지 않고, 정렬을 통해 현재 상대를 이길 수 있는 가장 작은 B팀 숫자를 선택하는 그리디 문제다. 이 선택은 큰 숫자를 불필요하게 소모하지 않으며, 이길 수 없는 작은 숫자는 과감히 버려도 최적 승점에 영향을 주지 않는다. 정렬과 두 포인터를 이용하면 O(n log n) 시간에 최대 승점을 구할 수 있다.

#그리디#프로그래머스#난이도 3