반응형

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

 

17299번: 오등큰수

첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다.

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. stack이 비어있지 않고, cnt[ arr[ i ] ]의 값이 s.top보다 클 경우 s.pop을 해주고, s가 완전히 비기 전까지 반복해 줍니다.

 

2. NGF 배열을 만들고, 1의 s.pop 과정에서 NGF 배열의 해당 숫자의 idx  값을 arr[ i ]로 갱신합니다. 

 

3. s에 cnt[ arr[ i ] ]를 push 합니다.

 

4. NGF 배열을 출력합니다.

 

[ 소스코드 ]

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
#include<iostream>
#include<stack>
 
using namespace std;
 
int N;
int arr[1000000];
int cnt[1000001];
int NGF[1000000];
stack<pair<int, int>> s;
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> N;
 
    fill(NGF, NGF + N, -1);
 
    for (int i = 0; i < N; i++) {
        cin >> arr[i];
        cnt[arr[i]]++;
    }
 
    for (int i = 0; i < N; i++) {
        if (!s.empty()) {
            while (s.top().first < cnt[arr[i]]) {
                NGF[s.top().second] = arr[i];
                s.pop();
                if (s.empty()) break;
            }
        }
 
        s.push({ cnt[arr[i]], i });
    }
 
    for (int i = 0; i < N; i++) {
        cout << NGF[i] << ' ';
    }
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

'백준' 카테고리의 다른 글

[ 백준 ] 20210번 - 파일 탐색기 (C++)  (1) 2023.10.08
[ 백준 ] 20120번 - 호반우와 리듬게임 (C++)  (1) 2023.10.07
[ 백준 ] 2186번 - 문자판 (C++)  (1) 2023.10.05
[ 백준 ] 2661번 - 좋은수열 (C++)  (1) 2023.10.04
[ 백준 ] 1461번 - 도서관 (C++)  (0) 2023.10.03
반응형

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

 

2800번: 괄호 제거

첫째 줄에 음이 아닌 정수로 이루어진 수식이 주어진다. 이 수식은 괄호가 올바르게 쳐져있다. 숫자, '+', '*', '-', '/', '(', ')'로만 이루어져 있다. 수식의 길이는 최대 200이고, 괄호 쌍은 적어도 1개

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. 수식을 입력받아 각 괄호에 번호를 붙입니다.

 

2. 조합을 이용하여 각 괄호들을 제거해주고, set 자료구조에 저장하여 중복을 제거해줍니다.

 

3. 저장된 답을 출력합니다.

 

[ 소스코드 ]

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
#include<iostream>
#include<string>
#include<stack>
#include<set>
 
using namespace std;
 
string str;
int arr[200];
set<string> ans;
int visited[11];
int cnt;
 
void dfs(int limit, int level, int num)
{
    if (level == limit) {
        string temp = "";
        for (int i = 0; i < str.size(); i++) {
            if (visited[arr[i]] != 1) {
                temp += str[i];
            }
        }
 
        ans.insert(temp);
        return;
    }
 
    for (int i = num; i <= cnt; i++) {
        visited[i] = 1;
        dfs(limit, level + 1, i + 1);
        visited[i] = 0;
    }
}
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> str;
    stack<int> s;
 
    for (int i = 0; i < str.size(); i++) {
        if (str[i] == '(') {
            cnt++;
            arr[i] = cnt;
            s.push(cnt);
        }
        else if (str[i] == ')') {
            arr[i] = s.top();
            s.pop();
        }
    }
 
    for (int i = 1; i <= cnt; i++) {
        dfs(i, 0, 1);
    }
 
    for (auto& next : ans) {
        cout << next << '\n';
    }
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

'백준' 카테고리의 다른 글

[ 백준 ] 7432번 - 디스크 트리 (C++)  (0) 2023.07.24
[ 백준 ] 16929번 - Two Dots (C++)  (0) 2023.07.23
[ 백준 ] 1990번 - 소수인팰린드롬(C++)  (0) 2023.07.21
[ 백준 ] 23326번 - 홍익 투어리스트 (C++)  (0) 2023.07.20
[ 백준 ] 21939번 - 문제 추천 시스템 Version 1 (C++)  (0) 2023.07.19
반응형

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

 

