[SW Expert Academy] Code Battle!

매주 화요일에 열리는 코드 배틀!

오늘도 참여했습니다.

언제나처럼 2 문제를 풀었습니다. 핫핫

SW Expert Academy의 문제는 무단 복제가 금지되어 있기 때문에 링크로 대체합니다!

클릭시 이동합니다!!

No. 1 이진 문자열 복원

어떻게 풀까?

해당 문제는 00, 01, 10, 11의 개수가 주어졌을 때, 만들 수 있는 이진 문자열을 아무거나 출력하면 됩니다!

두 문자 00, 01, 10, 11을 1번 문자, 2번 문자, 3번 문자, 4번 문자라고 하겠습니다!

문자열을 이어보면, 이진 문자열의 끝에 따라서 다음에 몇 번 문자가 오는지 알 수 있습니다.

그림에서 보듯이, 문자의 끝이 1이라면 뒤에 10 혹은 11이 와야합니다!

문자의 끝이 0이라면, 00, 01 문자가 와야합니다.

또한, 1번, 2번, 3번, 4번 문자는 각각 20개를 넘지 않는다는 것입니다.

모든 경우의 수를 살펴보아도 최대 160000 번이라는 것이죠.

엇! 이렇게 보니 1번 문자가 1개 있을 때, 2번 문자가 1개 있을 때, 3번 문자가 1개 있을 때를 베이스로 해서

만들어갈 수 있는 문자를 bfs로 돌리면서 문자를 하나씩 늘린다면, 모든 경우의 수를 찾을 수 있을 것 같습니다! 

이런 식으로 하나씩 하나씩 늘려주면서 모든 경우의 수를 배열[00 개수][01 개수][10 개수][11 개수]인 4차원 배열에 정리해 놓으면,

바로바로 찾을 수 있을 것입니다!

위로 예를 들면 배열[1][0][0][1] 을 하면 바로 011을 찾아주겠죠!

아무거나 출력하면 되기 때문에 4 차원 배열에 이미 무언가 채워져 있다면 깔끔하게 무시하면 될 것 같습니다.

라고 생각하면 함정에 빠진 겁니다.

위를 보시면, 맨 끝의 글자가 0인지 1인지에 따라서 갈 수 있는 경로가 달라지는 것을 볼 수 있습니다!

따라서, 끝이 0인지 1인지도 확인하기 위해 배열[2][00 문자 개수][01 문자 개수][10 문자 개수][11 문자 개수]의 오차원 배열을 이용합시다!

참고로 이건 스타일에 따라서 다른데, 저는 문자열 대신 '경로'를 이용했습니다.

0110을 예로 들면, 위 그림 처럼 배열[0][0][1][1][1]에 "0110"이라는 문자열 대신에 끝이 문자 10으로 끝난다는 3을 넣은 것 입니다!

그럼 이 경로를 이용해서 어떻게 문자를 찾는지 확인해 보겠습니다.

그림에서 볼 수 있듯이 뒷 글자가 3번 문자라고 저장해놨기 때문에 맨 뒤 문자 하나를 제거하면, 3번 문자가 제거될 것입니다.

그리고, 3번 문자이기 때문에 다음 맨 뒷글자는 1이 되겠죠!

따라서, 0110 이진 문자는 path[1][0][1][0][1]에서 파생되었음을 알 수 있는 것입니다!

마찬가지로 path[1][0][1][0][1]은 4번 문자이기 때문에, 끝에는 1이 저장되어 있음을 알 수 있습니다.

결과 문자에 1을 저장하고, 맨 뒤 문자를 하나 떼어낸다면, 다음 문자의 끝은 1일 것입니다.

0100은 기본 문자입니다!

다른 것이 없어도 2번 문자는 01 이라는 것을 알 수 있죠!

따라서, 결과 문자는 0110이 되는 것입니다!

코드

#pragma once
#include<cstdio>
 
char res[2][21][21][21][21];
char path[2][21][21][21][21];
char que[20 * 20 * 20 * 20][6];
 
