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

 

21939번: 문제 추천 시스템 Version 1

tony9402는 최근 깃헙에 코딩테스트 대비 문제를 직접 뽑아서 "문제 번호, 난이도"로 정리해놨다. 깃헙을 이용하여 공부하시는 분들을 위해 새로운 기능을 추가해보려고 한다. 만들려고 하는 명령

www.acmicpc.net

recommend x

x가 1인 경우 리스트에서 가장 어려운 문제의 번호를 출력, 가장 어려운 문제가 여러 개면 문제 번호가 큰 것을 출력

x가 -1인 경우 리스트에서 가장 쉬운 문제의 번호를 출력, 가장 어려운 문제가 여러 개면 문제 번호가 작은 것을 출력

 

add P L

리스트에 난이도가 L인 문제 번호 P를 추가한다.

현재 리스트에 없는 문제만 들어오며, 이미 해결하여 리스트에서 제외된 문제가 다시 들어올 수 있다.

 

solved P

리스트에서 문제 번호 P를 제거한다. (해결한 것으로 간주)

 

문제들은 [문제 번호, 난이도] 로 정리되어 있으며, 들어온 순서대로 명령을 처리하는 문제입니다.

recommend 명령어에서 난이도가 가장 어려운 문제와 가장 쉬운 문제를 빠르게 뽑아내야 하므로 우선 순위 큐를 2개 사용하며, 최대 우선순위 큐와 최소 우선순위 큐를 같이 관리합니다.

 

각 문제의 난이도를 나타내기 위해 levellist라는 배열을 사용하였으며, 값이 0이 아니라면 리스트에 있는 문제라는 뜻입니다.

이를 이용하여 solved 시 levellist의 값을 0으로 바꾸고, recommend 명령어가 들어왔을 때 출력하기 전에 현재 최대/최소 우선순위 큐에 이미 solved된 문제가 있는지 확인하는 작업을 거친 후에 출력하도록 합니다.

 

 

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
#include <iostream>
#include <queue>
#include <algorithm>
#include <set>
#include <string>
#define MAX 100001
using namespace std;
typedef pair<int, int> pi;
 
priority_queue<pi, vector<pi>, less<pi> > mxq;
priority_queue<pi, vector<pi>, greater<pi> > mnq;
int levellist[MAX];
int N, M;
 
void func() {
    string type;
    int x, y;
    cin >> M;
    while (M--) {
        cin >> type;
        if (type == "add") {
            cin >> x >> y;
            mxq.push({ y,x });
            mnq.push({ y,x });
            levellist[x] = y;
        }
        else {
            cin >> x;
            if (type == "recommend") {
                if (x == 1) {
                    while (1) {
                        int p = mxq.top().second;
                        int l = mxq.top().first;
                        if (levellist[p] == l) break;
                        mxq.pop();
                    }
 
                    cout << mxq.top().second << '\n';
                }
                else {
                    while (1) {
                        int p = mnq.top().second;
                        int l = mnq.top().first;
                        if (levellist[p] == l) break;
                        mnq.pop();
                    }
 
                    cout << mnq.top().second << '\n';
                }
            }
            else {
                levellist[x] = 0;
            }
        }
    }
}
 
void input() {
    int P, L;
    cin >> N;
    for (int i = 0; i < N; i++) {
        cin >> P >> L;
        mxq.push({ L,P });
        mnq.push({ L,P });
        levellist[P] = L;
    }
}
 
int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios::sync_with_stdio(false);
 
    input();
    func();
    
    return 0;
}
 cs

'algorithm > data-structure' 카테고리의 다른 글

boj 15926 현욱은 괄호왕이야!!  (1) 2023.07.24
boj 17299 오등큰수  (0) 2021.02.22
boj 9372 상근이의 여행  (0) 2021.02.09
boj 1158 요세푸스 문제  (0) 2021.02.09
boj 1918 후위 표기식  (0) 2021.02.05

www.acmicpc.net/problem/11279

 

11279번: 최대 힙

첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가

www.acmicpc.net

우선순위 큐를 연습하기 위해 두번째 힙 문제를 풀어봤습니다.

 

앞에서 포스팅했던 PriorityQueue는 작은 값이 peek()으로 온다고 하였습니다.

하지만 이 문제는 최대 힙을 구하는 문제입니다.

 

입력으로 주어지는 값들을 음수화해서 큐에 넣어주면 가장 큰 값이 가장 작은 값이 됩니다.

출력할 때도 -peek()을 출력해주시면 됩니다.

 

 

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
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.PriorityQueue;
import java.util.StringTokenizer;
 
public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static StringBuffer sb = new StringBuffer();
    static PriorityQueue<Integer> q = new PriorityQueue<>();
    static int N, x;
 
    static void solve() {
        if (x == 0) {
            if (q.isEmpty()) {
                sb.append("0\n");
                return;
            }
 
            sb.append(-q.peek() + "\n");
            q.remove();
            return;
        }
 
        q.add(-x);
    }
 
    static void input() throws Exception {
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
 
        while (N-- > 0) {
            st = new StringTokenizer(br.readLine());
            x = Integer.parseInt(st.nextToken());
 
            solve();
        }
    }
 
    public static void main(String[] args) throws Exception {
        input();
        System.out.println(sb.toString());
    }
}
 cs

'algorithm > data-structure' 카테고리의 다른 글

boj 10845 큐  (0) 2021.02.01
boj 1655 가운데를 말해요  (0) 2021.02.01
boj 1927 최소 힙  (0) 2021.01.31
boj 4889 안정적인 문자열  (0) 2021.01.26
boj 2504 괄호의 값  (0) 2021.01.26

www.acmicpc.net/problem/1927

 

1927번: 최소 힙

첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0

www.acmicpc.net

우선순위 큐를 연습하기 위해 간단한 힙 문제를 풀어보았습니다.

 

최소힙은 PriorityQueue로 간단하게 해결할 수 있습니다.

PriorityQueue는 가장 작은 값이 peek()으로 오기때문에

0이 아니면 그대로 add,

0이 오면 peek() 값을 출력해주시면 됩니다.

 

 

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
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.PriorityQueue;
import java.util.StringTokenizer;
 
public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static StringBuffer sb = new StringBuffer();
    static PriorityQueue<Integer> q = new PriorityQueue<>();
    static int N, x;
 
    static void solve() {
        if (x == 0) {
            if (q.isEmpty()) {
                sb.append("0\n");
                return;
            }
 
            sb.append(q.peek() + "\n");
            q.remove();
            return;
        }
 
        q.add(x);
    }
 
    static void input() throws Exception {
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
 
        while (N-- > 0) {
            st = new StringTokenizer(br.readLine());
            x = Integer.parseInt(st.nextToken());
 
            solve();
        }
    }
 
    public static void main(String[] args) throws Exception {
        input();
        System.out.println(sb.toString());
    }
}
 cs

'algorithm > data-structure' 카테고리의 다른 글

boj 1655 가운데를 말해요  (0) 2021.02.01
boj 11279 최대 힙  (0) 2021.01.31
boj 4889 안정적인 문자열  (0) 2021.01.26
boj 2504 괄호의 값  (0) 2021.01.26
boj 6198 옥상 정원 꾸미기  (0) 2021.01.26

+ Recent posts

티스토리툴바