6198번: 옥상 정원 꾸미기

문제 도시에는 N개의 빌딩이 있다. 빌딩 관리인들은 매우 성실 하기 때문에, 다른 빌딩의 옥상 정원을 벤치마킹 하고 싶어한다. i번째 빌딩의 키가 hi이고, 모든 빌딩은 일렬로 서 있고 오른쪽으

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. stack이 비어있지 않고, 건물의 높이 h의 값이 stack.top보다 크거나 같을 경우 st.pop을 해주고, st이 완전히 비기 전까지 반복해줍니다.

 

2. cnt에 현재 st의 size를 더해줍니다. 이때, cnt의 최댓값이 약 32억이므로 자료형을 long long으로 선언해줍니다.

 

3. stack에 건물의 높이 h를 push합니다.

 

4. cnt를 출력합니다.

 

[ 소스코드 ]

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
#include<iostream>
#include<stack>
#define ll long long
 
using namespace std;
 
int N;
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> N;
 
    stack<int> st;
 
    ll cnt = 0;
 
    for (int i = 0; i < N; i++) {
        int h;
        cin >> h;
 
        if (i == 0) {
            st.push(h);
        }
        else {
            while (st.top() <= h) {
                st.pop();
                if (st.empty()) break;
            }
 
            cnt += st.size();
            st.push(h);
        }
    }
 
    cout << cnt;
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

'백준' 카테고리의 다른 글

[ 백준 ] 5430번 - AC (C++)  (0) 2023.07.09
[ 백준 ] 17298번 - 오큰수 (C++)  (0) 2023.07.08
[ 백준 ] 1456번 - 거의 소수 (C++)  (0) 2023.07.06
[ 백준 ] 1038번 - 감소하는 수 (C++)  (0) 2023.07.05
[ 백준 ] 11402번 - 이항 계수 4 (C++)  (0) 2023.07.04
반응형

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

 

1863번: 스카이라인 쉬운거

첫째 줄에 n이 주어진다. (1 ≤ n ≤ 50,000) 다음 n개의 줄에는 왼쪽부터 스카이라인을 보아 갈 때 스카이라인의 고도가 바뀌는 지점의 좌표 x와 y가 주어진다. (1 ≤ x ≤ 1,000,000. 0 ≤ y ≤ 500,000) 첫

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. stack이 비어있지 않고, stack.top의 값이 현재 값보다 클 경우 cnt++, s.pop을 해주고, 같을 경우는 s.pop만 해줍니다.

 

2. stack에 y를 push합니다.

 

3. 위 과정이 끝난 후 마지막에 1번 과정을 반복해줍니다.

 

4. cnt를 출력합니다.

 

[ 소스코드 ]

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
#include<iostream>
#include<stack>
 
using namespace std;
 
int n;
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> n;
 
    stack<int> s;
    int cnt = 0;
 
    for (int i = 0; i < n; i++) {
        int x, y;
        cin >> x >> y;
 
        while (!s.empty() && s.top() >= y) {
            if (s.top() != y) cnt++;
            s.pop();
        }
 
        s.push(y);
    }
 
    while (!s.empty() && s.top() >= 0) {
        if (s.top() != 0) cnt++;
        s.pop();
    }
 
    cout << cnt;
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

'백준' 카테고리의 다른 글

[ 백준 ] 17025번 - Icy Perimeter (C++)  (0) 2023.07.01
[ 백준 ] 8981번 - 입력숫자 (C++)  (0) 2023.06.30
[ 백준 ] 12869번 - 뮤탈리스크 (C++)  (0) 2023.06.28
[ 백준 ] 1707번 - 이분 그래프 (C++)  (0) 2023.06.27
[ 백준 ] 1963번 - 소수 경로 (C++)  (0) 2023.06.26
반응형

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

 

