Murra Blog

BOJ 5430번 AC 문제

덱을 사용해서 푸는 문제인데 입력이 [1,2,3,4] 이런 식으로 주어져서 string을 정수로 변환하는 과정이 필요합니다. 한 자리수가 아니라 두 자리수 이상일 수 있으니 유의해서 풀어야합니다.

배열 원소 개수 n이 0일 때 출력을 신경써야합니다.

5430.cpp

#include <bits/stdc++.h>
using namespace std;
void printD(deque<int> q) {
    cout << '\n';
    for (auto s = q.begin(); s != q.end(); ++s)
        cout << *s << " ";
    cout << '\n';
}

void solve() {
    string func, arr;
    int size;
    cin >> func >> size >> arr;
    int arrSize = arr.size(), num = 0;
    deque<int> deq;

    if (size != 0) {
        for (int i = 1; i < arrSize; ++i) {
            if (arr[i] >= '0' && arr[i] <= '9') {
                num *= 10;
                num += (arr[i] - '0');
            } else {
                deq.push_back(num);
                num = 0;
            }
        }
    }
    int funcSize = func.size();
    bool forward = true;
    for (int i = 0; i < funcSize; ++i) {
        if (func[i] == 'R') {
            forward = !forward;
        } else if (func[i] == 'D') {
            if (deq.empty()) {
                cout << "error\n";
                return;
            }
            if (forward) {
                deq.pop_front();
            } else {
                deq.pop_back();
            }
        }
    }

    cout << "[";
    int deqSize = deq.size();
    if (forward) {
        for (int i = 0; i < deqSize; ++i) {
            cout << deq[i];
            if (i != deqSize - 1) {
                cout << ",";
            }
        }
    } else {
        for (int i = deqSize - 1; i >= 0; --i) {
            cout << deq[i];
            if (i != 0) {
                cout << ",";
            }
        }
    }
    cout << "]\n";
}

int main() {
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
}

BOJ 1021번 문제

덱을 사용해서 푸는 문제였습니다. 2번 연산과 3번 연산 중 어떤 연산을 통해 뽑아내는게 더 적은 연산을 하는지 계산하는 것만 신경 쓰면 풀 수 있었습니다.

1021.cpp

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

void printD(deque<int> q) {
    cout << '\n';
    for (auto s = q.begin(); s != q.end(); ++s)
        cout << *s << " ";
    cout << '\n';
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int size;
    cin >> size;
    deque<int> d;
    int count = 0;

    for (int i = 0; i < size; ++i) {
        d.push_back(i + 1);
    }

    int n;
    cin >> n;
    for (int i = 0; i < n; ++i) {
        int location;
        cin >> location;

        //printD(d);

        if (location == d.front()) {
            d.pop_front();
            continue;
        }
        int gap = 0;
        for (auto s = d.begin(); s != d.end(); ++s) {
            if (*s == location) {
                break;
            }
            gap++;
        }
        // 2를 하는게 최솟값
        if (gap <= (d.size() / 2)) {
            for (int j = 0; j < gap; ++j) {
                d.push_back(d.front());
                d.pop_front();
                count++;
                //cout << "2 ";
            }
            d.pop_front();
        }
        // 3을 하는게 더 최솟값
        else {
            gap = d.size() - gap;
            for (int j = 0; j < gap; ++j) {
                d.push_front(d.back());
                d.pop_back();
                count++;
                //cout << "3 ";
            }
            d.pop_front();
        }
    }
    cout << count;
}

BOJ 16719번 ZOAC 문제

주석에 설명 적었습니다.

O(N^3)으로 풀수 있다는데 이해가 직관적이지 않아서 재귀를 써서 풀어봤습니다.

16719.cpp

#include <bits/stdc++.h>
using namespace std;
#define INF 260
bool visited[101];
string s;
int sSize;
void solve(int, int);
char getSmallIndex(int, int);

int main() {
    cin >> s;
    sSize = s.size();
    solve(0, sSize - 1);
}

void solve(int l, int r) {
    int index = getSmallIndex(l, r);  // 현재 고르지 않은 문자 중 가장 작은 값의 Index
    if (index == -1) return;          // 모든 문자를 골랐을 경우 탈출
    visited[index] = true;            // 고른 문자 재사용 하는 일 없게 true

    // true인 문자는 순서대로 출력
    for (int i = 0; i < sSize; i++) {
        if (visited[i])
            cout << s[i];
    }
    cout << '\n';
    solve(index + 1, r); // 가장 작은 값을 골랐기 때문에 우측, 좌측 순으로 호출한다.
    solve(l, index - 1);
}

char getSmallIndex(int l, int r) {
    int small = 999;
    int index = -1;
    for (int i = l; i < r + 1; i++) {
        if (s[i] < small && !visited[i]) {
            small = s[i];
            index = i;
        }
    }
    return index;
}

BOJ 2503번 숫자 야구 문제

코드에 주석을 달았다. 서로 다른 숫자 세 개로 구성된 점과 0을 제외한 1-9 사이의 숫자임에 유의해서 풀면 된다.

2503.cpp

#include <bits/stdc++.h>
using namespace std;
#define NUMBERSIZE 3
int result;
int test;
struct question {
    string num;
    int strike;
    int ball;
};
vector<question> questionV;

