[Algorithm] 4주차 스터디 - 큐, 덱 (백준 11866, 5430, 10025, 15565)

문제 (11866: 요세푸스 문제 0)

www.acmicpc.net/problem/11866

11866번: 요세푸스 문제 0

N명의 사람이 원을 이루면서 앉아있고, 양의 정수 K(≤N)가 주어진다. 순서대로 K번째 사람을 제거하고, N명의 사람이 모두 제거될 때까지 계속된다. 원에서 사람들이 제거되는 순서를 (N, K)-요세푸스 순열이라고 한다.

N과 K가 주어지면, (N, K)-요세푸스 순열을 구하는 문제다.

풀이

queue의 FIFO(First-In-First-Out) 구조를 활용한다.

 

queue에 1부터 N까지의 정수를 push 한다. K를 기준으로 그 앞의 수를 모두 순서대로 queue에 push 하고(queue의 뒤로 삽입), push 한 수는 pop 한다. 이제 queue의 front에는 K가 있으므로 이를 pop 한다. N명의 사람이 모두 제거될 때까지 계속 K번째 사람을 제거해야 하므로, queue가 empty가 될 때까지 해당 작업을 반복한다.

 

소스코드

#include <iostream>
#include <queue>
 
using namespace std;
 
int N, k;
queue<int> q;
 
 
void josephus(int N, int k) {
    cout << "<";
    while (!q.empty()) {
        for (int i = 0; i < k - 1; i++) {
            q.push(q.front());
            q.pop();
        }
        cout << q.front();
        q.pop();
 
        if (!q.empty()) {
            cout << ", ";
        }
    }
    cout << ">";
}
 
int main() {
    cin >> N >> k;
 
    for (int i = 1; i <= N; i++) {
        q.push(i);
    }
 
    josephus(N, k);
}

문제 (5430: AC)

www.acmicpc.net/problem/5430

5430번: AC

두 가지 함수 R(뒤집기)과 D(버리기)가 있다. 함수 R은 배열에 있는 숫자의 순서를 뒤집는 함수이고, D는 첫 번째 숫자를 버리는 함수이다. 배열이 비어있는데 D를 사용한 경우에는 에러가 발생하고, 함수는 조합해서 한 번에 사용할 수 있다. 배열의 초기값과 수행할 함수가 주어졌을 때, 최종 결과를 구하는 문제다.

풀이

front와 end에서 삭제와 삽입이 모두 가능한 deque을 사용한다.

 

우선, substr을 이용하여 정수 배열에서 정수만 추출하여 deque에 앞에서부터 차례로 push_back 한다.

 

정수 배열의 초기 방향을 bool reverse = false라고 하자.

수행할 함수가 R이면, reverse의 bool 값을 바꿔준다. R이 한 개만 존재한다면 reverse = true이고, R이 두 개면 reverse = false, R이 세 개면 다시 reverse = true... 가 된다.

 

수행할 함수가 D이면, deque에서 값을 하나 빼준다. 이때 reverse = false, 즉 원래 배열의 방향과 같다면 deque에서 pop_front를 하고 reverse = true, 즉 원래 배열의 방향과 다르다면, deque에서 pop_back을 한다. deque이 empty인데 함수 D를 수행해야 한다면, error를 출력한다.

 

reverse = false라면, deque의 front부터 하나씩 출력하고, reverse = true라면, deque의 back부터 하나씩 출력한다.

 

소스코드

#include <iostream>
#include <deque>
#include <string>
 
using namespace std;
 
int T;           // 테스트 케이스의 개수
string p;        // 수행할 함수
int n;           // 배열 크기
string arr; // 정수 배열
deque<int> d; // 정수 저장할 deque
 
class Error {};
 
