4-O 반례나 어디가 문제인지 알 수 있을까요?

10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트

4-O

작성

수정됨

#include <iostream>

using namespace std;

string s;
int n, ans, skip;

int main(void) {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    cin >> n >> s;

    for (int i = 0; i < n; ++i) {
        int temp = 0;
        int flag = 1;

        for (int j = i; j < n; ++j) {
            char c = s[j];

            if ((flag == 1 && c == ')') || (j == n - 1 && c == '(')) {
                break;
            }

            if (c == '(') flag <<= 1;
            else flag >>= 1;

            temp++;
            if (flag == 1) {
                ans = max(ans, temp);
                skip = (temp - 1);
            }
        }

        i += skip;
        skip = 0;
    }

    cout << ans << '\n';
}

계속 1%에서 틀렸다고 나오네요..

강의를 보고 다른 방법으로 풀었으나 처음 풀었던 방식에서 어디가 문제인지 알고 싶어 질문드립니다!

커뮤니티, 백준 질문 게시판에 있는 반례들을 전부 통과했습니다..

c++코딩-테스트

답변 2

큰돌

지식공유자

안녕하세요 ㅎㅎ

사실 이 코드는 제가 여러번 디버깅을 해보며 시도를 해봤습니다.

2의 승수를 이용해서 로직을 짠점.

올바른 분기점에서의 break;

skip 부분까지

완벽하다 생각합니다.

다만,

생각해보면 flag가 1이 아니면서 -> c가 ( 또는 )인 상태로 반례를 만들면 되지 않을까?

했는데 해당 부분 또한 맞다고 뜹니다.

죄송하지만 어떤 문제가 있는지 파악하지 못하는 것 같습니다.

이부분은 제가 나중에 또 시도해보고 반례를 찾으면 다시 답변을 드리겠습니다.

감사합니다.

-1

인프런 AI 인턴

안녕하세요, 인프런 AI 인턴입니다. ki2님.

질문해 주신 코드와 관련한 유사한 사례를 찾아보았습니다. 원인은 여러 가능성이 있겠지만, 코드의 논리에서 잘못된 부분이나 고려하지 않은 엣지 케이스가 있는 것 같습니다. 비슷한 문제를 다룬 예제와 답변 링크를 참조하시어 문제를 해결해 보시길 바랍니다.

우선, 괄호의 짝을 맞춰야 하는 문제에서 자주 발생하는 실수를 점검하며, 관련된 몇 가지 답변 링크를 참고하도록 안내드리겠습니다:

링크: 2-O 4949번 문제의 반례를 못찾겠습니다
- 이 답변에서는 스택을 활용하여 괄호 짝을 맞추는 방법을 설명하면서, 스택이 비어있을 때의 예외 처리에 주목했습니다.
링크: 4949번 제가 낸 답이 왜 틀렸는지 모르겠습니다
- 이 답변에서는 괄호를 정확히 짝 지을 때 필요한 논리적 개선점을 설명했습니다. 특히, ‘]’ 또는 ‘)’ 괄호가 나올 때 스택이 비어있는지 확인하는 과정에 대해 강조하였습니다.
링크: 2-H 질문입니다
- 여기서도 비슷한 성격의 문제를 다루고 있으므로, 다양한 반례를 통해 코드의 정확성을 검토해 보는 것이 중요합니다. 특히, 문자열 내에서 모음과 자음의 연속성 문제를 설명하였습니다.
링크: 2-O 질문있습니다!
- 질문자의 코드에서 스택의 처리 방식, 특히 괄호가 닫힐 때 스택이 비어있는지 여부에 관한 논의를 하였습니다.

이외에도, 아래 몇 가지 지침을 참고하면 도움이 될 수 있습니다:
- 괄호의 짝을 맞추는 것 외에도 문자열의 길이나 특수한 입력 값에 따라 코드가 올바르게 동작하는지 확인해보세요.
- 코드의 각 조건에 대한 논리를 다시 한번 점검하면서, 예외 처리(특히 스택이 비어있는 경우)를 잘 살펴보세요.
- 다양한 테스트 케이스를 통해 코드가 모든 경우에 대해 올바르게 작동하는지 검증해보세요.

저는 질문자님의 이해를 돕고자 지식공유자님의 기존 답변을 참고하여 유사한 답변 링크를 추천해드리고 있습니다.
현재 베타 기능으로 답변이 만족스럽지 않을 수 있는 점 양해 부탁드립니다. 🙏
추가적으로 궁금한 점이 있으시면, 이어서 질문해 주세요. 곧 지식공유자께서 답변해 주실 것입니다.

인프런 커뮤니티 질문&답변

4-O 반례나 어디가 문제인지 알 수 있을까요?