[Python] 백준 2529번 - 부등호

문제 https://www.acmicpc.net/problem/2529

2529번: 부등호

 

permutation 함수를 사용해서 모든 경우를 다 확인하였다.

최근에 브루트포스 문제를 풀고 있었는데 감이 잘 잡히지 않아서 순열, 조합 함수를 직접 만들어보지는 못하더라도 일단 라이브러리라도 써서 문제를 풀어보자 라는 마음가짐이었다.

그래서 어찌저찌 permutations 라이브러리를 사용해서 코드를 만들기는 했다.

딱 봐도 시간초과 날 것 같아서 pypy3로 제출했는데 5분 동안 기다리는 중이었다. ㅋㅋㅋㅋ

근데 제출 결과 시간 초과는 안 나고 맞았다고 떴다. 이유는 모르겠다... 그치만 일단 라이브러리 써서라도 풀긴 했다는 점..

 

구글링해서 다른 사람들 풀이를 봤는데 대부분 다 비슷한 방법으로 풀었길래 그 방식을 이해해보려 직접 따라해보았다.

디버깅하면서 차근차근 봐서 코드 이해는 했다. 이제 앞으로 나도 이렇게 할 수 있게끔 노력해야겠지.. 재귀 써서 푸는 방식을 연습해야 할 것 같다.

 

#채점하는데 5분 걸림. 시간초과는 안 남...뭘까
import sys
from itertools import permutations
input = sys.stdin.readline

k = int(input())
oper = list(input().split())
num = ["0", "1", "2", "3", "4", "5", "6", "7", "8", "9"]
ans = []

perm = permutations(num, k+1)
for i in perm:
    for j in range(k):
        bk = 0
        if oper[j] == ">":
            if int(i[j]) < int(i[j+1]):
                bk = 1 #break.. 판별
                break
        if oper[j] == "<":
            if int(i[j]) > int(i[j+1]):
                bk = 1
                break
    if bk == 1:
        continue
    ans.append(i)

print(''.join(max(ans)))
print(''.join(min(ans)))

 

# 다른 사람들 풀이 기반
import sys
input = sys.stdin.readline

def possible(i, j, op):
    if op == "<":
        return i < j
    if op == ">":
        return i > j
    return True

def answer(cnt, s):
    global max_ans, min_ans
    if cnt == k + 1:
        if len(min_ans) == 0:
            min_ans = s
        else:
            max_ans = s
        return
    for i in range(len(num)):
        if not num[i]:
            if cnt == 0 or possible(s[-1], str(i), oper[cnt-1]):
                num[i] = 1
                answer(cnt+1, s + str(i))
                num[i] = 0

k = int(input())
oper = list(input().split())
num = [0] * 10 #0~9
max_ans = ''
min_ans = ''

answer(0, "")
print(max_ans)
print(min_ans)

 

ㅋㅋㅋㅋㅋpermutations 메모리 12만... ㅋㅋㅋㅋ