글 읽기 - 반례 좀 부탁드립니다.

revoir07 5년 전 0

하드코딩으로 구현한다고 했는데.. 틀렸다고 나오네요 ㅠ 우선가독성이 떨어지는점 죄송합니다.

잘못된 코딩습관이나 틀린부분, 반례 등 조언 부탁드립니다. 아주 기초적인 부분에 실수가 있을수도 있어요.

미리 감사드립니다.

#include <stdio.h>

void push(int* top, int c, int* stack){
	if ((c>0) && (stack[*top] > 0)){
		stack[*top] += c;
		return;
	}
	(*top)++;
	stack[*top] = c;

	return;
}

void pop(int* top, int ptr, int* stack){
	for (int i = ptr; i < *top; i++){
		stack[i] = stack[i + 1];
	}
	stack[*top] = 0;
	(*top)--;
	return;
}

int main()
{
	int num = 0;
	int top = 0;
	int pop_ptr = 0;
	char queue[32] = { 0 };
	int stack[32] = { 0 };

	scanf("%s", queue + 1);
	for (int i = 1; i < 31; i++)		// 입력받은 문자열 queue를 하나씩 stack에 push/pop
	{
		if (queue[i] == NULL){		// dequeue가 끝나면 계산된 숫자를 출력
			break;
		}
		switch (queue[i]){
		case '(':		// ( 들어오면 -1로 push
			push(&top, -1, stack);
			break;
		case '[':		// [ 들어오면 -2로 push
			push(&top, -2, stack);
			break;
		case ')':
			for (int i = top; i >= 0; i--){		// -1 검색해서 pop할 위치 탐색
				if (stack[i] == -1) {
					pop_ptr = i;
					break;
				}
			}
			if (pop_ptr == top){		// pop이 top에서 발생하면
				pop(&top, pop_ptr, stack);		// 원하는 위치 pop
				num = 2;
				if (stack[top] > 0){		// +연산 후 다시 push
					num += stack[top];
					stack[top--] = 0;
				}
				push(&top, num, stack);
			}
			else if (pop_ptr != top){		// pop이 중간에 숫자를 끼고 발생하면
				pop(&top, pop_ptr, stack);		// 원하는 위치 pop
				num = 2;
				if (stack[top] > 0){		// *연산 후 다시 push
					num *= stack[top];
					stack[top--] = 0;
				}
				else {
					top = 0;
					break;
				}
				push(&top, num, stack);
			}
			break;
		case ']':
			for (int i = top; i >= 0; i--){
				if (stack[i] == -2) {
					pop_ptr = i;
					break;
				}
			}
			if (pop_ptr == top){		// pop이 top에서 발생하면
				pop(&top, pop_ptr, stack);		// 원하는 위치 pop
				num = 3;
				if (stack[top] > 0){		// +연산 후 다시 push
					num += stack[top];
					stack[top--] = 0;
				}
				push(&top, num, stack);
			}
			else if (pop_ptr != top){		// pop이 중간에 숫자를 끼고 발생하면
				pop(&top, pop_ptr, stack);		// 원하는 위치 pop
				num = 3;
				if (stack[top] > 0){		// *연산 후 다시 push
					num *= stack[top];
					stack[top--] = 0;
				}
				else {
					top = 0;
					break;
				}
				push(&top, num, stack);
			}
			break;
		}
	}
	if (top == 1) printf("%d\n", stack[top]);
	else printf("0\n");
	return 0;
}

dyk777 5년 전 2

반례 드립니다.

https://ideone.com/loEAmP

Input:
[(])

Correct answer:
0

Test output:
6

revoir07 5년 전 0

dyk777님 감사합니다.

말씀하신부분 예외처리 반영했습니다. 그런데 그거말고도 틀린부분이 또있나봐요..

반영해서다시 시도해도 또틀렸다고 나오네요..

#include <stdio.h>

