반응형

문제 출처 :


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



알고리즘 분석 :


문제 해결에 필요한 사항

1. map


이 문제는 정말 많이 고민한 문제이다.


시작점으로 시작하는 값은 맵에 넣어주고 최대 높이를 갱신해준다.


반복을 해준다.


반복을 해준다. 이때 최대 높이가 갱신된다.


첫 기둥의 끝점이 나타날 때이다.


이때는 내가보고있는 기둥의 시작점을 우선 지우고, 기둥의 높이와 최대높이가 다르면 정답을 가지는 맵에 추가해준다.




두번째 기둥의 시작점을 지우고 끝점이 높이가 최대 높이와 다르니 맵에 추가한다.



이제 정답을 담은 맵에서는 모든 값을 출력하되, 이전값과 같은 값이 맵에 담겨있다면 출력하지 않는다.


이렇게 하면 정답을 구할 수 있다.


아래 주석을 통해 좀 더 자세히 기록해두었다.






소스 코드 : 


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
#include <iostream>
#include <cstdio>
#include <map>
#include <vector>
#include <algorithm>
#include <functional>
#include <queue>
 
using namespace std;
 
typedef pair<intint> pii;
 
vector<pair<pii, pii> > vc;
 
map<pii, int, greater<> > st;
 
map<intint> mp;
 
int main()
{
    int n;
    scanf("%d"&n);
 
    // vector에는 현재 점, 높이, 반대편점, 상태를 받는다.
    // 0 :: 현재 점이 사각형 시작 1 :: 현재 점이 사각형 끝
    for (int i = 0; i < n; i++)
    {
        int s, e, height;
        scanf("%d %d %d"&s, &height, &e);
 
        vc.push_back({ {s,height }, { e, } });
        vc.push_back({ {e,height }, { s, } });
    }
 
    // x좌표에 대해 정렬
    sort(vc.begin(), vc.end());
 
    // 이전의 최고 높이
    int prev = -1;
    st[{00}] = 0;
 
    for (int i = 0; i < vc.size(); i++)
    {
        int here = vc[i].first.first;
        int other = vc[i].second.first;
        int height = vc[i].first.second;
        int pos = vc[i].second.second;
 
        // 만약 현재 점이 시작이라면 맵에 그대로 넣는다.
        if (pos == 0)
            st[{height, here}] = other;
 
        // 시작점이 아닌 끝점이라면 시작점을 찾아 삭제한다.
        else {
            auto it = st.find({ height, other });
            st.erase(it);
        }
 
        // 지금 맵에 남아있는 높이 최대를 찾는다.
        auto it = st.begin();
        int maxH = it->first.first;
 
        // 내가 알고있던 이전 최대 높이와 다르다면
        if (maxH != prev)
        {
            // 최대 높이 갱신
            prev = maxH;
 
            // 만약 시작점이라면 최대 갱신
            if (pos == 0)
                mp[here] = max(mp[here], maxH);
 
            // 만약 끝점이라면
            else {
                // 아직 표시된 적이없다면 최대값으로 갱신
                if (mp.count(here) == 0)
                    mp[here] = maxH;
                // 표시된 적이 있다면 최솟값으로 갱신
                else
                    mp[here] = min(mp[here], maxH);
            }
        }
    }
 
    prev = -1;
    for (auto it = mp.begin(); it != mp.end(); it++) {
        if (it->second != prev)
            printf("%d %d ", it->first, it->second);
        prev = it->second;
    }
    return 0;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>
Crocus

반응형

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

[13326번] Diameter  (0) 2018.06.21
[15729번] 방탈출  (0) 2018.05.22
[14915번] 진수 변환기  (0) 2018.05.08
[14911번] 궁합 쌍 찾기  (0) 2018.05.07
[10174번] 팰린드롬  (2) 2018.05.04