[모각코] C/C++ 모각코 스터디 4일차

오늘은 강의를 들으며 진행한 문제들을 리뷰해보는 시간을 갖도록 하겠습니다.

 

-올바른 괄호찾기

문제: 괄호가 입력되면 올바른 괄호이면 “YES", 올바르지 않으면 ”NO"를 출력합니다. (())() 이것은 괄호의 쌍이 올바르게 위치하는 거지만, (()()))은 올바른 괄호가 아니다.

 

▣ 입력설명 첫 번째 줄에 괄호 문자열이 입력됩니다. 문자열의 최대 길이는 30이다.

▣ 출력설명 첫 번째 줄에 YES, NO를 출력한다.

 

JAVA를 공부했을 때 사용했던 방법으로는 자료구조인 'Stack'을 이용하였습니다. C++에서도 동일하게 스택을 사용할 수 있지만 이번강의에서는 스택을 사용하지 않고 조건문만을 통해서만 문제풀이를 진행하였습니다.

 

#include <stdio.h>
using namespace std;
int main(){
    //    freopen("input2.txt", "rt", stdin);
    char a[100];
    int i, cnt = 0;
    scanf("%s", &a);
    for(i=0; a[i]!='\0'; i++){
        if(a[i]=='(')cnt++;
        else if(a[i]==')')cnt --;
        if(cnt<0)  break;
    }
    if(cnt==0) printf("YES\n");
    else printf("NO\n");
    return 0;
}

char 형태의 a배열을 선언해주고 안에 입력예시인 '(()(()))(()'를 입력해줍니다. 그리고 반복문을 통해 '\0' 즉, 비어있는 배열이 나오지 않는 동안 반복문을 돌려주고 만일 배열 안 원소가 '('일 경우에는 cnt를 1씩 증가, ')'일 경우에는 cnt를 1씩 감소시켜 최종 cnt가 0인경우 열린괄호와 닫힌괄호의 개수가 일치하다는 결론을 도출해 냅니다. 이때 cnt가 음수일 경우를 따로 조건처리를 해준 경우는 '())('와 같이 열린괄호가 한번 나오고 닫힌괄호가 두번연속으로 나올 경우, 쌍의 개수는 일치하지만 정상적인 괄호의 형태가 아니기에 이 경우는 예외처리를 해주었습니다.

 

- 모두의 약수

문제: 자연수 N이 입력되면 1부터 N까지의 각 숫자들의 약수의 개수를 출력하는 프로그램을 작성하 세요. 만약 N이 8이 입력된다면 1(1개), 2(2개), 3(2개), 4(3개), 5(2개), 6(4개), 7(2개), 8(4 개) 와 같이 각 숫자의 약수의 개수가 구해집니다. 출력은 다음과 같이 1부터 차례대로 약수의 개수만 출력하면 됩니다. 1 2 2 3 2 4 2 4 와 같이 출력한다.

 

▣ 입력예제 1

8

 

▣ 출력예제 1

1 2 2 3 2 4 2 4

 

#include <stdio.h>
using namespace std;
int cnt[50001];
int main(){
    int n, i, j;
    scanf("%d", &n);
    for(i=1; i<=n; i++){
        for(j=i; j<=n; j=j+i){ //i를 약수로 갖는 숫자 j
            cnt[j]++;
        }
    }
    for(i=1; i<=n; i++){
        printf("%d ", cnt[i]);
    }
    return 0;

}

기존의 방법으로는 연속 for문을 통해서 각 배열의 칸마다 일일이 원소를 비교해서 약수인지를 판단하는 방법을 사용했었습니다. 하지만 이 경우에 연속 for문을 사용할 경우 시간복잡도가 O(n^2)가 되므로 시간초과가 발생하는 상황이 발생합니다. 따라서 기본적으로 배열을 전역변수로 선언해주고 모든 배열 칸의 값을 1로 기본설정 해줍니다. 그리고 for문을 통해 j를 증가시키는데, 이 때 j는 항상 i만큼 더해지기 때문(즉, j는 i를 약수로 갖게 됩니다)에 반복 횟수를 줄일 수 있습니다. 

 

- 자릿수의 합

문제: N개의 자연수가 입력되면 각 자연수의 자릿수의 합을 구하고, 그 합이 최대인 자연수를 출력 하는 프로그램을 작성하세요. 각 자연수의 자릿수의 합을 구하는 함수를 int digit_sum(int x)를 꼭 작성해서 프로그래밍 하세요.

 

▣ 입력예제 1

5

125 15232 79 1325 97

 

▣ 출력예제 1

97

 

#include <stdio.h>
int digit_sum(int x) {
    int sum=0, tmp;
    while(x>0){
        tmp=x%10;
        sum=sum+tmp;
        x=x/10;
    }
    return sum;
}

int main(){
    int n, i, num, sum, res, max=-2147000000;
    scanf("%d", &n);
    for(i=1; i<=n; i++) {
        scanf("%d", &num);
        sum=digit_sum(num);
        if(sum>max){
            max=sum;
            res=num;
        }
        else if(sum==max){
            if(num>res) res=num;
        }

    }
    printf("%d", res);
    return 0;

}

먼저 문제에서 digit_num함수를 사용하라고 명시되어 있었기 때문에 함수 선언을 해주었습니다. max변수의 경우 비교를 통해 값이 새롭게 갱신되는 변수이기 때문에 기본값으로는 최솟값이 -2147000000로 설정하였습니다. N개의 값을 먼저 입력해주고 비교를 위한 변수들을 넣어줍니다. 넣어준 값들은 바로 digit_num함수로 들어가게 되는데, 자릿수의 합을 구해야 함으로 10으로 나누어줌으로써 나머지를 자릿수 값으로, 몫을 다음 연산을 위한 값으로 남겨줍니다. 그리고 sum을 통해 자릿수 합을 저장합니다. 최종적으로 sum값과 max 값의 비교를 통해 최대의 sum값을 찾게되고 이때의 변수값을 res에 담아둠으로써 res반환을 통해 최종 정답을 구할 수 있게 됩니다.