[백준 알고리즘] 10828번

1. 문제와 실행결과 예시

백준 알고리즘을 풀어보았다...... 단계별로 풀기로 쭉 풀이를 진행하였지만 기초적인 문제를 제외하고 자료구조나 알고리즘같은 응용문제를 블로그에 정리할까 한다 ㅎㅎ 문제는 다음과 같다.

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

보다시피 기본적인 스택 연산을 구현하는 스택 문제이다. 조금 다른 점이 있다면 입력받은 수 만큼 명령어를 받고 명령어를 실행하는 것? 이것을 제외하면 책에서 읽은 (학교에서 배운) 스택문제와 똑같다. 나름 연결리스트를 사용하고 싶었지만, 최대 입력값이 주어졌기에, 배열로 구현했다. 클래스를 사용한 이유는 복습도 하고 클래스 공부도 할겸 ㅎㅎ...... 같은 문제를 연결리스트로 구현한 스택으로 풀어 다시 이 블로그에 올렸으면 좋겠다 ㅎㅎ 다음은 실행결과 예시이다.

- 실행결과 예시

2. 문제 풀이

나는 (다른 분들은 아닐 수 있겠지만......) 자료구조를 구현할 때 무조건 자료구조를 구현한 후 main() 함수를 작성한다. 아마 1학년 때 자료구조를 혼자 공부할 때 내가 구현한 자료구조가 맞는지 판단하기위해 main() 함수를 작성했는데 그게 습관이 된듯 하다...... 일단 전체적인 자료구조 Class의 변수는 간단하다. 특히 배열로 구현하는 Stack은 아마 자료구조 중에서 가장 간단하지 않을까 싶다. (지금까지 내가 만난 자료구조 구현에 한해서입니다.) 다음은 생성자와 변수들이다.

- 생성자와 구성 변수

class Stack {
private:

	int stack[SIZE];
	int top;

public:
	Stack() { top = -1; }
};

다시 한번 말하지만 Stack은 나름 간단한 구조에 속한다. 연산을 깊게 이해하고 있다면 그렇게 어려운 정도도 아니다. 생성자도 top변수에 -1을 대입하기만 하면 된다! 자 이제 필요한 연산들을 하나하나 작성해보자.

- push() 메소드

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

매우 간단하다! 분명 예전 같았으면 아래와 같이 작성했을 것이다.

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

하지만 우리 자료구조 교수님을 만난 뒤로...... 코드 줄 수를 줄이는데 나도 모르게 신경쓰고 있었다 ㅎㅎ 교수님 감사합니다 ㅎㅎ

- pop() 메소드

pop() 메소드도 어려운 점은 없다. 주의할 점은 반드시 top함수의 값이 변해야 하며, 변하기 전의 값을 반환해야 한다는 것이다. 다음은 내가 작성한 코드이다.

