Stack

문제 https://leetcode.com/problems/smallest-subsequence-of-distinct-characters 풀이 문자열 s에 있는 모든 개별 문자를 정확히 한 번씩 포함하는 부분수열 중, 사전순으로 가장 작은 것을 리턴하면 된다. 처음에 투 포인터를 생각했는데, 원소가 굳이 쭉 이어질 필요가 없으니 스택을 활용했다. 처음에 전처리로 각 문자의 마지막 등장 인덱스를 구해둔다. 스택 top의 마지막 인덱스가 현재 인덱스보다 크면 뒤에 또 나온다는 뜻이므로 제거할 수 있다. 스택에 문자를 추가하기 전, 아래 세 조건을 모두 만족할 때 top을 pop하면 된다. 스택이 비어있지 않다 스택 top이 현재 문자보다 크다 (사전순으로 뒤에 있다) 스택 top 문자가 뒤에 또 등장한다 (lastIndice[stack[-1]] > idx) 코드 class Solution: def smallestSubsequence(self, s: str) -> str: stack = [] lastIndice = {} for idx, c in enumerate(s): lastIndice[c] = idx for idx, c in enumerate(s): if c in stack: continue while stack and c < stack[-1] and lastIndice[stack[-1]] > idx: stack.pop() stack.append(c) return "".join(stack)

문제 https://www.acmicpc.net/problem/14719 풀이 스택 문제이다. 빗물은 양 옆이 블록으로 막혀있을 때, 낮은 블록의 높이를 기준으로 그 사이에 빗물이 고이게 된다. 따라서 스택을 하나 만들고 인덱스 순서대로 입력받은 다음에, “현재까지” 가장 높게 쌓여있던 블록의 높이(currentMax)와 같거나 더 높게 쌓여있는 블록이 스택에 들어오려 할 때, 스택에 쌓여있는 모든 블록들을 빼내면서 고여있는 물의 양을 더하면 된다(currentMax - 중간 블록의 높이). 하지만 이러한 방법을 쓰면 문제점이 하나 있는데, 블록이 계속 커진다는 보장이 없기 때문에, 마지막에 있는 블록들이 붕 뜨게 된다. 이 때는 스택을 뒤집어서 해결하면 된다. 현재 currentMax보다 더 큰 수가 앞에 존재하지 않는다면 뒤집힌 스택은 무조건 currentMax가 마지막에 존재하게 된다. (만약 currentMax보다 낮은 블록은 이미 pop된 상태일 것이기 때문에) 따라서 스택을 뒤집은 다음(혹은 다른 스택에 차례대로 옮긴 후에) 이 전의 과정을 한번 반복하면 문제가 해결된다. ...

문제 https://www.acmicpc.net/problem/2493 풀이 스택을 사용하면 쉽게 풀 수 있는 문제이다. 각 탑에서 왼쪽에 신호를 발사하므로, 현재 인덱스보다 앞에 있는 인덱스중 가장 먼저 나오는 값이 더 큰 인덱스를 찾으면 된다. 현재 인덱스의 탑과 스택의 top에 있는 인덱스의 탑을 비교한다. top 인덱스의 탑이 더 크면 이 인덱스에 있는 탑은 처음으로 신호를 받는 탑이므로, answer 배열에 추가한다. 그렇지 않다면, 해당 인덱스에 있는 탑은 신호를 받지 못하는 탑 이므로 스택에서 제거한다. 현재 인덱스가 다음 인덱스들의 신호를 받을 수 있으므로 스택에 현재 인덱스를 추가한다. ...

문제 https://www.acmicpc.net/problem/17298 풀이 스택을 이용하는 문제이다. 2493번 문제와 사실상 같은 문제인데, 배열이 뒤집혀 있다는 것과 인덱스가 아닌 해당 인덱스에 대응하는 값을 사용하는 것이 다르다. 코드 Swift import Foundation let n = Int(readLine()!)! let a = Array(readLine()!.split(separator: " ").map { Int(String($0))! }.reversed()) var stack: [Int] = [] var answer: [Int] = [] for element in a { while !stack.isEmpty && stack.last! <= element { stack.removeLast() } if let last = stack.last { answer.append(last) } else { answer.append(-1) } stack.append(element) } print(answer.map { String($0) }.reversed().joined(separator: " ")) C++ #include <iostream> #include <vector> #include <algorithm> using namespace std; int main() { int n; cin >> n; vector<int> a; for(int i = 0; i < n; i++) { int temp; cin >> temp; a.push_back(temp); } vector<int> stack; vector<int> answer; reverse(a.begin(), a.end()); for(int element: a) { while(!stack.empty() && stack.back() <= element) { stack.pop_back(); } if(stack.empty()) { answer.push_back(-1); } else { answer.push_back(stack.back()); } stack.push_back(element); } for(int answerIndex = (int)answer.size() - 1; answerIndex >= 0; answerIndex--) { cout << answer[answerIndex] << " "; } }