AtCoder Beginner Contest 217 A부터 E까지 업솔빙

AtCoder Beginner Contest 217 A부터 E까지 업솔빙

AtCoder 최고 퍼포먼스가 나왔다. 아직도 기억나는 퍼포 1183점이고, 이 점수를 환산하면 코드포스 블루 레이팅에 해당하는 1606이다!!. 이런 가끔식 이상치들이 생겨날때 마다 내가 PS를 접지 못하는 이유가 되는 것 같아서 좋아해야할지 말아야할지 모르겠지만 그래도 뭐 어떤가? 인생 목표인 코드포스 rating 블루 or atcoder 1200이상인 목표에 더욱 가까워졌으니 지금을 즐기고 싶다. 참고로 E번까지 전부 출제자 의도에 맞게 풀어서 더욱 기분이 좋다.
이번 대회에서 배운 것은

1. 자료구조 유형 익숙해지기
2. c++의 iterator와 관련된 유용한 함수 prev, next

문제 옆에 붙어있는 난이도는 Atcoder Problems 에서 추정한 것으로 작성했다는 것을 미리 알린다.

A - Lexicographic Order (*21)

접기/펼치기

문제 설명
두개 다른 문자열 $S$와 $T$가 주어진다.
$S$가 사전순으로 $T$보다 작다면 "Yes"를 출력하고 아니면 "No"를 출력하라.

문제 해설
c++에서는 문자열도 부등호로 비교가 가능하고, 부등호 비교가 곧 사전순으로 문자열을 비교하는 행위와 같다. 따라서 그냥 부등호 사용하면 된다.

정답 코드

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    string s, t; cin >> s >> t;
    cout << (s < t ? "Yes" : "No");
    return 0;
}

B - AtCoder Quiz (*22)

접기/펼치기

문제 설명
Atcoder에는 현재 4종류의 대회가 열린다. "ABC", "ARC", "AGC", "AHC"이다.
현재 $S_1$, $S_2$, $S_3$이 열리고 있을때 나머지 대회는 어떤 종류가 열려야 할까?

문제 해설
4개를 모두 set배열에 넣고 등장한 문자열을 set에서 지운다음 set에 남아있는 1개의 원소가 답이다.

정답 코드

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    set<string> s = {"ABC", "ARC", "AGC", "AHC"};
    for(int i = 0; i < 3; i++){
        string str; cin >> str;
        s.erase(str);
    }
    for(auto x : s) cout << x;
    return 0;
}

C - Inverse of Permutation (*49)

접기/펼치기

문제 설명
길이가 $N$인 순열 $P$가 주어진다. 다음 조건을 만족하는 길이가 $N$인 배열 $Q$를 구하라.

• 모든 $i (1 \le i \le N)$에 대해서 $Q$의 $p_i$번째 원소는 $i$이다.

문제 해설
문제에 나와있는 조건을 그대로 코드로 작성하면 된다. $Q$의 $p_i$번째 원소가 $i$이기 때문에 $Q[p_i] = i$ 이 식을 사용하면 끝.

정답 코드

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int n; cin >> n;
    int a[n + 1];
    for(int i = 1; i <= n; i++){
        int num; cin >> num;
        a[num] = i;
    }
    for(int i = 1; i <= n; i++) cout << a[i] << " ";
    return 0;
}

D - Cutting Woods (*802)

접기/펼치기

문제 설명
길이가 $L$인 긴 통나무가 있다.
$x = 1, 2, ..., L - 1$에 대해서 통나무 왼쪽 끝부터 $x$미터에 숫자 $x$가 표시되어 있다.

$i$번째 숫자 쌍이 $(c_i, x_i)$로 이루어진 질의 $Q$개가 주어진다.
숫자 $i$에 따라 아래에 주어진 과정을 질의 순서대로 수행하라.

• $c_i = 1$이면 $x_i$라고 적힌 부분을 잘라서 나무 토막 2개를 만들어라.
• $c_i = 2$이면 $x_i$라고 적힌 부분의 나무 토막을 골라서 그 토막의 길이를 출력하라.