int main() {
    int t;
    scanf("%d\n", &t);
    
    int f = 0, r = 0;
    
    que[r][0] = 1;
    que[r][1] = 0;
    que[r][2] = 0;
    que[r][3] = 0;
    que[r][4] = '0';
    que[r++][5] = 1;
 
    que[r][0] = 0;
    que[r][1] = 1;
    que[r][2] = 0;
    que[r][3] = 0;
    que[r][4] = '1';
    que[r++][5] = 2;
 
    que[r][0] = 0;
    que[r][1] = 0;
    que[r][2] = 1;
    que[r][3] = 0;
    que[r][4] = '0';
    que[r++][5] = 3;
 
    que[r][0] = 0;
    que[r][1] = 0;
    que[r][2] = 0;
    que[r][3] = 1;
    que[r][4] = '1';
    que[r++][5] = 4;
 
    res[0][1][0][0][0] = '0';
    res[0][0][1][0][0] = '1';
    res[0][0][0][1][0] = '0';
    res[0][0][0][0][1] = '1';
    res[1][1][0][0][0] = '0';
    res[1][0][1][0][0] = '0';
    res[1][0][0][1][0] = '1';
    res[1][0][0][0][1] = '1';
 
    while (f != r) {
        int now[6] = { que[f][0], que[f][1], que[f][2], que[f][3], que[f][4], que[f][5] };
        f++;
 
 
        if (now[4] =='0') {
            if (now[0] != 20 && res[0][now[0] + 1][now[1]][now[2]][now[3]] == 0) {
                res[0][now[0] + 1][now[1]][now[2]][now[3]] = '0';
                path[0][now[0] + 1][now[1]][now[2]][now[3]] = 1;
                que[r][0] = now[0]+1;
                que[r][1] = now[1];
                que[r][2] = now[2];
                que[r][3] = now[3];
                que[r][4] = '0';
                que[r++][5] = 1; 
            }
 
            if (now[1] != 20 && res[1][now[0]][now[1]+1][now[2]][now[3]] == 0) {
                res[1][now[0]][now[1]+1][now[2]][now[3]] = '1';
                path[1][now[0]][now[1]+1][now[2]][now[3]] = 2;
                que[r][0] = now[0];
                que[r][1] = now[1]+1;
                que[r][2] = now[2];
                que[r][3] = now[3];
                que[r][4] = '1';
                que[r++][5] = 2;
            }
        }
 
        if (now[4] =='1') {
            if (now[2] != 20 && res[0][now[0]][now[1]][now[2]+1][now[3]] == 0) {
                res[0][now[0]][now[1]][now[2]+1][now[3]] = '0';
                path[0][now[0]][now[1]][now[2]+1][now[3]] = 3;
                que[r][0] = now[0];
                que[r][1] = now[1];
                que[r][2] = now[2] + 1;
                que[r][3] = now[3];
                que[r][4] = '0';
                que[r++][5] = 3;
            }
 
            if (now[3] != 20 && res[1][now[0]][now[1]][now[2]][now[3]+1]==0) {
                res[1][now[0]][now[1]][now[2]][now[3]+1] = '1';
                path[1][now[0]][now[1]][now[2]][now[3]+1] = 4;
                que[r][0] = now[0];
                que[r][1] = now[1];
                que[r][2] = now[2];
                que[r][3] = now[3] + 1;
                que[r][4] = '1';
                que[r++][5] = 4;
            }
        }
    }
 
    for (int tc = 1; tc <= t; tc++) {
        char rc[100];
        int len = 0;
        rc[0] = 0;
        int cmp[5];
 
        scanf("%d %d %d %d\n", &cmp[1], &cmp[2], &cmp[3], &cmp[4]);
        
        int now = -1;
        now = res[0][cmp[1]][cmp[2]][cmp[3]][cmp[4]] < res[1][cmp[1]][cmp[2]][cmp[3]][cmp[4]] ? res[1][cmp[1]][cmp[2]][cmp[3]][cmp[4]] : res[0][cmp[1]][cmp[2]][cmp[3]][cmp[4]];
 
        if (now == 0) {
            printf("#%d impossible\n", tc);
            continue;
        }
 
        now -= '0';
        while (cmp[1] + cmp[2] + cmp[3] + cmp[4] != 1) {
            rc[++len] = res[now][cmp[1]][cmp[2]][cmp[3]][cmp[4]];
            int temp = now;
            now =path[now][cmp[1]][cmp[2]][cmp[3]][cmp[4]] > 2 ;
            cmp[path[temp][cmp[1]][cmp[2]][cmp[3]][cmp[4]]]--;
        }
 
        rc[++len] = res[0][cmp[1]][cmp[2]][cmp[3]][cmp[4]];
        rc[++len] = res[1][cmp[1]][cmp[2]][cmp[3]][cmp[4]];
        printf("#%d ", tc);
        for (int i = len; i > 0; i--) {
            printf("%c", rc[i]);
        }
        printf("\n");
    }
 
    return 0;
}

