180421 동아리 연습 문제 풀이

A. 스택

동아리 시간 때 설명했었고, 다음 코드를 첨부한다.

#include <iostream>
#include <string.h>
#include <stack>
using namespace std;
 
stack<int> st;
int q;
char op[10];
int k;
 
int main()
{
    cin >> q;
 
    for (int t=0; t<q; t++) {
        cin >> op;
        if (strcmp(op, "push") == 0)
            cin >> k;
 
        if (strcmp(op, "push") == 0)
            st.push(k);
 
        if (strcmp(op, "pop") == 0) {
            if (st.empty()) cout << "-1\n";
            else {
                cout << st.top() << "\n";
                st.pop();
            }
        }
 
        if (strcmp(op, "size") == 0)
            cout << st.size() << "\n";
 
        if (strcmp(op, "empty") == 0)
            cout << (st.empty() ? 1 : 0) << "\n";
 
        if (strcmp(op, "top") == 0) {
            if (st.empty()) cout << "-1\n";
            else cout << st.top() << "\n";
        }
    }
}
 

B. 스택 수열

스택에서 수를 pop함과 동시에 수열의 수가 하나씩 늘어나게 된다. 입력된 수열을 만들 수 있는 전략을 생각해 보자.

1. 첫 번째 수 $a_1$을 만들려면, $1$에서 $a_1$까지의 모든 수를 push한 다음에 한 번의 pop을 해야 한다.

2-1. 만약 두 번째 수가 $a_1-1$이라면, 바로 한 번 더 pop하면 된다.

2-2. 만약 두 번째 수가 $a_1$ 초과라면, 다시 $a_2$까지의 모든 수를 push한 다음에 한 번의 pop을 해야 한다.

2-3. 만약 두 번째 수가 $a_1-1$ 미만이라면, 만들 수 없는 수열이다.

일반화하면 다음과 같다. $i=1..n$까지 돌면서 각 $a_i$를 만들려 한다. (1) $a_i$가 이 때까지 스택에 넣은 마지막 수와 같거나 크다면, 마지막 수+1부터 $a_i$까지의 수들을 push한 다음 한 번의 pop을 한다. (2) 그렇지 않다면, $a_i$는 스택 안 바로 뺄 수 없는 곳에 들어 있으며, $a_i$를 만들 수 없다. 이 때엔 수열 전체가 만들 수 없으므로 "NO"를 출력한다.

C. 괄호의 값

괄호 문자열이 재귀적으로 정의되므로, 괄호의 값 또한 재귀적으로 풀 수 있다. 스택에 "현재 단계에서 괄호가 얼마나 열렸는지"를 유지한다.

할 수 있는 한 가지 관찰은, "여는 괄호와 닫는 괄호가 연이어서 나오는 지점"들에서 괄호의 값이 결정된다는 것이다. 위의 스택을 바탕으로 현재 단계에서 열려 있는 괄호들의 배율(×2 또는 ×3)의 누적 곱을 저장한 뒤, 그런 지점들에서 이 값들을 모두 합해주면 답을 얻을 수 있다.

만약 닫는 괄호가 현재 스택에 들어 있는 여는 괄호와 짝이 맞지 않는 괄호라면 입력은 만들 수 없는 괄호열이 된다. 모든 괄호를 입력받고 나서 스택이 비어있는지를 꼭 확인해주도록 하자(아니면 만들 수 없는 괄호열이다).

D. 큐

동아리 시간 때 설명했었고, 다음 코드를 첨부한다.

#include <iostream>
#include <string.h>
#include <queue>
using namespace std;
 
queue<int> st;
int q;
char op[10];
int k;
 
