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/1966

 

1966번: 프린터 큐

여러분도 알다시피 여러분의 프린터 기기는 여러분이 인쇄하고자 하는 문서를 인쇄 명령을 받은 ‘순서대로’, 즉 먼저 요청된 것을 먼저 인쇄한다. 여러 개의 문서가 쌓인다면 Queue 자료구조에

www.acmicpc.net

큐에 저장되어있는 중요도가 높은 순서대로 pop을 해야합니다.

저는 인덱스와 중요도 관리를 해주기 위해 큐에 배열(중요도, 인덱스)을 넣었습니다.

 

그리고 중요도가 입력되면 현재 최댓값을 저장하기 위해 몇번 나왔는지(num[])와 최댓값 (maxp)를 사용하였습니다.

그리고 다음과 같은 과정을 수행합니다.

1. 큐에서 원소하나를 pop

2. pop한 원소가 현재 최대 중요도인지 확인 -> 최대 중요도가 아니면 다시 큐에 push합니다.

3. 최대 중요도이면 인덱스가 M과 일치하는지 확인 -> 일치하면 그대로 출력하고 리턴합니다.

4. 인덱스가 맞지 않으면 num[x]을 1 내리고, 만약 num[x]이 0이 되었을 때 다음 최댓값을 꺼내옵니다.

 

이 과정을 반복하여 M번 인덱스가 몇 번째로 pop되는지 출력합니다.

 

 

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
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
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 Queue<int[]> q = new LinkedList<>();
    static int num[] = new int[10];
    static int N, M, maxp;
 
    static void func() {
        while (true) {
            int x = q.peek()[0];
            int idx = q.peek()[1];
 
            q.remove();
            if (x != maxp)
                q.add(new int[] { x, idx });
            else {
                if (idx == M) {
                    sb.append(N - q.size() + "\n");
                    return;
                }
                num[x]--;
                if (num[x] == 0) {
                    for (int i = x; i >= 1; i--) {
                        if (num[i] > 0) {
                            maxp = i;
                            break;
                        }
                    }
                }
            }
        }
    }
 
    static void input() throws Exception {
        int x;
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
 
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            x = Integer.parseInt(st.nextToken());
            q.add(new int[] { x, i });
            num[x]++;
            maxp = Math.max(maxp, x);
        }
    }
 
    static void clear() {
        maxp = 0;
        for (int i = 1; i <= 9; i++)
            num[i] = 0;
        while (!q.isEmpty())
            q.remove();
    }
 
    public static void main(String[] args) throws Exception {
        st = new StringTokenizer(br.readLine());
        int tc = Integer.parseInt(st.nextToken());
        while (tc-- > 0) {
            input();
            func();
            clear();
        }
        System.out.println(sb.toString());
    }
}
 cs

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

boj 10866 덱  (0) 2021.02.02
boj 11000 강의실 배정  (0) 2021.02.01
boj 2164 카드2  (0) 2021.02.01
boj 10845 큐  (0) 2021.02.01
boj 1655 가운데를 말해요  (0) 2021.02.01

www.acmicpc.net/problem/2164

 

2164번: 카드2

N장의 카드가 있다. 각각의 카드는 차례로 1부터 N까지의 번호가 붙어 있으며, 1번 카드가 제일 위에, N번 카드가 제일 아래인 상태로 순서대로 카드가 놓여 있다. 이제 다음과 같은 동작을 카드가

www.acmicpc.net

큐에 1부터 N까지 순서대로 push가 된 상태로 있습니다.

 

여기서 다음과 같은 동작을 카드가 하나 남을때까지 반복합니다.

1. 큐의 가장 위에있는 숫자를 버린다.

2. 큐의 가장 위에있는 숫자를 큐의 맨 뒤로 보내고 삭제한다.

 

큐의 크기가 1이 되면 break을 하고 남아있는 수를 출력합니다.

 

 

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
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
 
public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static Queue<Integer> q = new LinkedList<>();
    static int N;
 
    static void func() {
        while (true) {
            if (q.size() == 1)
                break;
            
            q.remove();
            q.add(q.peek());
            q.remove();
        }
        
        System.out.println(q.peek());
    }
 
    static void init() {
        for (int i = 1; i <= N; i++) {
            q.add(i);
        }
    }
 
    static void input() throws Exception {
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
    }
 
    public static void main(String[] args) throws Exception {
        input();
        init();
        func();
    }
}
 cs

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

boj 11000 강의실 배정  (0) 2021.02.01
boj 1966 프린터 큐  (0) 2021.02.01
boj 10845 큐  (0) 2021.02.01
boj 1655 가운데를 말해요  (0) 2021.02.01
boj 11279 최대 힙  (0) 2021.01.31

www.acmicpc.net/problem/10845

 

10845번: 큐

첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지

www.acmicpc.net

큐의 여러가지 기능을 사용해 볼 수 있는 간단한 문제입니다.

 

입력으로 6개의 명령이 주어집니다.

push X : 정수 X를 push

pop : q.peek()를 출력 후 pop, 만약 큐가 비어있으면 -1 출력

size : 큐의 크기를 출력

empty : 큐가 비어있으면 1, 아니면 0 출력

front : q.peek()를 출력, 만약 큐가 비어있으면 -1 출력

back : 큐에 가장 최근에 push된 정수 출력, 만약 큐가 비어있으면 -1 출력

 

큐가 비어있으면 -1을 출력해야하는 예외 처리만 신경써주시면 되겠습니다.

 

 

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
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
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 Queue<Integer> q = new LinkedList<>();
    static int N, last;
 
    static void push(int x) {
        q.add(x);
    }
 
    static void pop() {
        if (q.isEmpty()) {
            sb.append("-1\n");
            return;
        }
 
        sb.append(q.peek() + "\n");
        q.remove();
    }
 
    static void size() {
        sb.append(q.size() + "\n");
    }
 
    static void empty() {
        if (q.isEmpty())
            sb.append("1\n");
        else
            sb.append("0\n");
    }
 
    static void front() {
        if (q.isEmpty()) {
            sb.append("-1\n");
            return;
        }
 
        sb.append(q.peek() + "\n");
    }
 
    static void back() {
        if (q.isEmpty()) {
            sb.append("-1\n");
            return;
        }
 
        sb.append(last + "\n");
    }
 
    static void input() throws Exception {
        String type;
        int x;
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        while (N-- > 0) {
            st = new StringTokenizer(br.readLine());
            type = st.nextToken();
 
            if ("push".equals(type)) {
                x = Integer.parseInt(st.nextToken());
                push(x);
                last = x;
            } else if ("pop".equals(type))
                pop();
            else if ("size".equals(type))
                size();
            else if ("empty".equals(type))
                empty();
            else if ("front".equals(type))
                front();
            else
                back();
        }
    }
 
    public static void main(String[] args) throws Exception {
        input();
        System.out.println(sb.toString());
    }
}
 cs

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

boj 1966 프린터 큐  (0) 2021.02.01
boj 2164 카드2  (0) 2021.02.01
boj 1655 가운데를 말해요  (0) 2021.02.01
boj 11279 최대 힙  (0) 2021.01.31
boj 1927 최소 힙  (0) 2021.01.31

+ Recent posts

티스토리툴바