BOJ - 부등호(2529)

실버1 : 그리디 문제이다.

풀이

처음에 부르트 포스로 접근했다가, 시간초과가 났다. 그래서 그리디로 방향을 전향했다. >가 나왔을 때, 가장 큰 숫자를 설정해두고, 이하 부터 순서대로 이숫자를 채우는 것으로 해당 조건을 만족시킬 수 있다.

Code

import sys
from itertools import permutations
 
input = sys.stdin.readline
 
n = int(input())
operator_list = input().split()
ans = ""
count = 0
top = 9
for operator in operator_list:
    if operator == ">":
        for i in range(top - count, top + 1):
            ans += str(i)
        top = top - count - 1
        count = 0
    else:
        count += 1
for i in range(top - count, top + 1):
    ans += str(i)
top = top - count - 1
count = 0
print(ans)
 
ans = ""
count = 0
top = 0
for operator in operator_list:
    if operator == "<":
        for i in range(top + count, top - 1, -1):
            ans += str(i)
        top = top + count + 1
        count = 0
    else:
        count += 1
for i in range(top + count, top - 1, -1):
    ans += str(i)
top = top + count + 1
count = 0
print(ans)

Reference

• 백준(2529번) - 부등호