[SW Expert Academy] Code Battle!

이번주의 즐거운 코드 배틀도 끝났습니다.

터널 문제가 생각 외로 D5였네요! (어쩐지 계속 틀리더라니..)

어쨌든, 오늘도 코드배틀 풀이를 시작하겠습니다!

SW Expert Academy의 문제들은 저작권 문제 때문에 링크로 대체하겠습니다.

문제 제목 클릭시 이동합니다.

5356. 의석이의 세로로 말해요

어떻게 풀까??

세로로 출력하는 문제이군요!

딱 제한되는 조건은 하나입니다.

'왼쪽 위부터 아래로 출력하지만, 출력하고자 하는 글자가 없다면 무시하고 계속 진행한다.' 이것만 처리해서 구현하면 되겠군요!

행 마다 글자의 가로 글자의 개수를 저장하고,

만약, 해당 행에 해당하는 글자의 열의 위치를 출력하고자 할 때, 해당 행의 가로 글자가 열의 크기보다 작으면, 무시하고 다음 행을 진행하는 방식으로 구현하면 됩니다! 

테스트 케이스 2번을 한번 풀어보겠습니다!

처음 입니다.

처음에, 왼쪽 위부터 읽어나가기 시작합니다. A를 저장합니다.

]

왼쪽 위에서부터 아래로 읽어나갑니다. 맨 아래까지 온다면 오른쪽으로 한칸 옮겨서 맨 위 부터 다시 읽습니다.

Aa를 읽었습니다.

이렇게 읽어나가는 부분을 단순하게 반복합니다.

앗! 드디어 빈 글자가 나왔습니다. 2 행의 글자 수는 4개이고, 2행에서 뽑아내고자 하는 열의 글자는 5 입니다.

따라서, 글자가 없다는 것을 알 수 있고, 해당 위치는 무시합시다!

그러면 또 다시 단조로운 글자뽑기가 반복됩니다.

앗, 이번에도 2 행에서 글씨를 뽑으려고 하지만, 해당 위치에 글자는 없습니다. 무시합시다.

이제, 3 행에서도 글씨가 없습니다. 무시합시다.

글씨를 모두 추출했고, 결과값이 나왔습니다!

코드

#pragma once
#include<cstdio>
#include<cstring>
 
char in[5][16]; int ilen[5];
char res[76];
int rlen;
 
int main() {
    int t;
    scanf("%d\n", &t);
 
    for (int tc = 1; tc <= t; tc++) {
        rlen = 0;
        for (int i = 0; i < 5; i++) {
            scanf("%s\n", in[i]);
            ilen[i] = strlen(in[i]);
        }
 
        for (int j = 0; j < 15; j++) {
            for (int i = 0; i < 5; i++) {
                if (ilen[i] > j) {
                    res[rlen++] = in[i][j];
                }
            }
        }
 
        res[rlen] = 0;
        printf("#%d %s\n", tc, res);
    }
    return 0;
}

여담

시간 복잡도는 O(1)입니다!

(제 코드는 5행 15열을 항상 다 보기 때문이죠!)

5357. 터널 속의 기차

어떻게 풀까?

시뮬레이션 문제입니다!

조건을 잘 따져서 단계를 잘 구분해야합니다!

가장 중요한 것은 어떻게 하면 모든 경우에서 터널에 빛이 있는지 확인할 수 있는가? 입니다!

저는 우선, 터널안에 있는 차량을 큐에 넣었고,

현재, 차들이 늘어져 있는 길이를 height라는 변수에 저장했습니다.

그리고,  현재 터널에 있는 빛의 개수를 rCnt라는 값에 저장했죠!

이렇게 해놓으면, 터널의 길이 h에 따라서 맨앞의 차량이 터널에서 빠져나가게 하고, 맨 뒤에 차량이 들어오는 것을 조절하기 쉬울 것입니다.

그리고, rCnt값이 0이 되는 순간이 바로 터널에 빛이 0이 되는 순간입니다!

따라서, rCnt가 0이 될 때만 잘 조절하면 답을 구할 수 있는 것입니다!

그럼, 가장 중요한 부분을 먼저 해 봅시다!

큐에 어떻게 차량을 넣고 뺄 것인가!?

이를 위해 확인해야할 것은, 터널 안에 있는 빛이 언제 달라지는지를 잘 생각해 보는 것입니다!

터널 안에 있는 빛의 수가 변할 때는 딱 두가지 입니다.

1. 맨 앞 차량이 터널에서 빠져나갔다!

2. 새로운 차량이 터널에 들어왔다!

이것을 잘 조절해야합니다!

이를 세부적으로 나누면, 꽤 여러가지 경우가 있습니다.

1. 맨 앞 차량이 터널에서 빠져나가고, 뒤에서 차량이 들어오지 않았다.

2. 맨 앞 차량이 터널에서 빠져나가고, 맨 뒤에서 차량이 들어왔다.

3. 맨 앞 차량이 터널에서 빠져나가지 않았는데, 맨 뒤에서 차량이 들어왔다.