int main()
{
    cin >> q;
 
    for (int t=0; t<q; t++) {
        cin >> op;
        if (strcmp(op, "push") == 0)
            cin >> k;
 
        if (strcmp(op, "push") == 0)
            st.push(k);
 
        if (strcmp(op, "pop") == 0) {
            if (st.empty()) cout << "-1\n";
            else {
                cout << st.front() << "\n";
                st.pop();
            }
        }
 
        if (strcmp(op, "size") == 0)
            cout << st.size() << "\n";
 
        if (strcmp(op, "empty") == 0)
            cout << (st.empty() ? 1 : 0) << "\n";
 
        if (strcmp(op, "front") == 0) {
            if (st.empty()) cout << "-1\n";
            else cout << st.front() << "\n";
        }
        
        if (strcmp(op, "back") == 0) {
            if (st.empty()) cout << "-1\n";
            else cout << st.back() << "\n";
        }
        
    }
}
 

E. 홍준이와 울타리

큐를 쓰는 문제가 몇 개 없어서 가지고 왔더니, 알고보니 데크를 쓰는 문제였다. 데크에 관해서도 동아리 시간에 한 설명으로 대체한다.

왼쪽부터 각 $i = x .. n$에 대해, $a_{i-x+1} .. a_i$ 중 가장 작은 높이를 찾는 문제를 생각하자. 이 문제가 풀린다면 본 문제도 풀릴 것이다. 이는 데크를 이용하여 풀 수 있는데, 핵심 아이디어는 "왼쪽에서부터 훑으면서 계산했을 때, 현재 원소 $x$가 등장했다면, 그 전에 등장한 $x$보다 큰 원소들은 앞으로의 최솟값에 영향을 끼치지 못한다"는 것이다. 이는 deque를 이용해 해결할 수 있다. deque의 앞에서 뒤로 가면서 뒤의 원소들이 더 새롭고(뒤에 등장하고), 또한 뒤의 원소들이 더 큰 순서로 deque 안에 들어있다. 차례대로 원소를 넣으면서 이 순서를 유지할 것이다.

1. 현재 $i$번째 인덱스를 보고 있다: $a_i$를 데크의 뒤에 넣고 싶다.

2. 데크의 맨 뒤에 있는 원소가 $a_i$보다 크다면, 그 원소를 뺀다. 데크의 맨 뒤에 있는 원소가 $a_i$보다 작게 될 때까지 반복한다.

3. 데크의 맨 뒤에 $a_i$를 넣는다.

4. 데크의 맨 앞에 있는 원소가 등장한 인덱스(데크에 원소를 넣을 때 같이 기록해 두어야 한다!)가 $i-x+1$ 미만이 되지 않도록, 그런 원소들을 데크의 앞에서 제거해 준다.

5. 이 때, 데크의 맨 앞에 있는 원소가 $a_{i-x+1} .. a_i$ 중에서 가장 작은 원소가 된다.

그러면, 왼쪽에서부터 차례로 그 위치에서 칠할 수 있는 최대 높이까지 페인트를 칠해 보면서, 그런 높이가 변하거나 새로 페인트를 칠해야 하는 높이마다 새로 칠해 주는 방법으로 최대한의 널빤지를 페인트칠할 수 있다.

F. 최대 힙

동아리 시간에 설명했었고, 다음 소스를 첨부한다.

#include <bits/stdc++.h>
using namespace std;
 
priority_queue<int> pq;
 
int main()
{
    int n;
    cin >> n;
    while (n--) {
        int x;
        cin >> x;
        if (x) pq.push(x);
        else {
            if (pq.empty()) cout << "0\n";
            else {
                cout << pq.top() << '\n';
                pq.pop();
            }
        }
    }
}
 

G. 절댓값 힙

priority_queue 안에 비교 함수는 다음과 같이 정의할 수 있다. 동아리 시간에 설명하기를 깜빡하였다. ㅠ priority_queue 선언할 때 두번째 인자인 vector<int>는 별 의미는 없고, 세 번째 인자로 주어지는 comparator가 중요하다. 다음과 같은 comparator class를 넣어주면 정렬 순서를 지정할 수 있다.