여담

미리 이진 문자를 계산해 놓기 때문에 시간은 O(1)입니다!

No. 2 흘러라 시간! 딴 짓 하기

어떻게 풀까?

첫번째 행의 역할이 매우 중요합니다.

우선, 조건을 살펴봅시다.

열을 지워야 하지만, 지운 후에 1 번째, 2 번째, 3 번째 행렬에서 '모든 수가 같아야 합니다.' 

세 개의 행 중에서 가장 조건이 타이트한 것은 첫 번째 행렬입니다.

따라서, 이 문제는 어떻게하면 2번과 3번 행을 1번 처럼 만들 수 있을까? 고민하면 되는 문제입니다.

첫 번째 행은 1~N까지의 수가 딱 하나씩 놓여있습니다.

두 번째와 세 번째 행은 1~N의 수가 중복되어서 써질 수 있습니다.

중복되서 써진다와 딱 하나씩만 써진다는 것의 차이란 무엇일까요?

카운팅을 해 보면 명확하게 알 수 있습니다.

위와 같은 행렬이 있다고 합시다!

이제, 각 행에서 1의 개수 부터 N의 개수를 세 보는 것입니다!

이렇게 세 보면, 2번 행에는 2와 6이 없다는 것을 알 수 있습니다.

그리고 1과 5가 2개씩 있다는 것을 알 수 있죠!

우리가 첫번째 행과 두번째 행을 같게 만들기 위해서는, 행에서 중복되는 부분과 없는 부분을 삭제해 주어야 한다는 것이죠!!

위 그림에서는 1, 2, 5, 6을 조절해 주어야 겠죠.

엇! 그런데 없는 것은 2와 6 2개.... 중복되는 것은 1과 5 2개...

수상한 냄새가 나지 않습니까!?

간단한 이유입니다! N개의 열에서 1부터 N까지 하나씩만 써야하는데, 중복이 1개가 되면 그만큼 없는 것이 1개가 늘어난다는 것이겠죠.

있어야할 2가 1이 되어서 1은 2개가 되고 2는 0개가 됬다. 라고 생각하시면 될 것 같습니다.

자! 그럼 여기서 어떻게 조절하면 될지 생각해 보아야 합니다.

확실한 것은, 0개인 부분은 첫 번째 행에서도 나와선 안된다는 사실이죠!

즉, 첫 번째 행에서도 2와 6을 없애야 한다는 것입니다!

첫 번째 행은 모든 수가 1개씩만 있기 때문에, 2와 6을 삭제하기도 다른 행에 비해선 훨씬 간단하죠!

첫 번째 행에서 2와 6을 제거한다는 것은, 2번째 행에서는 1과 4, 3번째 행에서는 4와 6을 제거하는 것이기도 합니다!

해당 수들을 제거해 봅시다.

첫 번째 행에서 2와 6을 제거했더니, 2번째 행과 3번째 행에서 4가 사라져 버렸습니다! 따라서 첫번째 행에서 4도 같이 제거해줘야겠죠!

2번째 행에서 5 1개, 3번째 행에서 7을 지워줍시다.

이럴수가! 7번 행도 지워야 하는 상황이 되었습니다.

2번 행에서 7, 3번 행에서 2를 지웁시다.

아닛! 0이 된 것을 지우기만 했는데, 깔끔하게 정답이 나와버렸습니다!

왜 그런 것일까요?

비둘기집의 원리 라고 보시면 될 것 같습니다.

중복되는 것이 2개가 있다는 것은 0이 된 것이 2개가 된다는 것이겠죠!