2493번: 탑

첫째 줄에 탑의 수를 나타내는 정수 N이 주어진다. N은 1 이상 500,000 이하이다. 둘째 줄에는 N개의 탑들의 높이가 직선상에 놓인 순서대로 하나의 빈칸을 사이에 두고 주어진다. 탑들의 높이는 1

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. stack<pair<int, int>> s를 만들어 타워의 인덱스와 높이를 저장합니다.

 

2. 타워의 높이를 입력받고, s.top()보다 타워의 높이가 더 크다면 (s.top() < h) s.pop()을 해줍니다. 왜냐하면 s.top()의 타워는 뒤의 타워가 더 크므로 더 이상 레이저를 수신할 수 없기 때문입니다.

 

3. s.top()보다 타워의 높이가 더 작다면 현재 s.top()의 인덱스를 출력합니다.

 

[ 소스코드 ]

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
#include<iostream>
#include<stack>
 
using namespace std;
 
int N;
 
int main()
{
    stack<pair<int,int>> s;
    scanf("%d", &N);
 
    for (int i = 1; i <= N; i++) {
        int h;
        scanf("%d", &h);
 
        while (!s.empty()) {
            if (s.top().second > h) {
                printf("%d ", s.top().first);
                break;
            }
            s.pop();
        }
 
        if (s.empty()) {
            printf("0 ");
        }
 
        s.push({ i,h });
    }
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

'백준' 카테고리의 다른 글

[ 백준 ] 18436번 - 수열과 쿼리 37 (C++)  (0) 2023.01.14
[ 백준 ] 14427번 - 수열과 쿼리 15 (C++)  (0) 2023.01.13
[ 백준 ] 13975번 - 파일 합치기 3 (C++)  (0) 2023.01.11
[ 백준 ] 16118번 - 달빛 여우 (C++)  (0) 2023.01.10
[ 백준 ] 16562번 - 친구비 (C++)  (0) 2023.01.09
반응형

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

 

2812번: 크게 만들기

N자리 숫자가 주어졌을 때, 여기서 숫자 K개를 지워서 얻을 수 있는 가장 큰 수를 구하는 프로그램을 작성하시오.

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. stack에 가장 첫 번째 숫자를 넣습니다.

 

2. 이후 for문을 돌면서 stack.top()과 arr [ i ]를 비교합니다.

 

3. stack.top() < arr [ i ] 이면 stack.top() >= arr [ i ]가 될 때까지 stack.pop()을 해줍니다.

 

4. 이후 stack에 arr [ i ]를 push 해줍니다.

 

5. ans에 stack에서 하나씩 뽑아 저장해 준 후 for문을 돌면서 하나씩 출력해줍니다.

 

[ 소스코드 ]

 

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
#include<iostream>
#include<stack>
 
using namespace std;
 
int N, K;
char arr[500001];
 
int main()
{
    scanf("%d %d", &N, &K);
 
    scanf("%s", arr);
 
    stack<int> s;
    stack<int> ans;
    s.push(arr[0] - '0');
 
    int cnt = 0;
 
    for (int i = 1; i < N; i++) {
        while (!s.empty()) {
            if (s.top() < arr[i] - '0' && cnt < K) {
                s.pop();
                cnt++;
            }
            else break;
        }
        s.push(arr[i] - '0');
    }
 
    while (!s.empty()) {
        ans.push(s.top());
        s.pop();
    }
 
    for (int i = 0; i < N - K; i++) {
        printf("%d", ans.top());
        ans.pop();
    }
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

'백준' 카테고리의 다른 글

[ 백준 ] 1365번 - 꼬인 전깃줄 (C++)  (0) 2022.12.16
[ 백준 ] 16397번 - 탈출 (C++)  (0) 2022.12.15
[ 백준 ] 9019번 - DSLR (C++)  (0) 2022.12.13
[ 백준 ] 2665번 - 미로만들기 (C++)  (0) 2022.12.12
[ 백준 ] 1726번 - 로봇 (C++)  (0) 2022.12.11
반응형

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

 

3954번: Brainf**k 인터프리터

각 테스트 케이스에 대해서, 프로그램이 종료된다면 "Terminates"를, 무한 루프에 빠지게 된다면 "Loops"를 출력한다. 무한 루프에 빠졌을 때는, 프로그램의 어느 부분이 무한 루프인지를 출력한다. ([

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. 각각의 브라켓의 쌍을 저장할 수 있도록 map을 선언합니다.

 

2. stack을 사용하여 ' [ '를 만나면 stack에 현재 idx를 push 하고, ' ] '를 만나면 stack의 top과 쌍이므로 map [ i ] = stack.top(), map [ stack.top() ] = i를 저장해줍니다.

 

3. 5천만번 반복했을 때 무한 루프 안이거나 프로그램은 항장 종료되어 있기 때문에 5천만 번 반복 후에도 끝나지 않으면 무조건 무한 루프 안입니다.

 

4. 5천 만번 실행 후 한번 더 5천만 번 실행하면서 무한 루프 안이므로 도달한 최대 idx를 max에 저장하고 그에 맞는 쌍을 출력해주면 됩니다.

 

[ 소스코드 ]

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
#include<iostream>
#include<stack>
#include<map>
#include<cstring>
 
#define M 256
 
using namespace std;
 
unsigned char arr[100000];
char cal[4097];
char input[4097];
 
int main()
{
    int T;
    scanf("%d", &T);
 
    for (int t = 0; t < T; t++) {
        int sm, sc, si;
        scanf("%d %d %d", &sm, &sc, &si);
        
        stack<int> s;
        map<int, int> m;
        memset(arr, 0, sizeof(arr));
        scanf("%s", cal);
        scanf("%s", input);
 
        for (int i = 0; i < sc; i++) {
            if (cal[i] == '[') {
                s.push(i);
            }
            if (cal[i] == ']') {
                int temp = s.top();
                s.pop();
                m[temp] = i;
                m[i] = temp;
            }
        }
 
        int cnt = 0;    //연산 횟수
        int cur = 0;    //현재 포이터 위치
        int c = 0;        //현재 연산의 위치
        int in = 0;        //현재 문자열의 위치
        int Max = 0;
 
        while (1) {
            if (cnt > 50000000) {
                Max = max(Max, c);
            }
            if (cal[c] == '+') {
                arr[cur]++;
            }
            else if (cal[c] == '-') {
                arr[cur]--;
            }
            else if (cal[c] == '<') {
                cur--;
                if (cur < 0) {
                    cur = sm - 1;
                }
            }
            else if (cal[c] == '>') {
                cur++;
                if (cur >= sm) {
                    cur = 0;
                }
            }
            else if (cal[c] == '[') {
                if (arr[cur] == 0) {
                    c = m[c];
                }
            }
            else if (cal[c] == ']') {
                if (arr[cur] != 0) {
                    c = m[c];
                }
            }
            else if (cal[c] == ',') {
                if (in < si) {
                    arr[cur] = input[in++];
                }
                else {
                    arr[cur] = 255;
                }
            }
            c++;
            cnt++;
            if (c >= sc) {
                printf("Terminates\n");
                break;
            }
            if (cnt >= 100000000) {
                printf("Loops %d %d\n", m[Max], Max);
                break;
            }
        }
    }
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

'백준' 카테고리의 다른 글

[ 백준 ] 2631번 - 줄세우기 (C++)  (0) 2022.10.19
[ 백준 ] 2636번 - 치즈 (C++)  (0) 2022.10.16
[ 백준 ] 15486번 - 퇴사 2 (C++)  (0) 2022.10.14
[ 백준 ] 14442번 - 벽 부수고 이동하기 2 (C++)  (0) 2022.10.13
[ 백준 ] 17472번 - 다리 만들기 2 (C++)  (0) 2022.10.12
반응형

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

 

1725번: 히스토그램

첫 행에는 N (1 ≤ N ≤ 100,000) 이 주어진다. N은 히스토그램의 가로 칸의 수이다. 다음 N 행에 걸쳐 각 칸의 높이가 왼쪽에서부터 차례대로 주어진다. 각 칸의 높이는 1,000,000,000보다 작거나 같은

www.acmicpc.net

 

 

[ 문제풀이 ]

 

다음과 같은 순서대로 문제를 풀어주시면 쉽게 답을 구할 수 있습니다.

 

1. push 하려는 막대의 높이가 s.top() 인덱스의 막대 높이보다 크거나 같다면 계속해서 스택을 쌓습니다. 

 

2. 만약 push 하려는 막대의 높이가 s.top() 인덱스의 막대 높이보다 작다면 s.top()이 push 하려는 막대 높이보다 커질 때까지 s.pop()을 해줍니다.

 

3. s.pop()을 할 때마다 직사각형의 넓이를 구하고 최댓값을 저장합니다.

 

다음 글은 세그먼트 트리와 분할 정복을 통해 문제를 푸는 방법입니다.

https://rudalsd.tistory.com/88?category=1064612 

 

[ 소스 코드 ]

 

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
#include<iostream>
#include<stack>
 
using namespace std;
 
int N;
int arr[100005];
int ans;
 
int main()
{
    stack<int> s;
    s.push(0);
    scanf("%d", &N);
 
    for (int i = 1; i <= N; i++) {
        scanf("%d", &arr[i]);
    }
 
    for (int i = 1; i <= N + 1; i++) {
        while (!s.empty() && arr[i] < arr[s.top()]) {
            int cur = s.top();
            s.pop();
            int W = arr[cur] * (i - s.top() - 1);
            ans = max(ans, W);
        }
        s.push(i);
    }
 
    printf("%d", ans);
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

'백준' 카테고리의 다른 글

[ 백준 ] 10026번 - 적록색약 (C++)  (0) 2022.08.05
[ 백준 ] 11438번 - LCA 2 (C++)  (0) 2022.08.04
[ 백준 ] 6549번 - 히스토그램에서 가장 큰 직사각형 (C++)  (0) 2022.08.02
[ 백준 ] 1629번 - 곱셈 (C++)  (0) 2022.08.01
[ 백준 ] 11725번 - 트리의 부모 찾기 (C++)  (0) 2022.07.31
반응형

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

 

6549번: 히스토그램에서 가장 큰 직사각형

입력은 테스트 케이스 여러 개로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있고, 직사각형의 수 n이 가장 처음으로 주어진다. (1 ≤ n ≤ 100,000) 그 다음 n개의 정수 h1, ..., hn (0 ≤ hi ≤

www.acmicpc.net

 

 

[ 문제풀이 ]

 

이 문제를 풀기 전에 다음 글을 먼저 읽고 오시는 것을 추천드립니다!!

https://rudalsd.tistory.com/51?category=1073064 

 

[ 자료구조 ] 세그먼트 트리 (Segment Tree)

1. 세그먼트 트리 (Segment Tree) 먼저, 세그먼트 트리가 무엇인지 알아봅시다! 세그먼트 트리는 구간 합을 저장하기 위한 트리입니다. 예를 들어 size가 5인 배열이 있다고 생각해봅시다. int arr [5] = {1

rudalsd.tistory.com

 

먼저 높이 값이 가장 작은 idx를 각각의 노드에 저장하는 세그먼트 트리를 만듭니다. 그 후 일정 구간에서 가장 작은 높이를 가지는 idx를 구하는 함수를 만든 후 그 idx를 기준으로 왼쪽 오른쪽으로 나누어 분할 정복을 해주시면 됩니다.

 

다음 글은 스택을 활용하여 문제를 푸는 방법입니다.

https://rudalsd.tistory.com/89?category=1064612 

 

[ 소스 코드 ]

 

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
#include<iostream>
#include<cmath>
 
#define ll long long
 
using namespace std;
 
int n;
int segTree[300000];
ll arr[100001];
ll ans;
 
int makeTree(int node, int start, int end)        //세그먼트 트리 만들기
{
    if (start == end) {        //리프노드
        return segTree[node] = start;
    }
 
    int mid = (start + end) / 2;
    int left = makeTree(node * 2, start, mid);        //왼쪽 자식 노드
    int right = makeTree(node * 2 + 1, mid + 1, end);    //오른쪽 자식 노드
 
    return segTree[node] = arr[left] > arr[right] ? right : left;
}
 
int find(int node, int start, int end, int sidx, int eidx)    //최소 높이의 idx return
{
    if (eidx < start || sidx > end) return 0;    //범위에 완전히 포함되지 않을 때
    if (start >= sidx && end <= eidx) return segTree[node];    //범위에 완전히 포함될 때
    //범위에 일부 포함될 때
    int mid = (start + end) / 2;
    int left = find(node * 2, start, mid, sidx, eidx);
    int right = find(node * 2 + 1, mid + 1, end, sidx, eidx);
 
    if (left == 0) return right;
    if (right == 0) return left;
    return arr[left] > arr[right] ? right : left;
}
 
void getMax(int start, int end)
{
    if (start > end) return;
    int min = find(1, 1, n, start, end);
 
    ll W = arr[min] * (end - start + 1);
    ans = max(ans, W);
 
    getMax(start, min - 1);
    getMax(min + 1, end);
}
 
int main()
{
    while (1)
    {
        ans = 0;
        scanf("%d", &n);
        if (n == 0)break;
        for (int i = 1; i <= n; i++) {
            scanf("%lld", &arr[i]);
        }
 
        makeTree(1, 1, n);
 
        getMax(1, n);
 
        printf("%lld\n", ans);
    }
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

'백준' 카테고리의 다른 글

[ 백준 ] 11438번 - LCA 2 (C++)  (0) 2022.08.04
[ 백준 ] 1725번 - 히스토그램 (C++)  (0) 2022.08.03
[ 백준 ] 1629번 - 곱셈 (C++)  (0) 2022.08.01
[ 백준 ] 11725번 - 트리의 부모 찾기 (C++)  (0) 2022.07.31
[ 백준 ] 11444번 - 피보나치 수 6 (C++)  (0) 2022.07.30
반응형

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

 

3015번: 오아시스 재결합

첫째 줄에 줄에서 기다리고 있는 사람의 수 N이 주어진다. (1 ≤ N ≤ 500,000) 둘째 줄부터 N개의 줄에는 각 사람의 키가 나노미터 단위로 주어진다. 모든 사람의 키는 231 나노미터 보다 작다. 사람

www.acmicpc.net

 

 

[ 문제풀이 ]

 

stack이라는 자료구조를 사용하면 쉽게 풀 수 있는 문제입니다.

 

항상 스택 안에는 키가 큰 순서로 정렬이 되게끔 만들어서 쌍을 구하는 방법으로 풀었습니다. 따라서 3개의 분기로 나누어야 합니다.

 

1. stack.top() < cur

먼저 내 앞에 있는 사람의 키가 나보다 작다면 나는 내 앞에 있는 사람보다 더 앞에 있는 사람을 볼 수 있습니다. 따라서 나보다 더 작은 사람을 stack에서 pop 해주고 ans에 키가 같은 사람의 수만큼인 cnt를 더해주면 됩니다. while을 통해 나보다 앞에 있는 사람 중 나보다 작은 사람들을 모두 pop 해주면 마지막에는 나보다 큰 사람이 내 앞에 있게 됩니다.

 

2. stack.top() == cur

만약 내 앞에 있는 사람이 나와 키가 같다면 내 앞에 키가 같은 사람의 수만큼 ans에 더해주고 cnt를 나를 포함한 같은 키를 가진 사람의 수만큼 갱신해줍니다. 이때 나보다 큰 사람이 존재한다면 stack의 사이즈가 1보다 크므로 사이즈가 1보다 클 때는 ans에 1을 한번 더 더해줍니다.

 

3. stack.top() > cur

만약 내 앞에 있는 사람이 나보다 키가 크다면 그 사람보다 앞에 있는 사람을 나는 볼 수 없기 때문에 ans에 1을 더해주면 끝이 납니다.

 

2
4
1
2
2
5
1

1. 위를 예로 들면 먼저 stack에 2가 들어갑니다.

ans = 0

 

2. 그리고 다음 수 4가 들어갈 때 stack.top() 보다 4가 더 크므로 stack을 pop 해주고 ans에 1을 더해준 후 4를 stack에 넣어줍니다.(1번 분기)

ans = 1

 

3. 그리고 1은 stack.top()인 4보다 작으므로 ans에 1을 더해준 후 push 합니다.(3번 분기)

ans = 2

 

4. 다음으로 들어올 수는 2인데 stack.top() 보다 크므로 stack을 pop 해주고 ans에 1을 더해준 후 push 해줍니다. (1번 분기)그리고 4는 2보다 크므로 ans에 1을 더해줍니다.(3번 분기)

ans = 4

4의 cnt = 1

2의 cnt = 1

 

5. 또 2라는 수가 들어오는데 stack.top()과 같은 수이므로 ans에 같은 수가 존재하는 만큼(1)을 더해주고, cnt에 나를 포함한 같은 수가 존재하는 만큼 갱신해줍니다. 또한 size가 1보다 크므로 ans에 1을 더해줍니다.(2번 분기)

ans = 5

4의 cnt = 1

2의 cnt = 2

 

6. 다음으로 들어올 수는 5입니다. while문을 통해서 나보다 더 작은 키를 가진 사람들을 pop 해주면서 cnt를 더하면 됩니다. 2의 cnt = 2, 4의 cnt = 1이므로 ans에 3을 더해줍니다.(1번 분기)

ans = 9

 

7. 마지막으로 1이 들어오면 stack.top()인 5보다 작으므로 ans에 1을 더해주면 됩니다.(3번 분기)

ans = 10

 

[ 소스 코드 ]

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
#include<iostream>
#include<stack>
 
using namespace std;
 
int N;
 
struct node{
    int num;    //키
    int cnt;    //붙어있는 같은 키를 가진 사람
};
 
int main()
{
    cin >> N;
 
    stack<node> s;
 
    long long ans = 0;
 
    for (int i = 0; i < N; i++) {
        int cur;
        scanf("%d", &cur);
        int cnt = 1;
 
        while (!s.empty() && s.top().num < cur) {    //바로 앞사람의 키보다 현재 키가 더 클 때
            ans += s.top().cnt;
            s.pop();
        }
        if (!s.empty()) {    //stack이 비어있지 않을 때
            if (s.top().num == cur) {    //앞사람과 현재의 키가 같을 때
                ans += s.top().cnt;        //앞에 같은 키를 가진 사람 수만큼 ans에 더해줌
                cnt = s.top().cnt + 1;    //현재를 포함해서 같은 키를 가진 사람 + 1
                if (s.size() > 1) {        //같은 키를 가진 사람들 보다 큰 사람이 존재하면
                    ans++;
                }
                s.pop();
            }
            else {    //앞사람이 현재의 키보다 클 때
                ans++;
            }
        }
 
        s.push({ cur, cnt });
    }
 
    cout << ans;
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

'백준' 카테고리의 다른 글

[ 백준 ] 13977번 - 이항 계수와 쿼리 (C++)  (0) 2022.07.12
[ 백준 ] 11689번 - GCD(n, k) = 1 (C++)  (0) 2022.07.11
[ 백준 ] 11505번 - 구간 곱 구하기 (C++)  (0) 2022.07.09
[ 백준 ] 2096번 - 내려가기 (C++)  (0) 2022.07.08
[ 백준 ] 5639번 - 이진 검색 트리 (C++)  (0) 2022.07.07

+ Recent posts

티스토리툴바