BOJ 백준 2529: 부등호

Table of contents

들어가며

걸린 시간: 40분

사실 처음에 문제를 읽고, 백트래킹 문제인 걸 알았지만, 순열 최대 개수가 10!이어서, 오히려 실수할 여지를 주지 말고 쉽게 쉽게 가자해서 permutations 라이브러리를 써서 완전 탐색으로 구현하려 했습니다.

접근

그런데, 아직 원인 파악은 못했습니다.
계속 시간 초과가 뜨네요… (eval함수가 병목 구간이었습니다 ㅎㅎ) 그래서 아쉬운 대로 DFS + 백트래킹으로 구현했습니다!

구현

import sys
from itertools import permutations

input = sys.stdin.readline


def DFS(level, seq_str):
    global maxStr, minStr
    if level == K:
        seq_str_int = int(seq_str)
        if seq_str_int > int(maxStr):
            maxStr = seq_str
        if seq_str_int < int(minStr):
            minStr = seq_str
        return
    for i in range(10):
        if isUsed[i]:
            continue
        if not eval(f"{seq_str[-1]} {operators[level]} {i}"):
            continue
        isUsed[i] = True
        DFS(level + 1, seq_str + str(i))
        isUsed[i] = False


if __name__ == "__main__":
    K = int(input().strip())
    operators = [*input().strip().split()]
    nums = [*range(10)]
    isUsed = [False for _ in range(10)]
    maxStr = "0"
    minStr = "9999999999"
    for i in range(10):
        isUsed[i] = True
        DFS(0, str(i))
        isUsed[i] = False

    print(maxStr)
    print(minStr)

import sys
from itertools import permutations

input = sys.stdin.readline

def check(a, b, op):
    if op == "<":
        return a < b
    else:
        return a > b
if __name__ == "__main__":
    K = int(input().strip())
    operators = input().strip().split()

    maxSeqSum = 0
    minSeqSum = 9999999999
    maxSeq, minSeq = None, None
    seqCandsGen = permutations(range(10), K + 1)

    for candSeq in seqCandsGen:
        isValid = True
        for i, operator in enumerate(operators):
            if not check(candSeq[i], candSeq[i + 1], operator):
                isValid = False
                break

        if isValid:
            seqSum = 0
            factor = 1
            for idx in range(K, -1, -1):
                seqSum += candSeq[idx] * factor
                factor *= 10
            # print(f"seqSum: {seqSum}")
            if seqSum > maxSeqSum:
                maxSeq = candSeq
                maxSeqSum = seqSum
            if seqSum < minSeqSum:
                minSeq = candSeq
                minSeqSum = seqSum
            # print(f"minSeq: {minSeq}")

    # print(maxSeq, minSeq)
    print("".join(map(str, maxSeq)))
    print("".join(map(str, minSeq)))