취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 29338번 문제인 Склад Оби-Вана Кеноби이다.
문제는 아래 링크를 확인하자.

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

앞 절반의 원소를 들고 있는 덱과 뒤 절반의 원소를 들고 있는 덱을 관리하자.

자료를 이렇게 관리하면 주어지는 모든 쿼리를 \(O(1)\)에 어렵지 않게 처리할 수 있게 되므로 문제를 간단히 해결할 수 있다.

아래는 제출한 소스코드이다.

#include <iostream>
#include <deque>
#include <utility>
#include <string>
using namespace std;

int Q;
deque<int> L, R;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> Q;
    while (Q--) {
        string s; cin >> s;
        if (s.front() == 'a') {
            int x; cin >> x;
            R.push_back(x);
        }
        else if (s.front() == 't') {
            if (!R.empty()) R.pop_back();
        }
        else swap(L, R);
        while (L.size() > R.size()) R.push_front(L.back()), L.pop_back();
        while (L.size() + 1 < R.size()) L.push_back(R.front()), R.pop_front();
    }

    cout << L.size() + R.size() << '\n';
    for (auto &x:L) cout << x << ' ';
    for (auto &x:R) cout << x << ' ';
}

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 29343번 문제인 Шифровка이다.
문제는 아래 링크를 확인하자.

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

주어지는 문자열에 대하여, 1 이상 전체 길이 이하의 같은 길이의 접두사와 접미사 쌍 중 1개 이상의 모음을 포함하면서 같은 개수의 모음을 포함하는 쌍의 개수를 구하는 문제이다.

이는 각 접두사마다 모음이 몇 개 있는지, 접미사마다 모음이 몇 개 있는지를 이용해 어렵지 않게 계산할 수 있다.

길이가 \(k>1\)인 접두사에 포함된 모음의 개수는 길이가 \(k-1\)인 접두사에 포함된 모음의 개수와 \(k\)번째 문자의 모음 여부로 구할 수 있다는 점을 활용하자.

아래는 제출한 소스코드이다.

#include <iostream>
#include <string>
using namespace std;

int N, val1, val2, ans;
string s;
int isvowel[128];

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    isvowel['a'] = isvowel['e'] = isvowel['i'] = isvowel['o'] = isvowel['u'] = 1;
    isvowel['A'] = isvowel['E'] = isvowel['I'] = isvowel['O'] = isvowel['U'] = 1;
    cin >> N >> s;
    for (int L = 0, R = N - 1; L < N; L++, R--) {
        val1 += isvowel[s[L]], val2 += isvowel[s[R]];
        if (val1 && val1 == val2) ans++;
    }
    cout << ans;
}

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 33689번 문제인 CPDU이다.
문제는 아래 링크를 확인하자.

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

입력으로 주어지는 문자열 중 문자 'C'로 시작하는 것의 개수를 세어 출력하는 문제이다.

string으로 입력을 받고 그 첫번째 문자를 확인하는 것으로 위의 작업을 간단하게 구현할 수 있다.

아래는 제출한 소스코드이다.

#include <iostream>
using namespace std;

int T, ans;
string s;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> T;
    while (T--) {
        cin >> s;
        if (s.front() == 'C') ans++;
    }
    cout << ans;
}

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 33690번 문제인 포린드롬이다.
문제는 아래 링크를 확인하자.

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

먼저 한 자리 수(0 포함)는 주어진 조건을 항상 만족함을 관찰하자.

주어지는 조건을 만족하는 한 자리 이상의 수는 "두 자리 이상이면서 마지막 자리를 지운 수와 원래 수가 모두 팰린드롬인 수"로 해석할 수 있다. 한편, 두 수에서 서로 대응되는 위치에 있는 각 숫자의 쌍을 연결하면 이 조건을 만족하는 수를 구성하는 숫자가 모두 동일해야 함을 알 수 있다.

이러한 수는 몇 없으므로, \(N\) 이하의 수 중 이러한 수를 모두 생성하는 것으로 주어진 수 이하인지 확인하는 것으로 문제를 해결할 수 있다. 이는 111...1 꼴의 수에 1 이상 9 이하의 정수를 곱하는 것으로 모두 얻을 수 있다.

