[Python] 백준 2923번: 숫자 게임

https://www.acmicpc.net/problem/2923

2923번: 숫자 게임

 

 

Pypy3로 맞은 사람이 총 6명이긴 하지만 그 중에 시간복잡도와 공간복잡도가 마지막 등수인 풀이입니다.(참고로 Python으로 통과한 사람은 1명도 없습니다.) 이 점 참고해주시길 바랍니다.

 

 

import sys
input = sys.stdin.readline


def getMinMaxSum():
    # a, b를 변형시키고 다시 원상복구하기 위함
    originalA = [a[i] for i in range(101)]
    originalB = [b[i] for i in range(101)]

    ai, bi = getNotZeroIndex(a, 1, False), getNotZeroIndex(b, 100, True)
    minVar = min(a[ai], b[bi])
    a[ai] -= minVar
    b[bi] -= minVar

    minMaxSum = 0
    while ai != -1 and bi != -1:
        minMaxSum = max(minMaxSum, ai + bi)

        ai, bi = getNotZeroIndex(
            a, ai, False), getNotZeroIndex(b, bi, True)
        minVar = min(a[ai], b[bi])
        a[ai] -= minVar
        b[bi] -= minVar

    # a, b 원상복구
    for i in range(1, 101):
        a[i] = originalA[i]
        b[i] = originalB[i]

    return minMaxSum


# 0이 아닌 다음 인덱스 반환
def getNotZeroIndex(nums, startIndex, isReversed):
    if isReversed == False:
        for i in range(startIndex, 101):
            if nums[i] >= 1:
                return i
    else:
        for i in range(startIndex, 0, -1):
            if nums[i] >= 1:
                return i

    return -1


if __name__ == '__main__':
    N = int(input())

    a = [0]*101
    b = [0]*101

    for _ in range(N):
        ai, bi = map(int, input().split())
        a[ai] += 1
        b[bi] += 1

        minMaxSum = getMinMaxSum()
        print(minMaxSum)

 

우선 입력 범위가 1~100으로 매우 작으므로 a, b라는 리스트에 카운트하는 식으로 입력 정보를 처리하였다. 이후에 현재까지 입력받은 정보를 토대로 getMinMaxSum()을 통해 값을 받고 출력해주는 것이 가장 큰 틀이다.

 

getMinMaxSum()을 설명하기에 앞서, 가장 큰 값에서 최솟값을 구하려면, 각 값들을 정렬한 후 양극의 값들을 더해주고 여기에서 최솟값을 구해주면 된다. 가령 예제 입력 1의 경우에는,

1 1

2 4

3 8

처럼 정렬해주고, (1, 8), (2, 4), (3, 1)과 같이 묶어주면 된다는 것이다. 이것을 토대로 해당 함수를 설명하겠다.

우선 a, b의 값을 변경할 예정인데, 함수가 끝나기 전에 a, b를 원래 상태로 복구하기 위한 리스트가 originalA, B이다.

이후에 ai, bi를 getNotZeroIndex()를 통해 초기화시켜준다. getNotZeroIndex(nums, startIndex, isReversed)는 startIndex부터 시작해서 nums가 1 이상인 인덱스를 반환하는 함수이고, isReversed에 따라 for문의 진행 방향이 달라진다. 즉, 각각 1, 100부터 시작해서 a, b에서 처음으로 0이 아닌 인덱스를 가져오겠다는 뜻이다.

그리고 minVar로 각 인덱스에서의 최솟값을 담아서 a, b, modifyInfoA, B에 대입시켜주는데, 1이 아니라 minVar을 사용하는 이유는 시간복잡도를 위해서이다. 이렇게 하지 않고 1로 처리해주면 시간 초과가 나온다. 아래의 예시를 보자.

4

1 4

1 4

1 4

2 4

해당 케이스의 경우, a, b가 아래와 같은 순서로 바뀌게 된다.

 

이런 방식의 연산을 while문 안에 넣고, ai, bi를 각각 증가, 감소시키면서 minMaxSum의 값을 갱신시켜주면 우리가 찾는 값이 나온다.

a, b를 원상복구 시켜주고 minMaxSum을 반환해주면 된다.