void push(int* top, int c, int* stack){
	if ((c>0) && (stack[*top] > 0)){
		stack[*top] += c;
		return;
	}
	(*top)++;
	stack[*top] = c;

	return;
}

void pop(int* top, int ptr, int* stack){
	for (int i = ptr; i < *top; i++){
		stack[i] = stack[i + 1];
	}
	stack[*top] = 0;
	(*top)--;
	return;
}

int main()
{
	int num = 0;
	int top = 0;
	int pop_ptr = 0;
	char queue[32] = { 0 };
	int stack[32] = { 0 };

	scanf("%s", queue + 1);
	for (int i = 1; i < 31; i++)		// 입력받은 문자열 queue를 하나씩 stack에 push/pop
	{
		if (queue[i] == NULL){		// dequeue가 끝나면 계산된 숫자를 출력
			break;
		}
		switch (queue[i]){
		case '(':		// ( 들어오면 -1로 push
			push(&top, -1, stack);
			break;
		case '[':		// [ 들어오면 -2로 push
			push(&top, -2, stack);
			break;
		case ')':
			for (int i = top; i >= 0; i--){		// -1 검색해서 pop할 위치 탐색
				if (stack[i] == -1) {
					pop_ptr = i;
					break;
				}
			}
			if (pop_ptr == top){		// pop이 top에서 발생하면
				pop(&top, pop_ptr, stack);		// 원하는 위치 pop
				num = 2;
				if (stack[top] > 0){		// +연산 후 다시 push
					num += stack[top];
					stack[top--] = 0;
				}
				push(&top, num, stack);
			}
			else if (pop_ptr != top){		// pop이 중간에 숫자를 끼고 발생하면
				pop(&top, pop_ptr, stack);		// 원하는 위치 pop
				num = 2;
				if (stack[top] > 0){		// *연산 후 다시 push
					num *= stack[top];
					stack[top--] = 0;
				}
				else {
					top = 0;
					break;
				}
				push(&top, num, stack);
			}
			break;
		case ']':
			for (int i = top; i >= 0; i--){
				if (stack[i] == -2) {
					pop_ptr = i;
					break;
				}
			}
			if (pop_ptr == top){		// pop이 top에서 발생하면
				pop(&top, pop_ptr, stack);		// 원하는 위치 pop
				num = 3;
				if (stack[top] > 0){		// +연산 후 다시 push
					num += stack[top];
					stack[top--] = 0;
				}
				push(&top, num, stack);
			}
			else if (pop_ptr != top){		// pop이 중간에 숫자를 끼고 발생하면
				pop(&top, pop_ptr, stack);		// 원하는 위치 pop
				num = 3;
				if (stack[top] > 0){		// *연산 후 다시 push
					num *= stack[top];
					stack[top--] = 0;
				}
				else {
					top = 0;
					break;
				}
				push(&top, num, stack);
			}
			break;
		}
	}
	if (top == 1) printf("%d\n", stack[top]);
	else printf("0\n");
	return 0;
}

dyk777 5년 전 2

다른 반례 드립니다.

https://ideone.com/gMg4Qo

얼핏 보니 짝이 맞지 않는 괄호에 대해서 제대로 처리하지 못하고 있는 듯 보이네요.

Input:
())[]

Correct answer:
0

Test output:
5

revoir07 5년 전 0

아주 기본적인 예외를 누락했었네요 ㅠ 반영했습니다.

이후에는 다른사람 질문에 있는 반례까지 다 넣어봤는데 pass 했거든요.

근데 정답 제출하면 틀렸다고 나옵니다.. 다른 반례가 있을까요?

#include <stdio.h>

void push(int* top, int c, int* stack){
	if ((c>0) && (stack[*top] > 0)){
		stack[*top] += c;
		return;
	}
	(*top)++;
	stack[*top] = c;

	return;
}

