반응형

문제 출처 :


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



알고리즘 분석 :


문제 해결에 필요한 사항

1. 위상 정렬 :: http://www.crocus.co.kr/716

2. 우선순위 큐


별로 추천하고 싶지 않은 방식이지만, 값이  2 <= k <= 10이기에 해결가능한 코드이다.


알고리즘은 다음과 같다.


두개의 위상정렬을 이용하는데


첫번째 max로 적힌 위상 정렬은 오름차순으로 큐에서 뽑아내어 위상 정렬을 하고

두번째 min으로 적힌 위상 정렬은 내림차순으로 큐에서 뽑아내어 위상 정렬을 하는 방법이다.



위의 사진을 보면 1에 2와 0으로 들어오냐, 0과 2로 들어오냐의 차이가 존재한다.


0번째 위치는 1번째 위치에 상속되므로 line(indegree)가 1이고

1번째 위치는 0,2번째 위치보다 우선순위 이므로 line가 0이고

2번재 위치는 1번째 위치에 상속되므로 line이 1이다.


1번째 위치의 벡터 값을 보면 2, 0이냐 0, 2이냐에 따라 


정답이 7 9 8이 나올지, 8 9 7이 나올지 달라진다.


따라서 이 과정을 이용하여


max를 구할 때는 우선순위 큐를 최소 힙으로 구현하고

min을 구할 때는 우선순위 큐를 최대 힙으로 구현한다.





소스 코드 : 


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
#include <iostream>
#include <cstdio>
#include <vector>
#include <queue>
#include <algorithm>
#include <functional>
 
using namespace std;
 
int arr[11];
 
int lineMax[11];
int resultMax[11];
int cntMax[10];
vector<int> vcMax[11];
 
int lineMin[11];
int resultMin[11];
int cntMin[10];
vector<int> vcMin[11];
 
int main()
{
    int n;
    scanf("%d", &n);
 
    // 위상 정렬을 위해 정보 입력
    getchar();
    for (int i = 0; i < n; i++)
    {
        char ch;
        scanf("%c", &ch);
        getchar();
        int prev = i;
        int cur = i + 1;
 
        if (ch == '<')
        {
            // max, min 값을 위해 따로 저장한다.
            lineMax[prev]++;
            vcMax[cur].push_back(prev);
 
            lineMin[prev]++;
            vcMin[cur].push_back(prev);
        }
 
        else if (ch == '>')
        {
            // max, min 값을 위해 따로 저장한다.
            lineMax[cur]++;
            vcMax[prev].push_back(cur);
 
            lineMin[cur]++;
            vcMin[prev].push_back(cur);
        }
    }
 
    // max를 구하기위한 pq
    priority_queue<int, vector<int>, greater<int>> qMax;
 
    for (int i = 0; i < n + 1; i++)
        if (lineMax[i] == 0)
            qMax.push(i);
 
    for (int i = 0; i < n + 1; i++)
    {
        int here = qMax.top();
        qMax.pop();
 
        resultMax[i] = here;
 
        for (int j = 0; j < vcMax[here].size(); j++)
        {
            int there = vcMax[here][j];
            if (--lineMax[there] == 0)
                qMax.push(there);
        }
    }
 
    // min을 구하기 위한 pq
    priority_queue<int, vector<int>, less<int>> qMin;
 
    for (int i = 0; i < n + 1; i++)
        if (lineMin[i] == 0)
            qMin.push(i);
 
    for (int i = 0; i < n + 1; i++)
    {
        int here = qMin.top();
        qMin.pop();
 
        resultMin[i] = here;
 
        for (int j = 0; j < vcMin[here].size(); j++)
        {
            int there = vcMin[here][j];
            if (--lineMin[there] == 0)
                qMin.push(there);
        }
    }
 
    // 출력 코드
    int ans = 9;
 
    // 자신의 위치에 ans를 넣어준다.
    for (int i = 0; i < n + 1; i++)
    {
        cntMax[resultMax[i]] = ans;
        ans--;
    }
 
    for (int i = 0; i < n + 1; i++)
        printf("%d", cntMax[i]);
    
    printf("\n");
    
    ans = n;
 
    // 자신의 위치에 ans를 넣어준다.
    for (int i = 0; i < n + 1; i++)
    {
        cntMin[resultMin[i]] = ans;
        ans--;
    }
 
    for (int i = 0; i < n + 1; i++)
        printf("%d", cntMin[i]);
 
    return 0;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>
Crocus


반응형
저작자표시 비영리 변경금지

'Applied > 알고리즘 문제풀이' 카테고리의 다른 글

[1922번] 네트워크 연결  (0) 2017.04.03
[1197번] 최소 스패닝 트리  (2) 2017.04.03
[3665번] 최종 순위  (5) 2017.04.02
[1005번] ACM Craft  (5) 2017.04.02
[2637번] 장난감조립  (0) 2017.04.01

티스토리툴바