반응형

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

+ Recent posts

티스토리툴바