[백준 문제] 2529번 부등호 (파이썬)
내 풀이 문제점
- 문제점 : 리스트에 순열을 다 넣어 버리면 그냥 시간초과가 나온다.
- 다른 팀원들 풀이 방법 : DFS로 순열 구하는 방법 / 재귀로 푸는 방법
- 다른 답안 : 다음 순열을 구하는 함수를 만드는 방법
내 코드와 다른 사람 코드 다른점
- if와 else로 모호하게 쓰긴 보단 if와 if로 쓰는 것이 보기 좋아 보인다.
- while True 같은 경우, 계속 돌아가는거니까 break절로 멈추는 식으로 짜보자.
- if절에 함수르 돌리면 돌아가는구나
- print(‘‘.join(map(str,big))) 프린트할때, 이거 애용하자.
내 풀이 (시간 초과)
import itertools
k = int(input())
ineq = list(map(str, input().split()))
all_lst = [str(i) for i in range(0,10)]
perm = list(itertools.permutations(all_lst, k+1))
for x in perm :
x = list(x)
is_possi = True
for i in range(k) :
if ineq[i] == '>' :
if int(x[i]) > int(x[i+1]) :
is_possi = is_possi & True
else :
is_possi = is_possi & False
else :
if int(x[i]) < int(x[i+1]) :
is_possi = is_possi & True
else :
is_possi = is_possi & False
if is_possi is True :
ans1 = x
break
for x in reversed(perm) :
x = list(x)
is_possi = True
for i in range(k) :
if ineq[i] == '>' :
if int(x[i]) > int(x[i+1]) :
is_possi = is_possi & True
else :
is_possi = is_possi & False
else :
if int(x[i]) < int(x[i+1]) :
is_possi = is_possi & True
else :
is_possi = is_possi & False
if is_possi is True :
ans2 = x
break
for i in range(k + 1):
print(ans1[i], end='')
print()
for i in range(k + 1):
print(ans2[i], end='')
다른 답안 풀이
def next_perm(a):
i = len(a)-1
while i > 0 and a[i-1] >= a[i]:
i -= 1
if i <= 0:
return False
j = len(a)-1
while a[j] <= a[i-1]:
j -= 1
a[i-1],a[j] = a[j],a[i-1]
j = len(a)-1
while i < j:
a[i],a[j] = a[j],a[i]
i += 1
j -= 1
return True
def prev_perm(a):
i = len(a)-1
while i > 0 and a[i-1] <= a[i]:
i -= 1
if i <= 0:
return False
j = len(a)-1
while a[j] >= a[i-1]:
j -= 1
a[i-1],a[j] = a[j],a[i-1]
j = len(a)-1
while i < j:
a[i],a[j] = a[j],a[i]
i += 1
j -= 1
return True
def check(perm, a):
for i in range(len(a)):
if a[i] == '<' and perm[i] > perm[i+1]:
return False
if a[i] == '>' and perm[i] < perm[i+1]:
return False
return True
k = int(input())
a = input().split()
small = [i for i in range(k+1)]
big = [9-i for i in range(k+1)]
while True:
if check(small,a):
break
if not next_perm(small):
break
while True:
if check(big, a):
break
if not prev_perm(big):
break
print(''.join(map(str,big)))
print(''.join(map(str,small)))