아래는 제출한 소스코드이다.

#include <iostream>
using namespace std;

int N, ans = 1;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    cin >> N;
    for (int i = 1; i < 1000000000; i = i * 10 + 1) {
        for (int k = 1; k < 10; k++) {
            if (i * k <= N) ans++;
        }
    }
    cout << ans;
}

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 21275번 문제인 폰 호석만이다.
문제는 아래 링크를 확인하자.

https://www.acmicpc.net/probelm/21275

주어진 두 수를 2진수부터 36진수까지 각각의 진법으로 해석한 값을 먼저 계산해두자. 그리고 각각의 진법 쌍에 대하여 두 값이 같은지를 확인해 문제를 해결하자.

조건에 따라 두 진법이 서로 같으면 안 되며 각각의 값이 \(2^{63}\) 미만이어야 한다는 점에 유의하자.

아래는 제출한 소스코드이다.

#include <iostream>
using namespace std;
typedef long long ll;
typedef __int128 lll;

lll MX = 9223372036854775807LL;
lll A[37], B[37];
string s;
ll aval, aidx, bidx, cnt;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> s;
    for (int b = 2; b < 37; b++) {
        for (auto &l:s) {
            int x;
            if ('0' <= l && l <= '9') x = l - '0';
            else x = 10 + l - 'a';
            if (x >= b) {
                A[b] = -1;
                break;
            }
            A[b] = A[b] * b + x;
            if (A[b] > MX) {
                A[b] = -1;
                break;
            }
        }
    }
    cin >> s;
    for (int b = 2; b < 37; b++) {
        for (auto &l:s) {
            int x;
            if ('0' <= l && l <= '9') x = l - '0';
            else x = 10 + l - 'a';
            if (x >= b) {
                B[b] = -1;
                break;
            }
            B[b] = B[b] * b + x;
            if (B[b] > MX) {
                B[b] = -1;
                break;
            }
        }
    }

    for (int i = 2; i < 37; i++) {
        for (int j = 2; j < 37; j++) {
            if (i != j && A[i] == B[j] && A[i] >= 0) aval = A[i], aidx = i, bidx = j, cnt++;
        }
    }

    if (cnt > 1) cout << "Multiple";
    else if (cnt == 1) cout << aval << ' ' << aidx << ' ' << bidx;
    else cout << "Impossible";
}

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 33574번 문제인 끊임없는 정렬과 창조함으로이다.
문제는 아래 링크를 확인하자.

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

주어지는 쿼리의 수가 3000 이하이므로 각 쿼리가 주어질 때의 배열의 크기 \(N\)은 3000 이하이다. 또한 크기가 \(N\)인 배열을 정렬하는 것은 \(O(N\lg N)\)의 시간복잡도로, 원소를 삽입하는 것은 \(O(N)\)의 시간복잡도로 수행할 수 있으므로 주어진 쿼리를 곧이곧대로 수행하는 시간복잡도는 \(O(N^2\lg N)\)이 되며, 이는 문제를 해결하기에 충분한 시간복잡도이다.

더 좋은 복잡도로 문제를 해결할 수도 있다. 정렬을 한번 수행하면 앞서 원소를 어디에 삽입했는지나 정렬을 했었는지 여부에 관계없이 항상 일정한 결과를 얻을 수 있다는 점을 이용하면 정렬을 단 한번만 수행해도 됨을 관찰하자. 또한, 이후 원소삽입과정은 세그먼트 트리 등의 자료구조를 이용하여 각 원소의 삽입될 위치를 관리하는 것으로 한번에 갱신해줄 수 있다.

아래는 제출한 소스코드이다.

#include <iostream>
#include <algorithm>
using namespace std;

int Q, N;
int A[3000];

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> Q;
    while (Q--) {
        int q; cin >> q;
        if (q == 1) {
            cin >> q;
            if (q == 1) sort(A, A + N);
            else sort(A, A + N, greater<>());
        }
        else {
            int x, t; cin >> x >> t;
            for (int i = N - 1; i >= x; i--) A[i + 1] = A[i];
            A[x] = t;
            N++;
        }
    }
    cout << N << '\n';
    for (int i = 0; i < N; i++) cout << A[i] << ' ';
}