Codeforces Round #604 (Div. 2)

문제 링크 : https://codeforces.com/contest/1265

 

A. Beautiful String

문제 요약

'?'을 'a', 'b', 'c' 중 하나로 치환하여 인접한 두 문자가 같지 않도록 만들 수 있는지 확인하고, 가능하면 그 값을 출력하는 문제이다.

 

접근 방법

문자열이 A[1]부터 A[N]까지 있다고 하면(N은 입력받은 문자열의 길이), A[0]과 A[N+1]에는 더미 문자를 미리 삽입하면 A[1]과 A[N]에서도 양 옆의 문자열을 확인하면 되므로 따로 처리를 할 필요가 없어진다고 생각하였다.

 

시간복잡도

이미 입력 받은 값이 불가능한 값인지 체크하는 부분이 O(n)이고, 값을 생성하는 부분이 O(n)이므로 총 O(n)이 걸린다고 생각한다.

#include <iostream>
#include <cstring>

using namespace std;

void solution(string& s) {
    for(int i = 1; i < s.length() - 2; i++) {
        if(s[i] == s[i+1] && s[i] != '?') { //물음표가 아니면서 둘 다 값이 같으면 불가능
            cout << "-1" << endl;
            return;
        }
    }
    
    for(int i = 1; i < s.length() - 1; i++) {
        if(s[i] == '?') {
            if(s[i+1] == '?' || s[i-1] == s[i+1]) {
                s[i] = s[i-1] + 1;
                if (s[i] > 'c') s[i] = 'a';
            } else {
                s[i] = 'a' + 'b' + 'c' - (s[i-1] + s[i+1]);
                if(s[i] < 'a') s[i] = 'a';
            }
        }
    }
    for(int i = 1; i < s.length() - 1; i++) { //A[0]과 A[N+1]은 더미 값이므로 출력 안 함
        printf("%c", s[i]);
        if(i == s.length() - 2) printf("\n");
    }
}

int main(void) {
    int T;
    cin >> T;
    for(int i = 0; i < T; i++) {
        string s, t;
        cin >> t;
        s += "c"; //A[0]
        s += t; //A[1]...A[N]
        s += "c"; //A[N+1]
        solution(s);
    }
    return 0;
}

 

C. Beautiful Regional Contest

문제 요약

어떤 대회에서 금, 은 그리고 동상을 줄 사람을 나누어야 하는데, 줄 수 있다면 얼마나 줄 수 있는지 확인하는 문제이다.

 

접근 방법

금상의 개수가 은, 동상보다 적어야 하는데, 은상과 동상에는 상관관계가 없고, 금+은+동상의 총합을 최대한 많이 주라는 것에서 착안하여, 금상과 은상을 최소로 주고 나머지를 동상으로 주면 된다고 생각하였다.

 

시간복잡도

금상, 은상 수상자를 체크하는데 각각 O(n)이 들며, 동상은 (전체 수상자 - 금상 수상자 - 은상 수상자)로 구하면 되므로 O(1)이다. 총 O(n).

#include <iostream>
#include <vector>


using namespace std;

void solution(vector<int>& V) {
    if(V.size() < 10) {
        printf("0 0 0\n"); //최소 10명이 참가해야 반인 5명을 줄 수 있으므로(g<s, g<b를 만족하려면)
        return;
    }
    
    int m = V.size() / 2;
    while(m > 0) {
        if(V[m] < V[m-1]) //자른 부분의 바로 위 등수를 확인하여, 점수가 같으면 동점이므로 수상 불가
            break;
        m--;
    }
    
    int g = 1;
    while(g < m) {
        if(V[g] < V[g-1]) break; //다음 등수의 점수가 현재보다 낮으면 커트
        g++;
    }
    
    int s = g+g+1;
    while(s < m) {
        if(V[s] < V[s-1]) break;
        s++;
    }
    s -= g;
    
    int b = m - g - s;
    if(g < s && g < b)
       printf("%d %d %d\n", g, s, b);
    else printf("0 0 0\n");
    
}

int main(void) {
    int T;
    cin >> T;
    for(int t = 0; t < T; t++) {
        int L;
        cin >> L;
        vector<int> V;
        V.reserve(L);
        for(int l = 0; l < L; l++) {
            int t;
            scanf("%d", &t);
            V.push_back(t);
        }
        solution(V);
    }
}

 

D. Beautiful Sequence

문제 요약

0, 1, 2, 3으로 이루어진 문자열을 두 인접한 문자가 1씩 차이가 나도록 문자열을 만들 수 있는지 확인하는 문제이다.

 

접근 방법

0과 2를 먼저 써두고, 1과 3을 어디에 넣을 수 있는지 체크하면 어렵지 않았다. 1은 X-0, 0-0, 0-2, 2-2, 2-X 사이에 모두 들어가지만, 3은 X-2, 2-2, 2-X 에만 들어갈 수 있기 때문에 이 점을 유의하여 구분하였다.

 

시간복잡도

미리 불가능한 답안을 모두 거르는데는 O(1)이 소요되고, 답을 생성하는 데 O(n)이 걸리므로 O(n)이 소요된다.

#include <iostream>

using namespace std;

void solution(int data[]) {
    if((data[0] > 0 && data[3] > data[2]) ||
       (data[2] > 0 && data[0] > data[1]) ||
       data[1] + data[3] < data[0] + data[2] - 1 ||
       data[1] + data[3] > data[0] + data[2] + 1) { 
        cout << "NO" << endl;
        return;
    }

    int length = data[0] + data[1] + data[2] + data[3];
    
    int r[100000] = {0};
    
    int first = 0;
    if(data[1] + data[3] > data[0] + data[2]) { //1이 먼저냐 0이 먼저냐
            //1이 먼저다
            first = 1;
    }
    
    for(int i = 0; i < length; i++) {
        if(i % 2 == 0) {
            if(data[first] > 0) {
                r[i] = first;
                data[first]--;
            }
            else r[i] = first + 2;
        } else {
            if(data[(first + 1) % 2] > 0) {
                r[i] = (first + 1) % 2;
                data[(first + 1) % 2]--;
            }
            else r[i] = ((first + 1) % 2) + 2;
        }
    }
    cout << "YES" << endl;
    for(int i = 0; i < length; i++) {
        cout << r[i] << " ";
    }
    
}

int main(void) {
    int input[4];
    cin >> input[0] >> input[1] >> input[2] >> input[3];
    solution(input);
    return 0;
}

 

총평

B번은 아무리 생각해도 O(n^2)인 풀이밖에 생각이 나지 않아, 풀이를 보았다 흑흑..

그리고 드디어 다음주가 휴가다!! 휴가 나가면 내 노트북으로 풀어야지 ㅠㅅㅠ