물론 저 방법을 쓰지 않고도 앞서 알려준 힙의 기능만으로 풀 수도 있다. 양수들을 저장하는 힙, 음수들을 저장하는 힙, 두 개의 힙을 유지하면 된다. 최솟값을 뽑아야 하므로, 양수에 대해서는 -1을 곱하여 음의 값으로 만들어 넣도록 하자.

#include <bits/stdc++.h>
using namespace std;
 
class comp {
    // < 연산자 역할을 할 수 있는 함수여야 함.
    // 하지만 최소 힙이므로 부등호 방향을 바꾼다.
    public:
    bool operator()(int x, int y) {
        return abs(x) > abs(y) or (abs(x) == abs(y) and x > y);
    }
};
 
priority_queue<int, vector<int>, comp> pq;
 
int main()
{
    int n;
    cin >> n;
    while (n--) {
        int x;
        cin >> x;
        if (x) pq.push(x);
        else {
            if (pq.empty()) cout << "0\n";
            else {
                cout << pq.top() << '\n';
                pq.pop();
            }
        }
    }
}
 

H. 카드 정렬하기

카드를 최소 비용으로 합치기 위해서는 아래 전략에 따르면 됨을 간단히 알 수 있다. 증명은 생략한다.

- 항상 가장 작은 두 묶음의 카드를 합친다.

$N$개의 카드 묶음에서 가장 작은 두 묶음을 합치고 나면 $N-1$개의 카드 묶음이 남게 되고, 다시 이 카드 묶음들 중 가장 작은 두 묶음의 카드를 합쳐 나가면 최소 비용으로 카드를 정렬할 수 있다.

이를 위해서 우선순위 큐를 이용한다.

1. $N$개의 카드 묶음의 크기를 우선순위 큐에 넣는다.

2. 가장 작은 두 수를 뺀다.

3. 그 두 수의 합을 비용에 더하고 다시 우선순위 큐에 넣는다. 2번으로 돌아간다.

4. 1개의 수가 남았을 때, 합치기가 끝났으므로 누적된 최종 비용을 출력한다.

I. 소수의 곱

이 또한 우선순위 큐로 비슷하게 생각하여 풀 수 있다.

1. 우선순위 큐에 먼저 K개의 소수들을 넣는다.

2. 우선순위 큐에서 가장 작은 수 $x$를 뺀다. 그리고 $x$에서 각 소수를 곱한 값들을 다시 우선순위 큐에 넣는다.

3. 2번을 N번째 반복했을 때 나오는 수가 우리가 원하는 결과값이다.

이 때 우선순위 큐에 같은 원소가 중복하여 들어가지 않도록 set 등의 자료구조(검색해 보자!)로 중복 원소를 관리할 수 있다.

J. 컴퓨터실

연속된 빈 자리의 개수를 우선순위 큐에 넣어 관리한다고 생각하면 이 문제 또한 H, I와 같이 특정 연산들을 계속 반복해서 수행하는 문제로 바뀔 것이다. 간단하니 생각해 보자.

K. Pilots

추가 문제로 제시되었는데, 기존의 문제들도 다 못 풀어서 문제를 읽은 사람은 없는 것 같다. ㅎㅎㅎㅎ

E번과 유사한 풀이로 풀리는데, 한 가지 차이점은 구간 길이에 제한이 있는 게 아니라, 구간의 최대 원소 - 최소 원소의 크기에 제한이 있다는 것이다. E와 같이 데크를 최댓값, 최솟값을 위해 두 개 사용한 뒤, 원소를 뺄 때에는 "만료"된 원소를 빼기보다는 "최대 원소 - 최소 원소"가 기준값보다 크게 하는 가장 오래된 값을 삭제하는 방식으로 한다.

Set 등을 사용하는 $O(n \log n)$ 방법으로는 시간 초과가 나게 설정되어 있다.