int main() {
    int n;
    question input;
    cin >> n;

    for (int i = 0; i < n; i++) {
        cin >> input.num >> input.strike >> input.ball;
        questionV.push_back(input);
    }

    for (int i = 123; i <= 987; i++) {
        string target = to_string(i);
        test = 0;
        // 숫자가 0 일 경우 continue, 중복 숫자가 있을 경우 continue.
        if (target[0] == '0' || target[1] == '0' || target[2] == '0' || target[0] == target[1] || target[1] == target[2] || target[2] == target[0]) {
                continue;
        }

        for (int j = 0; j < n; j++) {
            int targetStrike, targetBall;
            targetStrike = targetBall = 0;
            for (int k = 0; k < NUMBERSIZE; k++) {
                // 같은 자리일때 Strike를 증가
                if (target[k] == questionV[j].num[k])
                    targetStrike++;
                // 다른 자리의 숫자일때 Ball을 증가
                if (target[k] == questionV[j].num[(k + 1) % NUMBERSIZE] || target[k] == questionV[j].num[(k + 2) % NUMBERSIZE])
                    targetBall++;
            }
            // Strike, Ball의 수가 같을 때 test의 값을 증가.
            if (questionV[j].strike == targetStrike && questionV[j].ball == targetBall) {
                test++;
            }
        }
        // 모든 경우에 대해 가능한 숫자일 경우 결괏값을 증가.
        if (test == n) {
            result++;
        }
    }
    cout << result;
}

BOJ 1213번 팰린드롬 만들기 문제

코드에 주석을 달았다. 홀수번 등장하는 알파벳이 두 개 이상이면 팰린드롬을 만들 수 없다.

1213.cpp

#include <bits/stdc++.h>
#define ALPHABET 26
using namespace std;
int alphabet[ALPHABET];
string result;
int main() {
    string input;
    cin >> input;
    int input_size = input.size();
    for (int i = 0; i < input_size; i++) {
        alphabet[input[i] - 'A']++;
    }
    int odd_index, odd;
    odd_index = -1;
    odd = 0;
    for (int i = 0; i < ALPHABET; i++) {
        if (alphabet[i] % 2 == 1) {
            odd++;
            odd_index = i;
        }
    }
    // 홀수번 등장한 알파벳이 2개 이상이면 만들 수 없다.
    if (odd > 1) {
        result = "I\'m Sorry Hansoo";
    }
    // 홀수번 등장한 알파벳이 1번이면 
    // AAABBBA -> AABBBAA
    else if (odd == 1) {
        char odd_char = odd_index + 'A';
        // temp : 홀수번 등장한 알파벳을 제외한 string 저장.
        // AAABBBA -> AAABBA, odd_char = 'B'
        string temp = "";
        bool do_once = true;
        for (int i = 0; i < input_size; i++) {
            if (do_once && input[i] == odd_char) {
                do_once = false;
                continue;
            }
            temp += input[i];
        }
        // temp = AAAABB
        // half = AAB
        sort(temp.begin(), temp.end());
        string half = "";
        int temp_size = temp.size();
        for (int i = 0; i < temp_size; i += 2) {
            half += temp[i];
        }
        result = half + odd_char;
        // half = BAA
        reverse(half.begin(), half.end());
        result += half;
    }
    // 모두 짝수번 등장. 
    // ABAABA -> AABBAA
    else {
        sort(input.begin(), input.end());
        string half = "";
        for (int i = 0; i < input_size; i += 2) {
            half += input[i];
        }
        result += half;
        reverse(half.begin(), half.end());
        result += half;
    }
    cout << result;
}

BOJ 1072번 게임 문제

이분탐색으로 풀면 된다. 99%일때 예외 경우를 따로 해줘야한다. 1패라도 있으면 승률이 100%가 될 수 없다.

1072.cpp

#include <bits/stdc++.h>
#define MAX_ 1000000000
using namespace std;
typedef long long ll;
int main() {
    ll x, y, z, low, high, mid, test_z;
    cin >> x >> y;
    z = 100 * y / x;
    if (z >= 99) {
        cout << -1;
        return 0;
    }

    low = 0;
    high = MAX_;

    while (low <= high) {
        mid = (low + high) / 2;
        test_z = 100 * (y + mid) / (x + mid);
        if (z < test_z) {
            high = mid - 1;
        } else {
            low = mid + 1;
        }
    }
    cout << low;
}

BOJ 10539번 수빈이와 수열

수열 B가 3, 2, 3, 5일 떄

1. 3 = 3/1

2. 2 = (3+x)/2 에서 x = 1

3. 3 = (3+x+y)/3 에서 y = 5

4. 5 = (3+x+y+z)/4 에서 z = 11

10539.cpp

#include <bits/stdc++.h>
using namespace std;
int arr[101];
int res[101];
int main() {
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> arr[i];
    }
    int plus = 0;
    res[1] = arr[1];
    for (int i = 2; i <= n; i++) {
        plus = 0;
        for (int j = 1; j <= i; j++) {
            plus += res[j];
        }
        res[i] = arr[i] * i - plus;
    }
    for (int i = 1; i <= n; i++) {
        cout << res[i] << ' ';
    }
}