int main() {
    cin >> T;
 
    for (int i = 0; i < T; i++) {
        d.clear();
 
        cin >> p;
 
        cin >> n;
        cin >> arr;
 
        // arr의 '['와 ']' 제거
        arr = arr.substr(1, arr.size() - 2);
 
        // 원래 정수 배열과 같은 방향이면 false
        bool reverse = false;
 
        try {
            if (n > 0) {
                int a = 0;
                int b = 0;
                // arr에서 정수만 추출하여 deque에 저장
                for (; b < arr.length(); b++) {
                    if (arr[b] == ',') {
                        if (a < b) {
                            d.push_back(stoi(arr.substr(a, b - a)));
                            a = b + 1;
                        }
                    }
                }
                if (!d.empty()) {
                    d.push_back(stoi(arr.substr(a)));
                }
                else {
                    d.push_back(stoi(arr));
                }
            }
 
            for (int i = 0; i < p.length(); i++) {
                if (p[i] == 'R') {
                    reverse = !reverse;
                }
                else if (p[i] == 'D') {
                    if (d.empty()) {
                        throw Error();
                        break;
                    }
                    if (reverse == false) {
                        d.pop_front();
                    }
                    else {
                        d.pop_back();
                    }
                }
            }
 
            cout << "[";
            while (d.size()) {
                if (reverse == false) {
                    cout << d.front();
                    d.pop_front();
                }
                else {
                    cout << d.back();
                    d.pop_back();
                }
 
                if (!d.empty()) {
                    cout << ",";
                }
            }
            cout << "]\n";
        }
        catch (Error) {
            cout << "error\n";
        }
    }
}

문제 (10025: 게으른 백곰)

www.acmicpc.net/problem/10025

10025번: 게으른 백곰

1차원 배열이 있고, 총 N개의 얼음 양동이들이 x_i(0 ≤ x_i ≤ 1,000,000) 좌표마다 놓여있고 각 양동이 안에는 g_i(0 ≤ g_i ≤ 10,000)씩의 얼음이 들어있다. 일단 백곰 앨버트가 자리를 잡으면 그로부터 좌우로 K(1 ≤ K ≤2,000,000)만큼

떨어진 양동이까지 닿을 수 있다. 앨버트는 양동이가 놓여있는 자리에도 자리 잡을 수 있으며, 모든 얼음 양동이의 위치는 다르다. 앨버트가 최적의 자리를 골랐을 때 얼음의 합, 즉 얼음들의 합의 최댓값을 구하는 문제다. 

풀이

key와 value가 쌍으로 저장되며 key를 기준으로 오름차순 정렬하는 map, FIFO(First-In-First-Out) 구조를 가진 queue, 데이터 쌍을 표현할 수 있는 pair를 활용한다.

 

map의 key에 좌표(x_i)를 저장하고, value에 얼음의 양(g_i)을 저장한다. map은 key를 기준으로, 즉 좌표를 기준으로 오름차순으로 정렬된다. for loop을 돌면서, queue가 empty인 경우, queue에 key와 value를 push 하고, sum에 value를 더해준다. key와 value 쌍을 push 해야 하므로, queue<pair<int, int>>에 push 한다.

 

앨버트의 좌우로 K만큼 떨어진 양동이까지 닿을 수 있으므로, 현재 좌표와 queue의 front에 있는 좌표의 차가 2*K보다 작거나 같아야 앨버트가 접근할 수 있는 범위에 들어간다.

앨버트가 접근할 수 있는 최대범위: 2*K

 

따라서 queue가 empty가 아닌 경우, 현재 좌표와 queue의 front에 있는 좌표의 차가 2*K보다 작거나 같으면, queue에 해당 key와 value를 push 하고, sum에 value를 더해준다. 만약 queue가 empty가 아니고 현재 좌표와 queue의 front에 있는 좌표의 차가 2*K보다 크다면, sum에서 queue의 front에 있는 value를 빼주고 queue에서 해당 원소를 pop 한다. 

 

sum의 값이 갱신될 때마다, max와 sum을 비교하여 sum이 더 크다면 max를 고쳐준다. 

 

소스코드

#include <iostream>
#include <queue>
#include <utility>
#include <map>
 