문제 해설
문제를 보자마자는 못풀었지만 워낙 이분 탐색 문제가 자주 나와서 이분탐색을 사용하면 어떨까라는 생각을 하니까 해답이 보이기 시작했다.
결국 통나무를 자르면 해당 숫자에서 그 전에 이미 잘라진 숫자의 차이만큼 길이를 가진 통나무가 남을 것이고 이것을 이용했다.

일단 set에 0하고 통나무의 길이를 넣는다. 그리고 나무가 잘라질때마다 그 숫자를 set에 넣는다. 그리고 길이를 구해야할 숫자가 등장하면 set에서 그 숫자보다 큰 수중에서 가장 작은 값을 찾고, set에서 그 값보다 작은 값중에서 가장 큰 숫자와 그 값의 차이를 출력하면 답이 나온다.

정답 코드

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int l, q; cin >> l >> q;
    set<int> s = {0, l};
    while(q--){
        int c, x; cin >> c >> x;
        if(c == 1) s.insert(x);
        else{
            auto it = s.lower_bound(x);
            cout << *it - *prev(it) << "\n";
        }
    }
    return 0;
}

E - Sorting Queries (*986)

접기/펼치기

문제 설명
빈 배열 $A$가 주어진다. 그리고 질의 $Q$개가 주어진다. 각 질의는 주어진 순서대로 수행해야 하며, 아래에 적혀진 3가지 종류중의 반드시 하나이다.

• 1 x: $A$의 마지막에 $x$를 추가한다.
• 2: $A$의 맨 앞에 있는 값을 출력하고 그 값을 삭제한다. 이 질의가 주어질때 반드시 $A$는 비어있지 않다.
• 3: $A$를 오름차순으로 정렬한다.

문제 해설
마지막 정렬하는 것 때문에 살짝 문제가 꼬았지만 Atcoder에서 우선순위 큐와 큐를 자주 사용한다는 사실을 알았기에 그것을 적절히 조합하면 풀 수 있을 것 같다고 생각을 했고, 실제로 그렇게 하는게 정해였다. 일단 질의 1번 유형과 2번 유형은 누가봐도 큐 자료구조이라는 생각이 날 것이다 그런데 마지막 3번 질의 때문에 꼬인건데 이 3번 질의를 시간 안에 하기 위해서 큐 자료구조와 우선순위 큐 자료구조를 합쳤다. (큐 는 정렬을 할 수 없다.)

우선순위 큐를 앞에 두고 그 뒤에 큐를 둔다고 생각해보자. 일단 1번 질의는 반드시 큐의 맨 뒤에 넣는다. 그리고 2번 질의가 주어졌을 때, 우선순위 큐에 원소가 없다면 큐의 맨 앞을 출력하고 우선순위 큐에 원소가 존재한다면 우선순위 큐의 맨 앞을 출력한다. 마지막으로 3번 질의인데 이것을 그냥 큐에 있는 원소 전부를 우선순위 큐에 넣기만 하면 된다. 우선순위큐는 자동으로 정렬이 되기 때문이다. 다 정렬이 되어있는 상태에서 새로운 원소가 주어져도 상관 없다. 이 원소는 우선순위 큐가 아닌 큐에 들어가기 때문에 정렬이 되지 않는다.

이렇게 하면 앞에 정렬이 되어있는데 새로운 원소가 들어와서 앞에만 정렬이 되어있고 뒤에는 정렬이 안된 상태를 손쉽게 구현할 수 있으며, 전체 원소를 오름차순도 큐에 남아있는 원소만 다 넣으면 되기 때문에 적은 시간으로 수행할 수 있다.

정답 코드

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int Q; cin >> Q;
    queue<int> q;
    priority_queue<int, vector<int>, greater<int>> pq;
    while(Q--){
        int c; cin >> c;
        if(c == 1){
            int x; cin >> x;
            q.push(x);
        }else if(c == 2){
            if(pq.empty()){
                cout << q.front() << "\n";
                q.pop();
            }else{
                cout << pq.top() << "\n";
                pq.pop();
            }
        }else{
            while(q.size()){
                pq.push(q.front());
                q.pop();
            }
        }
    }
    return 0;
}