void pop(int* top, int ptr, int* stack){
	for (int i = ptr; i < *top; i++){
		stack[i] = stack[i + 1];
	}
	stack[*top] = 0;
	(*top)--;
	return;
}

int main()
{
	int i, j, num = 0, top = 0, pop_ptr = 0;
	char queue[32] = { 0 };
	int stack[32] = { 0 };

	scanf("%s", queue + 1);
	for (i = 1; i < 31; i++)
	{
		if (queue[i] == NULL){
			break;
		}
		switch (queue[i]){
		case '(':		// ( 들어오면 -1로 push
			push(&top, -1, stack);
			break;
		case '[':		// [ 들어오면 -2로 push
			push(&top, -2, stack);
			break;
		case ')':
			for (j = top; j > 0; j--){		// -1 검색해서 pop할 위치 탐색
				if (stack[j] == -1) {
					pop_ptr = j;
					break;
				}
			}
			if (j == 0) {		// pop할 것 못찾으면 fail
				top = 0;
				i = 31;
				break;
			}
			if (pop_ptr == top){		// pop이 top에서 발생하면
				pop(&top, pop_ptr, stack);		// 원하는 위치 pop
				num = 2;
				if (stack[top] > 0){		// +연산 후 다시 push
					num += stack[top];
					stack[top--] = 0;
				}
				push(&top, num, stack);
			}
			else if (pop_ptr != top){		// pop이 중간에 숫자를 끼고 발생하면
				pop(&top, pop_ptr, stack);		// 원하는 위치 pop
				num = 2;
				if (stack[top] > 0){		// *연산 후 다시 push
					num *= stack[top];
					stack[top--] = 0;
				}
				else {
					top = 0;
					break;
				}
				push(&top, num, stack);
			}
			break;
		case ']':
			for (j = top; j > 0; j--){		// -2 검색해서 pop할 위치 탐색
				if (stack[j] == -2) {
					pop_ptr = j;
					break;
				}
				if (j == 0) {		// pop할 것 못찾으면 fail
					top = 0;
					i = 31;
					break;
				}
			}
			if (pop_ptr == top){		// pop이 top에서 발생하면
				pop(&top, pop_ptr, stack);		// 원하는 위치 pop
				num = 3;
				if (stack[top] > 0){		// +연산 후 다시 push
					num += stack[top];
					stack[top--] = 0;
				}
				push(&top, num, stack);
			}
			else if (pop_ptr != top){		// pop이 중간에 숫자를 끼고 발생하면
				pop(&top, pop_ptr, stack);		// 원하는 위치 pop
				num = 3;
				if (stack[top] > 0){		// *연산 후 다시 push
					num *= stack[top];
					stack[top--] = 0;
				}
				else {
					top = 0;
					break;
				}
				push(&top, num, stack);
			}
			break;
		}
	}
	printf("%d\n", top == 1 ? stack[top] : 0);
	return 0;
}

dyk777 5년 전 4

다른 반례 드립니다.

https://ideone.com/mxGVhG

짝이 맞는 괄호를 찾기 위해 뒤에서부터 배열을 탐색하시는데, 그러면 스택으로서의 의미가 없습니다.

탐색 대신, pop() 만으로 어떻게 할 수 있을지 한번 고민해보세요.

Input:
(()([())])

Correct answer:
0

Test output:
28

revoir07 5년 전 0

ㅈ조언감사합니다. 일단은 그냥 예외처리로 제출해서 PASS는 했는데..

stack 특성 반영해서 다시 해보려고요

감사합니다.

kimyh0316 5년 전 0

@dyk777

정말 감사합니다 ㅜㅜ 덕분에 해결했네요

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

문제

문제

출처

ICPC

반례 좀 부탁드립니다.

revoir07 5년 전 0

dyk777 5년 전 2

revoir07 5년 전 0

dyk777 5년 전 2

revoir07 5년 전 0

dyk777 5년 전 4

revoir07 5년 전 0

kimyh0316 5년 전 0

@dyk777

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말