하지만, 0이 되면서 지우게 되는 수들을 지웠는데, 중복되는 것을 지우지 못한다면?

원래 정상적이었던 수를 건드리게 된다는 것이고, 지우지 못한 중복수 만큼 0개가 되버리는 수가 늘어나겠죠!

그리고 그 0이 된 수들은, 해당 수를 꼭 추가적으로 지워야 한다는 것을 의미합니다.

그리고 위 2개의 표에서 7의 개수를 확인해 봅시다! 2번째 행에서 7이 0으로 떨어졌죠!

하지만, 이미 7은 지워야 한다고 선언된 상태입니다!

따라서, 2번째 행에서 7이 0으로 된 것은 목표하는 상태가 된 것이기 때문에 추가적인 작업을 하지 않아도 됩니다.

이렇게 되면, 어떻게 프로그래밍을 해야하는지 감을 잡을 수 있습니다!

처음에 0인 개수를 큐에 넣고, 큐에서 0이된 수들을 빼면서, 첫번째 행에서 해당 수와 연관된 2번째 행과 3번째 행의 수들의 개수를 하나씩 지웁니다!

만약, 하나씩 지웠는데 해당 수가 0이 됐고, 아직 첫번째 행에 남아있는 수라면 위 과정을 다시 반복합니다.

이 것을 큐가 비워질때까지 하면, 지금까지 지웠던 개수가 바로 정답이 됩니다!

BFS를 이용하는 문제였군요!!

코드

#pragma once
#include<cstdio>
#include<cstring>
int check[3][100001];bool inque[100001];
int info[3][100001];
int idx[100001], temp[1000001];
int que[100000], f, r;
 
 
void merge(int left, int right) {
    if (left < right) {
        int m = (left + right) / 2;
 
        merge(left, m);
        merge(m + 1, right);
 
        int l = left, r = m + 1, k = l;
 
        while (l <= m && r <= right) {
            temp[k++] = info[0][idx[l]] < info[0][idx[r]] ? idx[l++] : idx[r++];
        }
        while (l <= m) temp[k++] = idx[l++];
        while (r <= right) temp[k++] = idx[r++];
 
        for (int i = left; i <= right; i++) {
            idx[i] = temp[i];
        }
    }
}
 
int main() {
    int t;
    scanf("%d\n", &t);
 
    for (int tc = 1; tc <= t; tc++) {
        int n;
        scanf("%d\n", &n);
        memset(check, 0, sizeof(check));
        memset(inque, false, sizeof(inque));
        for (int i = 1; i <= n; i++) idx[i] = i;
 
        for (int i = 0; i < 3; i++) {
            for (int j = 1; j <= n; j++) {
                scanf("%d \n", &info[i][j]);
                check[i][info[i][j]]++;
            }
        }
        f = r = 0;
 
        merge(1, n);
 
        for(int ro = 0; ro < 3; ro++)
            for (int i = 1; i <= n; i++) {
                if (check[ro][i] == 0) {
                    if (inque[i]) continue;
                    inque[i] = true;
                    que[r++] = i;
                    check[0][i]--;
                }
            }
 
        while (f != r) {
            int now = que[f++];
 
            int conv = idx[now];
            check[1][info[1][conv]]--;
            if (check[1][info[1][conv]] == 0 && inque[info[1][conv]] == false) {
                inque[info[1][conv]] = true;
                que[r++] = info[1][conv];
                check[0][info[1][conv]]--;
            }
 
            check[2][info[2][conv]]--;
            if (check[2][info[2][conv]] == 0 && inque[info[2][conv]] == false) {
                inque[info[2][conv]] = true;
                que[r++] = info[2][conv];
                check[0][info[2][conv]]--;
            }
        }
 
        int res = 0;
        for (int i = 1; i <= n; i++) {
            res += inque[i];
        }
        printf("#%d %d\n", tc,res);
    }
 
    return 0;
}

여담

생각보다 복잡한 문제였습니다... 특히 방법 생각하기가 까다로웠어용

시간 복잡도는 최악의 경우 모든 열을 지워야 하는 경우이기 때문에 O(N) 입니다!

코드 배틀 결과!

으악.. 넘나리 아까워요..