글 읽기 - 반례를 못찾겠습니다

compa513 5년 전 0

arr에 괄호 문자열을 입력받은 다음

func함수로 넘겨줘서 하나씩 확인하여

'('가 나오면 check++

')'가 나오면 check--

그리하여 return check를 해서 check가 0일때만 YES를 출력하도록 했습니다.

함수 내에서 check의 값이 변동될 때마다 check가 음수가 되는지를 확인하여

모든 NO case를 확인하려 했으나

고려하지 못한 반례가 아직 남아있는지

오답 코드로 뜹니다

반례를 알려주시면 감사하겠습니다

#include <stdio.h>
#include <stdlib.h>
int func(char *arr);

int main() {
	int num;
	int i, j;
	
	
	scanf("%d", &num);
	int *check_arr = (int*)malloc(sizeof(int)*num);
	getchar();

	for (i = 0; i < num; i++) {
		int *arr = (int*)malloc(sizeof(int) * 51);
	
		gets(arr);

		int flag = func(arr);

		if (flag == 0) {
			check_arr[i] = 1;
		}
		else {
			check_arr[i] = 0;
		}

		free(arr);
	}

	for (i = 0; i < num; i++) {
		if (check_arr[i] == 1) {
			printf("YES\n");
		}
		else {
			printf("NO\n");
		}
	}

	return 0;
}

int func(char *arr) {
	int check = 0;
	
	for (int i = 0; i < 51; i++) {
		if (arr[i] == '(') {
			check++;
		}
		else if (arr[i] == ')') {
			check--;
		}

		if (check < 0) {
			return -1;
		}
	}

	return check;
}

djm03178 5년 전 2

무조건 51자까지 돌리면 문자열의 길이를 넘어선 위치에 우연히도 괄호 문자가 있어서 잘못된 동작을 할 수 있게 됩니다.

특히나 이렇게 반복적으로 메모리를 동적할당하고 지울 때는 이전과 똑같은 위치에 메모리가 잡힐 가능성이 크기 때문에, 이전 케이스의 잔재를 사용할 수도 있게 됩니다.

문자열의 끝을 올바르게 판단하고, 그 길이를 넘어서서 검사하지 않게 해 보세요.

compa513 5년 전 0

func조건문에

else { break; }를 추가했더니 해결 되었습니다

감사합니다! :)

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

문제

문제

출처

ICPC

반례를 못찾겠습니다

compa513 5년 전 0

djm03178 5년 전 2

compa513 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말