본문 바로가기

stack14

[Leetcode] 71. Simplify Path 문제 : https://leetcode.com/problems/simplify-path/description/ 주어진 문자열 path는 Unix 스타일 파일 시스템에서 파일 또는 디렉토리까지의 절대 경로(슬래시('/')로 시작)입니다. 이를 간소화된 카노니컬 경로로 변환하세요. Unix 스타일 파일 시스템에서 마침표(.)는 현재 디렉토리를 의미하며, 두 개의 마침표(..)는 상위 디렉토리를 의미합니다. 여러 개의 연속된 슬래시(//)는 하나의 슬래시(/)로 처리됩니다. 이 문제에서는 '...'와 같은 다른 마침표 형식은 파일, 디렉토리 이름으로 처리됩니다. 카노니컬 경로는 다음과 같은 형식을 가져야 합니다: 1. 경로는 슬래시(/)로 시작합니다. 2. 두 개의 디렉토리는 하나의 슬래시(/)로 구분됩니다... 2023. 4. 12.
[Leetcode] 2390. Removing Stars From a String 문제 : https://leetcode.com/problems/removing-stars-from-a-string/description/ 문자열 s가 주어지며, s는 별표(*)를 포함합니다. 한 번의 작업에서 다음을 할 수 있습니다: s에서 별표 하나를 선택합니다. 그 별표 왼쪽에서 가장 가까운 비 별표 문자를 제거하고, 그 별표 자체도 제거합니다. 모든 별표가 제거된 후의 문자열을 반환합니다. 참고 - 입력은 항상 작업이 가능하도록 생성됩니다. - 결과 문자열은 항상 고유함이 보장됩니다. stack을 사용합니다. 문자를 앞에서부터 탐색하면서 별표가 아닌 문자인 경우 스택에 문자를 넣습니다. 별표인 경우 스택의 탑에 있는 문자를 제거합니다. 모든 문자열을 탐색했으면 스택에서 문자를 제거하면서 정답 문자열.. 2023. 4. 11.
[Leetcode] 20. Valid Parentheses 문제 : https://leetcode.com/problems/valid-parentheses/description/ '(', ')', '{', '}', '[', ']' 문자만 포함하는 문자열 s가 주어집니다. 입력 문자열이 유효한지 여부를 판단하세요. 입력 문자열이 유효한 경우는 다음과 같습니다. 열린 괄호는 같은 종류의 괄호로 닫혀야 합니다. 열린 괄호는 올바른 순서로 닫혀야 합니다. 각 닫는 괄호는 동일한 유형의 열린 괄호와 대응 되어야 합니다. 문자열을 탐색하면서 열린 괄호가 나오면 스택에 넣습니다. 닫힌 괄호가 나오는 경우 스택의 탑에 있는 괄호와 대응되지 않거나 스택이 비어있을 땐 유효한 경우가 아닙니다. 스택의 탑에 있는 열린 괄호와 탐색 중인 닫힌 괄호가 대응된다면 스택의 탑에 있는 문자.. 2023. 4. 10.
[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.