본문 바로가기

stack14

[C++/STL] stack을 vector로 변환하기 STL에서 stack은 컨테이너에 대한 접근을 제어하는 목적으로 사용된다. 따라서 iterator를 제공해주지 않기 때문에 iterator을 사용해서 vector를 만들어낼 수 없다. 요소를 제거하면서 vector 생성 stack st; st.push(1); st.push(2); st.push(3); vector arr(st.size()); int index = arr.size() - 1; // copy st to arr while(!st.empty()){ arr[index--] = st.top(); st.pop(); } stack에서는 top을 통해서만 요소를 가져올 수 있기 때문에 top을 이용해서 vector의 뒤에서부터 값을 채워준다. 단, 이 방법을 쓰면 기존 stack에는 요소가 더 이상 남아.. 2021. 1. 21.
[leetcode][394] Decode String 문제 : leetcode.com/problems/decode-string/ k[encoded_string] 의 룰을 가진 문자열이 주어진다. 이 룰은 encoded_string 문자열을 k번 반복한다는 뜻이다. 룰은 중첩되서 나올 수 있다. k는 반드시 숫자이며 encoded_string에는 숫자가 포함되지 않는다. 위 룰을 적용한 문자열이 주어질 때 decode한 결과를 구하라. 괄호? => 스택. 백퍼는 아니지만 대부분의 문제에 적용된다. k와 encoded_string을 pair로 가지는 스택을 만든다. 이 때 입력 문자열을 "3[a]"라 하였을 때 이는 "1[3[a]]" 와 동일하기 때문에 코드의 일관성을 맞춰주기 위해(예외처리 덜하려고. ex. "ab3[a]" 와 같은 문자열은 초기에 나오는 a.. 2020. 11. 21.
[leetcode][735] Asteroid Collision 문제 : leetcode.com/problems/asteroid-collision/ 0이 아닌 정수 값을 가진 asteroids 배열이 주어진다. 요소의 절대값은 크기를 의미하고 부호는 방향을 의미한다. 같은 방향을 가지는 운석들은 부딪히지 않는다. 다른 방향을 가지는 운석들이 만날때 크기가 크거나 같은 운석들이 파괴된다. asteroids 배열에서 충돌가능한 운석들이 충돌한 뒤 남은 운석들의 배열을 반환하라. [1,2,3,4,-5] 가 주어졌을 때, -5는 4,3,2,1을 차례대로 파괴시킬 수 있고, 만약 [1,2,6,3,-5] 과 같은 운석들이 있다면 -5 운석은 3까지만 파괴시키고 6을 만나 파괴되므로 1,2 운석은 확인하지 않아도 되기 때문에 스택을 사용했다. 배열을 앞에서부터 탐색하면서 스택에 .. 2020. 10. 24.
[leetcode][678] Valid Parenthesis String 문제 : https://leetcode.com/problems/valid-parenthesis-string/ '(', ')', '*' 로 이루어진 문자열이 입력값으로 주어진다. *은 '(', ')'가 될 수 있고 빈 문자도 될 수 있다. * 가 특정 문자로 대체될 때, 괄호들의 쌍이 맞는 경우 유효한 문자열이라 한다. 입력 문자열이 유효한 문자열인지 판단해라. 여는 괄호가 나오는 인덱스를 저장하는 스택 하나와 '*' 가 나오는 인덱스를 저장하는 deque 하나를 사용한다. 입력된 문자열을 앞에서부터 탐색하면서 스택과 deque를 채운다. 1. 탐색중인 문자가 * 인 경우 deque의 뒤에 현재 인덱스를 채운다. 2. 여는 괄호인 경우 스택에 현재 인덱스를 push 한다. 3. 닫는 괄호인 경우 3-1. .. 2020. 4. 16.
[leetcode][1209] Remove All Adjacent Duplicates in String II 문제 : https://leetcode.com/problems/remove-all-adjacent-duplicates-in-string-ii/ {문자, 문자가 연속으로 나온 횟수}를 요소로 하는 stack을 하나 만든다. 문자열 s를 앞에서부터 탐색하면서 스택이 비어있거나 스택 top에 있는 요소의 문자가 탐색중인 문자와 같다면 top 요소의 문자가 연속으로 나온 횟수를 +1 해준다. 그리고 만약 스택 top의 연속 횟수가 k와 같다면 stack을 pop 시킨다. 모든 문자열 s를 탐색하면서 stack을 세팅했다면 stack을 pop하면서 정답 문자열 앞에 문자열을 추가하면서 정답을 구할 수 있다. 시간 복잡도는 O(N). (N = |s|) 소스코드 : https://github.com/fpdjsns/A.. 2019. 10. 3.
[leetcode][1190] Reverse Substrings Between Each Pair of Parentheses 문제 : https://github.com/fpdjsns/Algorithm/blob/master/leetcode/1190.%20Reverse%20Substrings%20Between%20Each%20Pair%20of%20Parentheses.cpp 스택을 사용했다. Example 3: "(ed(et(oc))el)" 을 예로들어보자. 여는 괄호가 시작될때마다 스택을 하나씩 생성해서 이후에 나오는 문자들을 최근 스택에 쌓는다. 스택이 하나도 없는 경우 문자열 순서에 변경이 없을 것이기 때문에 정답 문자열의 뒤에 추가한다. 닫는 괄호가 나오면 최근 스택을 pop하면서 이전 스택에 push한다. 스택을 pop할때 이전 스택이 없는 경우 (스택이 하나인 경우) 정답 문자열에 추가한다. 시간복잡도는 O(|s|^2).. 2019. 10. 1.

티스토리툴바