using namespace std;
 
int main(){
    int N, K;
    cin >> N >> K;
 
    map<int, int> m;
    for (int i=0;i<N;i++){
        int g, x;
        cin >> g >> x;
        m[x] = g;
    }
 
    queue<pair<int, int>> q;
    int max = 0, sum = 0;
    for(map<int,int>::iterator it = m.begin();it!=m.end();it++){
        int idx = it->first;
        int val = it->second;
        while(!q.empty()){
            if(idx - q.front().first <= 2*K){
                q.push({idx, val});
                sum += val;
                break;
            }
            else{
                sum -= q.front().second;
                q.pop();
            }
        }
        if(q.empty()){
            q.push({idx, val});
            sum += val;
        }
        
        if(max < sum){
            max = sum;
        }
    }
 
    cout << max << endl;
 
    return 0;
}

 

문제 (15565: 귀여운 라이언)

www.acmicpc.net/problem/15565

15565번: 귀여운 라이언

1과 2로 이루어진 N개의 숫자가 있고, 1이 K개 이상 있는 가장 작은 연속된 1의 집합의 크기를 구하는 문제다.

풀이

queue의 FIFO(First-In-First-Out) 구조를 활용한다. 앞에서 살펴본 <10025: 게으른 백곰>과 풀이가 유사하다.

 

예제 입력 값을 이용하여 살펴보자.

10 3

1 2 2 2 1 2 1 2 2 1

 

우선 vector에 N개의 숫자를 받으면서 1이 총 몇 개 있는지 확인하고, 그 개수를 val에 저장한다. val이 K 보다 작다면 -1을 출력하고 프로그램을 종료한다. 

 

count로 1의 개수를 세고, for loop를 돌면서 vector에 저장된 값을 확인한다. vector에서 1이 처음 등장하면, queue에 해당 원소를 push 하고 count를 1 증가시킨다.

1

queue에 처음 등장한 1을 추가한 이후부터는 값이 1이든, 2이든 상관없이 queue에 원소를 push 한다.

단, 원소가 1이면 count를 1씩 증가시킨다.

1

2

2

2

1

2

1

count가 K가 되는 순간, queue의 size(= 문제에서 구하고자 하는 집합의 크기)와 min(vector의 size로 초기화)과의 값을 비교한다. min보다 queue의 size가 작다면, min의 값을 갱신한다.

 

마저 loop를 돌면서, count가 K보다 크거나 같아지면 queue에서 원소를 하나 pop 한다. 이 원소의 값은 1이다.

2

2

2

1

2

1

그리고 queue가 empty가 아니고, queue의 front가 1이 될 때까지 pop을 반복한다. 

1

2

1

queue의 front가 1이 되면 또 queue에 원소를 push 하다가, count가 K가 되면, queue의 size와 min과의 값을 비교하는 작업을 한다.

1

2

1

2

2

1

위 작업을 반복한 후, 구해진 min을 출력한다.

 

소스코드

#include <iostream>
#include <queue>
#include <vector>
 
using namespace std;
 
int main(){
    int N, K;
    cin >> N >> K;
 
    int val = 0;
    vector<int> v(N);
    for(int i=0;i<N;i++){
        cin >> v[i];
        if(v[i] == 1){
            val++;
        }
    }
 
    if(val < K){
        cout << -1 << endl;
        return 0;
    }
 
    int min = v.size();
    int count = 0;
    queue<int> q;
    for(int i=0;i<N;i++){
        if(q.empty()){
            if(v[i] == 1){
                q.push(v[i]);
                count++;
            }
        }
        else{
            if(v[i] == 1){
                if(count >= K){
                    q.pop();
                    while(!q.empty() && q.front() != 1){
                        q.pop();
                    }
                }
                else{
                    count++;
                }
            }
            q.push(v[i]);
        }
 
        if(count >= K && q.size() < min){
            min = q.size();
        }
    }
 
    cout << min << endl;
 
    return 0;
}