int pop() {
	if(top == -1){
    	return-1;
    }
    else{
    	int buff = top;
        top = top - 1;
        return stack[buff];
}

다시 한번 말하지만, 내가 저 코드를 만약 자료구조 과제로 제출했다면 하핳 정말 심하게 혼났을 것이다...... 다행이도 저 코드는 한 줄로 작성될 수 있다! 다음은 내가 처음으로 작성한 코드이다! 사실 저 위의 코드는 과거의 나를 보여주는 코드이다 ㅎㅎ

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

사랑해요 3항 연산자 ㅠㅠ 문법에 관한 설명은 이 카테고리에서 다루지 않기에 3항 연산자에 대한 설명은 하지 않겠다! (문법을 다루는 카테고리도 빨리 만들고 싶지만 ㅠㅠ 왜 시간이 없는걸까 ㅠㅠ)

- size() 메소드

size() 메소드의 기능은 간단하다! 바로 스택에 들어있는 정수의 갯수를 출력하는 것이다. 많은 방법이 있을 것이다. 나는 top을 사용하는 것이 가장 좋다고 생각했다. 왜냐하면 top에 1을 더하면 요소의 갯수가 나오기 때문이다! 덕분에 이 메소드도 한 줄로 끝낼 수 있었다!

int size() {
	return top + 1;
}

- empty() 메소드

empty() 메소드도 한 줄로 작성할 수 있다! 3항 연산자를 사용하면 ㅎㅎ 경우의 수가 두개밖에 없고 이 두가지의 경우의 수 모두 한줄로 표현 가능하기 때문에 한 줄로 구현할 수 있는 것이다. 다음은 내가 작성한 코드이다.

int empty() {
	return top == -1 ? 1 : 0;
}

- top() 메소드

드디어 마지막이다! ( 아직 시간이 제일 오래걸린 main()이 남았지만 ㅠㅠ ) top()의 기능은 간단하다. -1 이면 -1을 반환하고 아니면 0을 반환하면 된다! 다음은 top() 메소드의 코드이다.

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

- main() 함수

자, 드디어 main()함수이다! 사실 문제를 풀기 전, 제일 간단해 보였지만 실제로 시간이 엄청 걸렸다. ( 중간에 화나서 롤하러 갔는데, 이 시간을 제외해도 가장 오래 걸렸다. ) 거두 절미하고 문제는 문자열에 대한 입력! scanf() 함수가 엔터를 입력받고 ( 관련검색어: 입력버퍼, scanf() ) 입력받는 문자열을 배열로 다루기 보단 문자열 포인터를 사용하는 것이 더 현명했으며! 바보같이 문자열 비교를 할 때 비교 연산자 '=='를 사용했다는 것이다! 이 세가지로 나는 힘을 다 뺐다 ㅠㅠ ( 사실 이렇게 힘을 안 뺐으면 훨씬 빨리 끝났을 수도 ㅠㅠ) 이것에 대한 오류 내용은 무!조!건! 정리해서 올릴 것이다...... 겁나 힘들었기 때문이다 ㅠㅠ 다음은 내가 작성한 main() 함수이다.

int main(void) {

	int num, trash;
	char *input = (char*)malloc(sizeof(char) * 10);
	Stack arr = Stack();
	scanf("%d", &num);
	getchar();

	for (int i = 0; i < num; i++) {
		scanf("%s", input);
		
		if (!strcmp(input, "push")) {
			int buff;
			scanf("%d\n", &buff,&trash);
			arr.push(buff);
		}
		else if (!strcmp(input, "top"))
			printf("%d\n", arr.getTop());
		else if (!strcmp(input, "empty"))
			printf("%d\n", arr.empty());
		else if (!strcmp(input, "size"))
			printf("%d\n", arr.size());
		else if(!strcmp(input, "pop"))
			printf("%d\n", arr.pop());
	}
	return 0;
}

많은 사람들이 입력 명령어를 받을 때 (num) 와 push되는 요소를 받을 때 (buff) 가 왜 다른지를 궁금해 할 것이다. 사실 두가지 방법은 같은 기능이다. 그저, 정말 같은 기능을 하는지 궁금해서 두가지 방법을 동시에 사용한 것이지 특별한 이유는 없다. 실제로 저 두 방법을 각자의 위치에 사용해도 main() 함수는 똑같이 작동한다. (물론 메모리는 다르겠지만 결과적으로!) 밑은 기존 코드를 주석처리하고, 서로의 방법을 바꿔서 코드를 작성한 예이다.

int main(void) {

	int num, trash;
	char *input = (char*)malloc(sizeof(char) * 10);
	Stack arr = Stack();
	scanf("%d", &num, &trash);
	//getchar();

	for (int i = 0; i < num; i++) {
		scanf("%s", input);
		
		if (!strcmp(input, "push")) {
			int buff;
			//scanf("%d\n", &buff,&trash);
			scanf("%d", &buff);
			getchar();
			arr.push(buff);
		}
		else if (!strcmp(input, "top"))
			printf("%d\n", arr.getTop());
		else if (!strcmp(input, "empty"))
			printf("%d\n", arr.empty());
		else if (!strcmp(input, "size"))
			printf("%d\n", arr.size());
		else if(!strcmp(input, "pop"))
			printf("%d\n", arr.pop());
	}
	return 0;
}

다시 한번 말하지만, 위의 내용은 블로그에 한 번 정리하여 올릴것이다. (지금까지 내가 가장 많이 겪은 문제들이다 ㅠㅠ)

- 전체 코드

#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--];
	}

	int size() {
		return top + 1;
	}

	int empty() {
		return top == -1 ? 1 : 0;
	}

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

#include <cstdio>
#include <cstring>
#include <cstdlib>

int main(void) {

	int num, trash;
	char *input = (char*)malloc(sizeof(char) * 10);
	Stack arr = Stack();
	scanf("%d", &num, &trash);
	//getchar();

	for (int i = 0; i < num; i++) {
		scanf("%s", input);
		
		if (!strcmp(input, "push")) {
			int buff;
			//scanf("%d\n", &buff,&trash);
			scanf("%d", &buff);
			getchar();
			arr.push(buff);
		}
		else if (!strcmp(input, "top"))
			printf("%d\n", arr.getTop());
		else if (!strcmp(input, "empty"))
			printf("%d\n", arr.empty());
		else if (!strcmp(input, "size"))
			printf("%d\n", arr.size());
		else if(!strcmp(input, "pop"))
			printf("%d\n", arr.pop());
	}
	return 0;
}

3. 결어

사실 나는 꾸준하게 백준 알고리즘 문제를 풀지는 않았다 ㅠㅠ 지금이라도 조금씩 백준알고리즘의 풀이를 이 블로그에 올렸으면 좋겠다!

'programming > 알고리즘 풀이' 카테고리의 다른 글

[백준 알고리즘] 10996번 - 별 찍기 21 (0)	2020.06.19
[백준 알고리즘] 별찍기-13, 별찍기-9 (2523, 2446) (0)	2020.06.19
[백준 알고리즘] 4949번 - 균형잡힌 세상 (런타임에러) (0)	2020.05.23
[백준 알고리즘] 9012번 - 괄호 검사 코드 (0)	2020.05.13
[백준 알고리즘] 10773번 (0)	2020.05.13

Blog for Programming

[백준 알고리즘] 10828번

'programming > 알고리즘 풀이' 카테고리의 다른 글

티스토리툴바

[백준 알고리즘] 10828번

'programming > 알고리즘 풀이' 카테고리의 다른 글

'programming/알고리즘 풀이' Related Articles

티스토리툴바