[SW Expert Academy] 8월의 마지막 코드배틀

어느덧 8월도 끝나부렀네요.

진짜 생각해보면 시간이 빠릅니다.

여름 핵더웠는데, 이제는 조금 괜찮아진것도 같고,

산 다닐때 모기도 정말 드럽게 많았는데, 요즘은 또 잠잠하더라구요.

어쨌든, 화요일마다 시행하는 코드배틀! 오늘도 시작하겠습니다.

SW Expert Academy의 문제들은 무단 복제가 금지되어있기 때문에 링크로 대체하겠습니다! 클릭시 이동합니다.

5431. 민석이의 과제 체크하기

어떻게 풀까?

카운팅 소팅을 응용합시다!

우선, 과재의 개수 N만큼 check 배열을 만듭니다.

그리고 입력이 들어올때마다 해당 check배열을 true로 만들어줍니다.

그리고 입력이 끝나면, 이제 1부터 N까지 순회하면서 check배열이 false라면 해당 수를 출력하면 쉽게 구할 수 있을 것 입니다!

코드

#pragma once
#include<cstdio>
#include<cstring>
bool arr[101];
 
int main() {
    int t;
    int n, k;
    scanf("%d\n", &t);
    for (int tc = 1; tc <= t; tc++) {
        memset(arr, false, sizeof(arr));
 
        scanf("%d %d\n", &n, &k);
 
        for (int i = 0; i < k; i++) {
            int in; scanf("%d\n", &in);
 
            arr[in] = true;
        }
        printf("#%d ", tc);
 
        for (int i = 1; i <= n; i++) {
            if (arr[i] == false) {
                printf("%d ", i);
            }
        }
        printf("\n");
    }
    return 0;
}

여담

시간복잡도는 O(N) 이겠죠!

5432. 쇠막대기 자르기 

어떻게 풀까?

문제의 특성을 파악하면 빠르게 풀 수 있습니다!

문제는 '('와 ')'만으로 구성되어있습니다.

또한, ()는 레이저를 발사하는 것이죠!

겹치는 구간이 없기 때문에 문제를 풀기가 굉장히 수월해집니다!

왜냐하면, '('가 나온다는 것은, 층이 딱 하나가 더 쌓인다는 것이기 때문이죠!

이제 ')'의 경우를 생각해봅시다.

')'는 앞의 문자가 무엇이냐에 따라서 다른 역할을합니다.

첫 번째로 ')'가 바로 앞에 오는 경우입니다.

이 경우에는 쇠 막대기 하나가 사라진다. 라는 의미를 가지고있죠.

쇠 막대기는 겹쳐져서 놓이지 않기 때문에 무조건 딱 하나만 사라집니다!

그리고, 이렇게 되면 조각 하나가 완성됬다. 라는 의미이기도 합니다.

왜냐하면, 위 조각은 이제 뒤에 오는 레이저에 의해서 분해되는 일이 없기 때문이죠!

이제 ')'앞에 '('가 오는 경우를 생각해봅시다.

위 경우는 레이저를 쏘는 경우입니다!

그리고 레이저를 쏜다면, 쌓여있는 층이 2 개로 분리됩니다!

즉, 만약 층이 n개라면, 레이저를 쐈을때 얻을 수 있는 막대기 조각은 n개라는 것이죠!

위에서 보았듯이, 문자열을 하나하나 읽으면, 

층이 하나 생긴다, 층이 하나 사라진다에 대한 정보를 알 수 있습니다.

이를 통해, 레이저를 쐈을 때 만들어지는 조각들의 개수도 알 수 있죠!

이제 문자열을 입력받으면, 앞에서부터 문자열을 하나하나 읽으면서 그에 대한 맞는 처리를 해주면 문제를 쉽게 해결할 수 있습니다!!

코드

#pragma once
#include<iostream>
#include<cstring>
using namespace std;
 
char info[100001];
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    int t;
 
    cin >> t;
 
    for (register int tc = 1; tc <= t; tc++) {
        cin >> info;
        int land = 1;
 
        int len = strlen(info);
        int res = 0;
        char pr = info[0];
        for (register int i = 1; i < len; i++) {
            if (info[i] == ')') {
                land--;
                if (info[i - 1] == '(') {
                    res += land;
                }
                else {
                    res++;
                }
            }
            else {
                land++;
            }
        }
        cout << '#' << tc << ' ' << res << '\n';
    }
    return 0;
}

여담

시간복잡도는 문자열의 길이를 N이라고 했을 때, 앞에서부터 하나씩 순차 검사하므로, O(N) 입니다!

이번 코드배틀은 굉장히 쉬웠네요!

그래서 그런지 등수도 별로 높지 않답니다.