글 읽기 - 어떤 반례가 있는지 잘 모르겠습니다

spblue4422 2년 전 0

처음에 문자열을 만들어 풀다가 메모리 초과로 인해 스택에 개별로 푸시하고 팝하면서 길이를 구하는 방식으로 풀어보았는데,

예제와 질문게시판의 반례들은 다 정답이 나오는데 계속 '틀렸습니다' 가 나옵니다.

제 코드에 어떤 문제가 있는지 확인 부탁드립니다.

+ 이 문제에 5시간동안 머리 싸매고 있는데 도움 부탁드립니다 ㅠㅠ

#include <iostream>
#include <stack>
#include <stdio.h>
#include <stdlib.h>
#include <string>
using namespace std;

struct zip {
    int letter;
    //플래그가 0이면 일반 글자, 1이면 반복된 문자열의 길이
    int flag;
};

stack<zip> stk;
char arr[100];

int main() {
    long long len = 0;
    int cnt = 0;
    scanf("%s", arr);
    string str = arr;

    for (int i = 0; i < str.length(); i++) {
        if (str[i] == ')') {
            //)일때는 (가 나오기전까지 스택에서 팝
            while (stk.top().letter != '(') {
                //팝할때, 플래그 값이 1이면 압축을 푼 문자열의 길이 이므로,
                // cnt에 더해줘야함. 아니면 그냥 1을 더함.
                cnt += stk.top().flag ? stk.top().letter : 1;
                stk.pop();
            }
            //( 팝
            stk.pop();
            //문자열을 반복할 횟수
            int repeat = stk.top().letter - 48;
            stk.pop();
            // 반복횟수 * 반복할 문자열길이, 플래그는 1로 푸시
            stk.push({repeat * cnt, 1});
            cnt = 0;
        } else { //)가 아니면 스택에 모두 푸시
            stk.push({str[i], 0});
        }
    }

    while (!stk.empty()) {
        len += stk.top().flag ? stk.top().letter : 1;
        stk.pop();
    }

    printf("%lld", len);

    return 0;
}

spblue4422 2년 전 0

새롭게 짜서 제출했더니 '맞았습니다'가 나왔는데 위의 코드와 어떤 부분에서 차이가 있는걸까요...

전반적인 로직은 거의 비슷하게 가져갔고, 스택을 int로 바꾸면서 문자열의 길이를 나타내는 푸쉬일 경우 음수로 푸쉬했습니다. (길이가 0일 경우 푸쉬 X)

#include <iostream>
#include <stack>
#include <stdio.h>
#include <stdlib.h>
#include <string>
using namespace std;

int main() {
    long long len = 0;
    int cnt = 0, temp = 0;
    stack<int> stk;
    char arr[100];

    scanf("%s", arr);
    string str = arr;

    for (int i = 0; i < str.length(); i++) {
        if (str[i] == ')') {
            while (stk.top() != '(') {
                if (stk.top() < 0) {
                    cnt += (stk.top() * -1);
                    stk.pop();
                } else {
                    cnt++;
                    stk.pop();
                }
            }
            stk.pop();
            if (!stk.empty()) {
                temp = stk.top() - 48;
                stk.pop();
                if (temp * cnt * -1 != 0) {
                    stk.push(temp * cnt * -1);
                }
            }
            cnt = 0;
        } else {
            stk.push(str[i]);
        }
    }

    while (!stk.empty()) {
        if (stk.top() < 0) {
            len += (stk.top() * -1);
        } else {
            len++;
        }
        stk.pop();
    }

    printf("%lld", len);

    return 0;
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

어떤 반례가 있는지 잘 모르겠습니다

spblue4422 2년 전 0

spblue4422 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말