4. 맨 앞 차량이 터널에서 빠져나가지 않았는데, 맨 뒤에서 차량이 들어오지 않았다.

이렇게 네 가지로 나눌 수 있습니다!

첫 번째 경우는 뒤의 차량의 길이가 매우 긴 경우입니다!

위와 같이 12의 길이를 가지는 터널이 있다고 가정해 봅시다!

맨 앞에는 길이가 4인 자동차가 있습니다. 그 뒤에는 16의 길이를 가지는 자동차가 있습니다.

위 그림처럼, 맨 앞의 차량이 나가도, 터널에는 새로운 차량이 들어오지 않았습니다!

또한, 터널 안에 있는 차량의 수가 바뀌었기 때문에, 빛의 수가 바뀌겠죠!

두 번째 경우는 현재 큐에 저장된 자동차들의 길이에서 맨 앞의 차량을 뺐을 때, 그 길이가 터널의 길이(h) 보다 작을 경우 입니다!

위 그림 같은 경우에는 그 길이가 12보다 작을 경우겠군요!

위와 같은 상황에서

길이 4의 차가 빠지면, 차들의 총 길이는 11이 되고 

그러면 새로운 차가 들어올 수 있겠죠!

다만! 정말 중요한 것이 하나 있습니다.

차의길이가 무지무지 길다고 생각해 봅시다!

위와 같은 상황에서 앞에있는 11의 차가 빠져나가면 어떻게될까요!?

이렇게, 차가 하나 들어와도 뒤에 빈 공간이 생기는 경우가 생깁니다!

11의 차가 빛나고 있었다고 가정하고, 뒤의 길이 3 차 두 개는 빛이 나지 않는다고 가정하겠습니다!

위의 경우로 따지면, 터널에 빛이 없기 때문에 빛을 늘려주는 작업을 해주어야 합니다!

하지만, 만약 뒤에 있는 차량이 불이 켜져있었으면, 실제로는 터널에 빛이 있기 때문에 빛을 켜는 작업은 해줄 필요가 없습니다!

따라서, 차량의 길이가 h보다 작다면 뒤에 계속 차량을 넣는 작업을 해줍시다!

아래처럼 말이죠!

세 번째 경우, 맨 앞에 차량이 빠져나가지 않았는데, 맨 뒤에서 차량이 들어왔다.

맨 뒤에서차량이 들어온 경우만 있기 때문에, 터널에 빛이 있다가 없어지는 일은 없습니다!

따라서, 추가로 생각할 필요가 없다는 것이죠!

네 번째 경우, 맨 앞 차량이 터널에서 빠져나가지 않았는데, 맨 뒤에서 차량이 들어오지 않았다.

이 조건은 아예 터널 내의 차량이 변화가 없다는 것을 말합니다.

따라서, 저 조건에 따라서 처리해주면 됩니다!

그럼, 이제 터널에 불이 없을때 어떻게 해야할까에 대해서 생각해 봅시다!

그리디처럼 생각할 수 있습니다!

어떤 순간에, 터널에 빛이 없는 경우, 어떻게 하는 경우가 최선일까요!?

간단합니다! 바로 맨 뒤에 있는 차량의 불을 켜는 것 입니다!

맨 뒤에 있는 차량이 터널 밖으로 나갈 때까지 해당 터널에는 계속해서 빛이 있겠죠!

맨 뒤에 있는 차량이란, 큐의 맨 마지막에 들어있는 차량을 의미하겠죠! 이제보니 큐가 아니라 덱을 써야겠군요 ㅋㅋㅋ

코드

#pragma once
#include<cstdio>
int h;
int que[100000], f, r, n;
int infos[100000][2];
int main() {
    int t;
    scanf("%d\n", &t);
    for (int tc = 1; tc <= t; tc++) {
        scanf("%d %d\n", &n, &h);
        f = r = 0;
 
        int rcnt = 0;
        
        for (int j = 0; j < 2; j++) {
            for(int i = 0; i < n; i++)
            scanf("%d \n", &infos[i][j]);
        }
 
        int height = infos[0][0];
        int res = infos[0][1] == 0;
        infos[0][1] = 1;
        rcnt = 1;
        que[r++] = 0;
        int idx = 1;
        while (idx != n) {
            if (height >= h) {
                int now = que[f++];
                height -= infos[now][0];
                rcnt -= infos[now][1];
            }
 
            while(idx != n && height < h) {
                que[r++] = idx;
                height += infos[idx][0];
                rcnt += infos[idx][1];
                idx++;
            }
 
            if (rcnt == 0) {
                res++;
                infos[que[r - 1]][1] = 1;
                rcnt = 1;
            }
        }
 
        while (r - f != 1) {
            int now = que[f++];
            if (infos[now][1]) {
                rcnt--;
                res += rcnt == 0;
            }
        }
        printf("#%d %d\n", tc, res);
    }
    return 0;
}

여담

시간 복잡도는 기차가 큐에 들어갔다 나왔다 하는 것 밖에 없기 때문에 O(n)이 됩니다!

코드 배틀 결과!!

5 등입니다~ 두둥!