[BOJ] 2529 부등호

문제

두 종류의 부등호 기호 ‘<’와 ‘>’가 k개 나열된 순서열  A가 있다. 우리는 이 부등호 기호 앞뒤에 서로 다른 한 자릿수 숫자를 넣어서 모든 부등호 관계를 만족시키려고 한다. 예를 들어, 제시된 부등호 순서열 A가 다음과 같다고 하자. 

A =>  < < < > < < > < >

부등호 기호 앞뒤에 넣을 수 있는 숫자는 0부터 9까지의 정수이며 선택된 숫자는 모두 달라야 한다. 아래는 부등호 순서열 A를 만족시키는 한 예이다. 

3 < 4 < 5 < 6 > 1 < 2 < 8 > 7 < 9 > 0

이 상황에서 부등호 기호를 제거한 뒤, 숫자를 모두 붙이면 하나의 수를 만들 수 있는데 이 수를 주어진 부등호 관계를 만족시키는 정수라고 한다. 그런데 주어진 부등호 관계를 만족하는 정수는 하나 이상 존재한다. 예를 들어 3456128790 뿐만 아니라 5689023174도 아래와 같이 부등호 관계 A를 만족시킨다. 

5 < 6 < 8 < 9 > 0 < 2 < 3 > 1 < 7 > 4

여러분은 제시된 k개의 부등호 순서를 만족하는 (k+1)자리의 정수 중에서 최댓값과 최솟값을 찾아야 한다. 앞서 설명한 대로 각 부등호의 앞뒤에 들어가는 숫자는 { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 }중에서 선택해야 하며 선택된 숫자는 모두 달라야 한다.

입력

첫 줄에 부등호 문자의 개수를 나타내는 정수 k가 주어진다. 그 다음 줄에는 k개의 부등호 기호가 하나의 공백을 두고 한 줄에 모두 제시된다. k의 범위는 2 ≤ k ≤ 9 이다. 

출력

여러분은 제시된 부등호 관계를 만족하는 k+1 자리의 최대, 최소 정수를 첫째 줄과 둘째 줄에 각각 출력해야 한다. 단 아래 예(1)과 같이 첫 자리가 0인 경우도 정수에 포함되어야 한다. 모든 입력에 답은 항상 존재하며 출력 정수는 하나의 문자열이 되도록 해야 한다. 

 

 

 

분명히 위상정렬 카테고리를 보고 들어왔는데, 전혀 상관없어 보이는 문제가 등장해서 당황했다.

 

그래서 몇번 고민하다가 어떻게 위상정렬로 푸는지에 대한 힌드를 얻기위해서 힌트를 보았다.

 

풀이는 간단했다. 

 

>, < 부등호를 이용해 "간선"을 만들어주는 것이었다.

 

최소값 찾을떄는 0부터9 까지 차례대로 pop하며배치,

A<B 일때는 0<1 이렇게 넣어야 하므로 A->B간선

A>B 일때는 1>0 이렇게 넣어야 하므로 A<-B간선

최대값 찾을떄는 9부터0 까지 차례대로 pop하며배치,

A<B 일때는 8<9 이렇게 넣어야 하므로 A<-B간선

A>B 일때는 9>8 이렇게 넣어야 하므로 A->B간선

 

으로, 기존 위상정렬 방법에서 조금만 더 응용하면 되었었다.

 

import sys
import heapq
input = sys.stdin.readline

n = int(input().rstrip())
s = input().rstrip().split(" ")


def solve(findMin):
    global n, s

    # 간선 저장
    graph = dict()
    for i in range(n+1):
        graph[i] = []

    # inDegree 저장
    # inDegree[2] 는 ?->2인 간선의 개수를 뜻함
    inDegree = [0] * (n+1)

    if(findMin):
        '''
        최소값 찾을떄는 0부터9 까지 차례대로 pop하며배치,
        A<B 일때는 0<1 이렇게 넣어야 하므로 A->B간선
        A>B 일때는 1>0 이렇게 넣어야 하므로 A<-B간선
        '''

        for i, _s in enumerate(s):
            if(_s == "<"):
                graph[i].append(i+1)
                inDegree[i+1] += 1
            else:
                graph[i+1].append(i)
                inDegree[i] += 1
    else:
        '''
        최대값 찾을떄는 9부터0 까지 차례대로 pop하며배치,
        A<B 일때는 8<9 이렇게 넣어야 하므로 A<-B간선
        A>B 일때는 9>8 이렇게 넣어야 하므로 A->B간선
        '''

        for i, _s in enumerate(s):
            if(_s == "<"):
                graph[i+1].append(i)
                inDegree[i] += 1
            else:
                graph[i].append(i+1)
                inDegree[i+1] += 1

    # print(inDegree)
    # print(graph)
    q = []

    for i in range(n+1):
        # 0인것부터 왼쪽큐에넣는다
        if(inDegree[i] == 0):
            heapq.heappush(q, i)
            # 해당 indegree의 차수를 낮추어 다음 비교에 포함안되도록 한다.
            inDegree[i] -= 1

    # 최소값구하려면 0~9넣어야하므로 거꾸로 pop하기위해서 뒤집기
    arr = sorted(range(10), reverse=findMin)

    answer = [-1] * (n+1)
    while(len(q) != 0):

        # 오는 간선이 없는 노드를 1개 뽑는다.
        i = heapq.heappop(q)

        # 적절한 위치에 숫자를 순서대로 넣는다
        answer[i] = arr.pop()

        # 노드 사라졌으므로 i의 목적지에 해당하는 간선을 1개씩 없애준다
        for g in graph[i]:
            inDegree[g] -= 1

        for j in range(n+1):
            # 0인것부터 왼쪽큐에넣는다
            if(inDegree[j] == 0):

                heapq.heappush(q, j)
                # 해당 indegree의 차수를 낮추어 다음 비교에 포함안되도록 한다.
                inDegree[j] -= 1

    print("".join(map(str, answer)))


solve(False)
solve(True)