스택(stack)
Last updated
Last updated
자료 구조
스택과 관련된 내용
알고리즘에서 스택을 이용하여 문제를 푸는 방법은 직접 스택을 구현해서 푸는 것이 아니라, 각 자료구조의 특징을 이용하여 이미 만들어진 메서드를 이용하여 문제를 풀고 있기 때문에 아직 자료구조를 배우지 않은 1학년분들도 쉽게 따라올 수 있습니다.
참고로 C++을 아시는 분들은 작년 KOALA 회장님이 지난 겨울 방학 때 진행한 영상도 있으므로 참고하시면 좋을 것 같습니다.
스택은 값이 들어가는 입구와 나가는 출구가 같은 자료구조 입니다. 그래서 마지막으로 들어간 값이 첫 번째로 나오는 Last In First Out(LIFO)구조를 가졌습니다.
이게 무슨 소리인지 그림들을 통하여 살펴봅시다.
이렇게 아래가 막혀있고, 위가 뚫려있는 상자가 있을 때, 값이 들어가는 곳과 나오는 곳이 같으므로 이것은 스택입니다. 이 그림을 보면 알 수 있듯이 가장 먼저 들어가는 값이 맨 아래로 들어가서 차곡차곡 쌓이게 됩니다. 생긴 것이 상자에 물건을 넣을 때와 비슷하게 생겼습니다.
이렇게 4번 상자까지 스택에 들어갔다고 가정할 때, 들어가는 입구와 출구가 같기 때문에 값이 빠져나가는 과정은 아래 사진처럼 4 → 3 → 2 → 1이 되겠네요.
스택을 이용한 알고리즘 문제를 풀 때 알고 있어야 하는 특징은 이게 끝입니다. 스택 자료구조는 LIFO이다, 마지막 값이 제일 먼저 들어간다, ... 이런 내용을 외울 필요 없이 한쪽이 열려있는 상자와 박스 모양 그림만 떠올리면 됩니다.
스택은 리스트(list)로 만들 수 있습니다. 리스트의 메소드를 이용하여 만들 수 있는데 바로 append() 메소드와 pop() 메소드입니다. 이 메소드들은 이미 우리가 2주차에서 배우고 계속 사용하고 있었습니다. 이것을 그냥 스택처럼 생각해서 이용하면 됩니다.
위에 있는 그림을 코드로 만들어봅시다.
이렇게 값을 추가해주면 오른쪽 끝에 값이 추가되는 것을 확인할 수 있습니다.
이제 값을 빼는 코드를 만들어봅시다.
마찬가지로 값을 빼줄 때도 오른쪽 끝에서 값이 빠져나오는 것을 확인할 수 있습니다. 간단하죠?
다른 기능들은 아래 문제를 통해 풀어봅시다.
스택은 5가지 명령을 가지고 있다고 합니다.
일단 입력값을 받는 코드를 만들기 전에 예제1 입력 값부터 살펴봅시다.
top, size, empty, pop은 전부 입력 값이 한 개이지만, push 1과 push 2와 같이 push는 입력 값이 2개로 이루어져 있습니다.
그래서 입력 값을 리스트로 받아서 push, top, size, empty, pop은 arr[0]로 받고, push다음에 들어오는 값은 arr[1]로 받을 수 있겠네요.
이제 입력 값을 받는 코드를 만들어봅시다. 이 문제는 일단 빠른 입력을 필요로 합니다.
이제 본문에 설명된 순서인 push, pop, size, empty, top 순서대로 만들어봅시다.
push X는 입력 값이 2개이고, X는 숫자값이므로 arr[1]의 값을 int형으로 바꿔야 한다는 생각이 들 수 있습니다. 하지만 여기서는 스택에 넣는 값 가지고 다른 연산을 하지 않기 때문에 굳이 int형으로 바꾸지 않아도 될 것 같네요.
push 기능은 스택에 X 값을 넣어주는 것이므로 append 메소드를 이용하여 만들어주면 됩니다.
pop은 위에서 배운 내용대로 pop 메소드를 사용하면 됩니다. 그리고 스택에서 뺀 정수를 출력하는데, 만약 스택에 뺄 정수가 없으면 -1을 출력하라고 합니다.
이것은 len()함수를 통하여 len(stack)이 0이면 -1을 출력, 아니면 stack.pop()을 출력하면 됩니다.
스택에 들어있는 정수의 개수를 출력하라고 합니다.
스택에 들어있는 정수의 개수, 즉 요소의 개수를 출력하라는 말인데요. 이것도 pop에서와 마찬가지로 len()함수를 통하여 출력할 수 있습니다.
스택이 비어있으면 1, 아니면 0을 출력하라고 합니다. 이것도 len()함수를 이용하여 만들 수 있습니다.
마지막으로 top은 스택의 가장 위에 있는 정수를 출력하라고 합니다. 예제 1 출력 값을 보니 push 1, push 2, top을 입력하면 2를 출력하고 있습니다. 이것은 우리가 스택의 특징을 배울 때 봤던 위가 뚫려있는 상자에서 맨 위 값을 출력하면 될 것 같습니다. 리스트에서는 맨 오른쪽의 값을 출력해야겠네요.
그리고 스택에 정수가 없을 때는 -1을 출력하라고 합니다. 이것도 len()함수를 이용하여 만들 수 있습니다.
이렇게 코드를 완성하면 끝입니다.
이제 스택을 이용한 문제를 풀어보겠습니다.
아치형 곡선을 그리는데, 선끼리 교차하지 않고 A는 A끼리, B는 B끼리 쌍을 지을 수 있다면 그 단어는 좋은 단어라고 합니다.
아치형 곡선인데 선끼리 교차하지 않는다는 것은 예제 1을 그림으로 그려보면 아래와 같습니다.
ABAB는 선끼리 교차하므로 좋은 단어가 될 수 없고, AABB는 AA, BB곡선이 따로 떨어져 있으므로 교차하지 않으니 좋은 단어, ABBA는 BB위에 AA곡선이 있지만 둘이 교차하지 않으므로 좋은 단어 입니다.
이걸 보니까 문자 A가 나오면 스택 맨 위 값이 A일 경우 stack.pop()을 하여 스택 맨 위에 있던 값인 A를 빼 주고, 마찬가지로 문자 B가 나오면 스택 맨 위 값이 B일 경우 stack.pop()을 해주면 되겠네요. 그게 아니라면 전부 append()로 추가해주면 될 것 같습니다.
이제 입력 값을 받아봅시다.
이제 스택에 값을 넣어야 하는지, 빼야 하는 결정하려면 문자를 확인할 때, 맨 위 값을 비교하여 append를 사용할지, pop을 사용할지 결정해야겠죠?
이것은 stack[-1]을 통해 확인할 수 있습니다. 그런데 스택에 값이 들어있지 않으면 stack[-1]을 사용할 때 오류를 출력하므로 if문을 이용하여 stack에 값이 있는지 없는지 확인해봐야 합니다.
그래서 스택에 값이 들어있으면 stack[-1]을 사용해서 진행하고, 없으면 무조건 append를 이용하여 값을 넣어줘야겠네요.
이제 문제에서 요구하는 구현은 끝났고, ans변수를 통하여 좋은 단어의 개수를 출력해야 합니다. 좋은 단어일 경우 스택이 비어있으므로 len()함수를 이용해 ans += 1을 해주고, 마지막에 ans를 출력을 해주면 됩니다.
풀어볼 문제
