본문 바로가기

stack11

[Leetcode] 32. Longest Valid Parentheses 문제 : https://leetcode.com/problems/longest-valid-parentheses/ '(', ')' 문자만 포함한 문자열이 주어질 때, 가장 긴 유효한 괄호 부분 문자열의 길이를 구하여라. DP + Stack dp[i] = s[~i] 문자열에서 s[i]를 포함한 부분 문자열의 가장 긴 유효한 괄호 부분 문자열 길이. stack 열린 괄호 문자 인덱스 문자열 s를 앞에서부터 탐색하면서 열린 괄호 문자면 스택에 저장하고 닫힌 괄호 문자이면서 스택에 값이 있으면 top 값을 가져온다. top은 현재 탐색 중인 닫힌 괄호 문자와 매칭 되는 열린 괄호 문자의 인덱스(let, index)이며 dp[i] = (i - index + 1) + dp[index-1] dp의 점화식은 위와 같다. .. 2022. 5. 24.
[Leetcode] 739. Daily Temperatures 문제 : https://leetcode.com/problems/daily-temperatures/ 일별 온도 정수 배열이 주어지면 해당 날짜에서 볓 번째 날이 지났을 때 해당 날짜의 온도보다 더 높은 온도를 얻을 수 있는지 저장한 배열을 구하라. 만일 가능한 날이 없다면 0을 저장해라. 배열을 뒤에서부터 탐색하면서 stack에 탐색하는 일자의 온도보다 높은 온도만 존재하게 유지한다. 탐색하면서 만일 stack에 탐색 일자의 온도보다 높은 온도가 존재하지 않는다면 0, 존재한다면 stack의 top에 있는 온도의 인덱스에 현재 인덱스를 뺀 값을 정답 배열에 저장한다. Ex) temperatures = [73,74,75,71,69,72,76,73] 시간복잡도는 O(N) 소스코드 C++ : https://gi.. 2021. 11. 13.
[leetcode][13] Roman to Integer 문제 : leetcode.com/problems/roman-to-integer/ 로마 문자를 숫자로 1:1 매칭하는 map을 하나 만든다. 문자열 s를 처음부터 탐색하면서 문자를 숫자로 바꾼 결과(let, value)를 stack에 넣는다. 만약 value가 1이 아니라면 바로전 값이 1, 10, 100인지 확인하고 그 값의 5, 10의 배수가 value와 맞는지 비교해야 한다. 이를 위해 바로 전 값을 stack의 top에서 가져온 뒤 판단한다. 만약 마이너스가 되는 경우라면 value에 top 값을 빼주면서 stack을 pop 해준다. value를 적절히 갱신 후 stack에 push 한다. 문자열 s를 모두 탐색해서 stack을 다 채웠다면 stack의 모든 숫자를 더한 값이 정답이 된다. 시간복잡.. 2021. 2. 21.
[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.