백준 - 부등호 / Silver 1 / 2529번 / Python

문제 📋

백준 - 부등호

초기 풀이 📝

import sys
from itertools import permutations
from collections import deque
from copy import deepcopy

k = int(sys.stdin.readline())
symbols = deque(sys.stdin.readline().split())
digits = [i for i in range(10)]
cases = list(map(deque, permutations(digits, len(symbols) + 1)))
max_val = '0'
min_val = "9999999999"

for case in cases:
    temp_symbols = deepcopy(symbols)
    temp_case = deepcopy(case)

    left = temp_case.popleft()
    exit_flag = False

    while temp_case:
        right = temp_case.popleft()
        symbol = temp_symbols.popleft()

        if symbol == '<' and left > right:
            exit_flag = True
            break
        elif symbol == '>' and left < right:
            exit_flag = True
            break

        left = right

    if exit_flag:
        continue

    num = ''.join(map(str, case))

    if num > max_val:
        max_val = num
    if num < min_val:
        min_val = num

print(max_val)
print(min_val)

문제 자체는 간단한 완전탐색 문제였다.
부등호의 수가 최대 9개이고 그 사이에 최대 10개의 숫자들을 배열하는 시나리오이다.

따라서 순열을 활용하면 최대 10!의 경우의 수가 나오는데
그중에서 부등호 조건을 만족하는 case들을 구하고
해당 case들의 숫자를 이어붙여서 최대, 최솟값을 구하는 문제이다.

처음에 생각했을때 숫자가 부등호가 같은 for문으로 순회하기 번거롭다고 생각하여
deque를 활용하여 문제를 풀었다.
왜냐하면 시간복잡도를 계산했을때 문제가 없을 것을 확인했기 때문이다

그러나 문제는 공간복잡도에서 발생하여 메모리 초과로 풀이에 실패하게 되었다.

for case in cases:
    temp_symbols = deepcopy(symbols)
    temp_case = deepcopy(case)

첫번째 원인은 반복문내에서 deepcopy() 함수를 계속 호출하여 메모리를 새로 할당했기 때문이었다.
cases 배열의 길이는 최대 10! 즉, 360만 정도가 된다.
따라서 배열 길이가 10정도 되는 배열을 360만번 메모리를 할당하고 있는 것이다.
하지만 해당 문제를 해결하였지만 여전히 메모리 초과는 해결되지 않았다.

cases = list(map(deque, permutations(digits, len(symbols) + 1)))

두번째 원인은 해당 코드에서 permutaions 함수가 반환하는 튜플들을 deque로 변환하면서 발생하는 문제였다.
해당 상황에서도 마찬가지로 최대 약 360만의 튜플들을 deque로 변환하면서 새로운 메모리를 너무 많이 할당하고 있었다.

개선된 풀이 📝

import sys
from itertools import permutations


k = int(sys.stdin.readline())
symbols = sys.stdin.readline().split()  # 부등호 리스트
digits = [i for i in range(10)]
cases = list(permutations(digits, len(symbols)+1))  # 가능한 케이스들을 순열을 이용해 구함
max_val = '0'
min_val = "9999999999"

for case in cases:

    left = case[0]
    exit_flag = False

    for i in range(len(symbols)):
        right = case[i+1]
        symbol = symbols[i]

        if symbol == '<' and left > right:
            exit_flag = True
            break
        elif symbol == '>' and left < right:
            exit_flag = True
            break

        left = right

    if exit_flag:  # 부등호 조건에 안맞으면 넘김
        continue

    num = ''.join(map(str, case))

    if num > max_val:  # 조건을 통과한 수들 중 최대, 최솟값을 구함
        max_val = num
    if num < min_val:
        min_val = num

print(max_val)
print(min_val)

위에서 확인한 모든 이슈들을 해결하고 난 최종코드이다.
조금만 고민해보면 부등호와 숫자들을 같이 순회할 수 있었고
따라서 추가적인 자료구조를 사용하여 불필요한 메모리를 사용할 필요가 없었다.

앞으로 시간복잡도에 문제가 없다고해서 아무생각없이 자료구조를 변환하기보단
메모리 부분도 생각하며 코드를 짜야겠다.