[백준 알고리즘] 10773번

1. 문제와 실행결과 예시

 

이번 문제는 스택을 잘 알고있는 사람이라면 매우 쉽게 풀 수 있는 알고리즘 문제이다. (심지어 push()와 pop() 메소드만 구현하면 된다 ㄷㄷ) 그리고 바로 전에 풀었던 문제(10820번)에서 이미 스택을 구현했기 때문에, 런타임 에러 해결을 위한 구글링 시간을 제외한다면 10분도 걸리지 않았다! 다음은 10773번 문제에 대한 안내이다.

 

출처: https://www.acmicpc.net/problem/10773

 

---

백준알고리즘 10773번

---

 흠......일단 문제만 봐서는 아직 잘 모르겠지만 (나만 그럴수도 ㅎ) 실행결과를 보면 구현해야할 코드가 확실해진다. 다음은 실행결과 예시이다.

 

---

실행결과 예시

---

2. 문제풀이

 

- stack() 구현

 

 실행결과 예시를 보면 알겠지만 '0'을 입력받으면 pop()을 실행하고 '0'이 아닌 다른 정수는 push()를 실행하여 스택에 넣어주면 된다! "왜 pop()이지?" 라고 생각하시는 분들이 계실 수도 있을 것 같아 간단하게 설명하자면, '0'을 입력받았을 때 가장 최근의 수를 지운다는 문장에서 stak의 pop()을 사용하면 편리하게 구현할 수 있다는 것을 알 수 있다. 다시 한번 말하지만 이 카테고리는 나의 문제풀이를 보여주는 곳이므로, Stack에 대한 개념을 설명하지는 않는다. (꼭 만들게요 ㅠㅠ) 다음은 내가 작성한 Stack이다.

 

#define SIZE 10000

class Stack {
private:

	int stack[SIZE];
	int top;

public:

	Stack() { top = -1; }

	void push(int x) {
		stack[++top] = x;
	}

	int pop() {
		return top == -1 ? -1 : stack[top--];
	}

};

 

 정말 슬픈 사실이지만 이렇게 간단한 Stack을 구현해도 나는 에러가 났다 ㅠㅠ 왜 그럴까? 살펴보면 메소드에는 문제가 없어 보인다. ( 적어도 이 문제에 안에서는) 그렇다면 무슨 에러가 발생한 것일까? 내 코드에서 발생한 에러는 바로 런타임 에러이다. 자 이 런타임 에러에 대하 자세히 살펴보자.

 

- 런타임 에러

 

 내가 지금까지 검색한 정보를 정리하자면, 런타임에러가 발생하는 경우는 다음과 같다.

 

1. 배열의 범위가 너무 적거나 많을 때
2. 0으로 무언가를 나눴을 때
3. 메모리를 과다하게 사용했을때

나의 코드에서는 메모리를 과다하게 사용할 만한 반복문이나 변수 생성문이 없으며 0으로 무언가를 나누는 코드도 없다. (심지어 나머지 연산자를 사용하는 코드도 없음) 자, 그렇다면 배열이 문제라는 것인데 (일단 내가 수집한 정보가 전부라면) 배열의 범위가 많다라고는 생각하지 않는다. 그래서 적다는 경우를 생각해봤다. 아니나 다를까 문제에서는 입력값이 정해져있다. 최대가 100000 이다. 극단적인 경우를 생각해보자 (EGOING님의 명언이다.) 만약 100000개의 명령어가 모두 push라면? 배열은 100000개의 자리를 가지고 있어야한다. 결국 stack으로 사용해야하는 배열의 최댓값은 100000이어야 한다는 얘기가 된다. 결과적으로 코드를 다음과 같이 생성하면 에러를 피할 수 있다.

 

#define SIZE 100000

class Stack {
private:

	int stack[SIZE];
	int top;

public:

	Stack() { top = -1; }

	void push(int x) {
		stack[++top] = x;
	}

	int pop() {
		return top == -1 ? -1 : stack[top--];
	}

};

 

- main() 함수

 

 자 이제 stack()을 구현하였으니 main() 함수만 구현하면 된다. main() 함수는 크게 두가지 부분으로 나눌 수 있는데, 입력받는 부분과 스택의 요소들의 합을 계산하는 부분이다. 첫줄에 입력될 명령어의 갯수를 입력받으니 for문을 사용하였고, 스택의 모든 값을 받을 때는 while문을 사용하였다. 다음은 내가 작성한 main() 함수이다.

 

#include <stdio.h>

int main(void) {

	int num;
	Stack stack;

	scanf("%d", &num);
	getchar();

	for (int i = 0; i < num; i++) {
		
		int input;
		scanf("%d", &input);
		getchar();

		if (input) {
			stack.push(input);
		}
		else {
			stack.pop();
		}
	}

	int buff;
	int total = 0;

	while ((buff = stack.pop()) != -1) total = total + buff;

	printf("%d", total);

	return 0;
}

 

 while문의 동작 해석이 조금 어려운 분들은 같은 기능을 하는 아래의 코드를 참조했으면 한다.

 

while (1) {
		buff = stack.pop();
		if (buff == -1) {

			break;

		}

		total = total + buff;
	}

 

 코드를 줄이는데 익숙해지다니...... 다시 한번 우리 교수님께 감사의 인사를 드린다 ㅎㅎ

 

3. 결어

 

 사실 이번 문제도 기본적은 스택 연산을 구현하고 그것을 확인하는 문제이기때문에 그렇게 어렵지는 않았다. 다음 문제도 이렇게 무난하게 풀었으면 좋겠지만 ㅠㅠ 앞으로 이런 문제는 없을 것이다. 그래도 이 블로그에는 꾸준하게 게시할것이다.