본문 바로가기

IN DEPTH CAKE

(40)

[c++/LeetCode-Stack] 1047. Remove All Adjacent Duplicates In String 난이도: EASY키워드: Stack 문제 소문자 영어 알파벳으로 이루어진 문자열 s가 주어집니다. 중복 제거는 서로 인접하고 같은 글자 두 개를 선택하고 제거하는 것으로 구성됩니다.`s` 에서 더 이상 중복 제거를 할 수 없을 때까지 반복하여 수행합니다.모든 이러한 중복 제거가 완료된 후 최종 문자열을 반환합니다. 답이 유일함이 증명될 수 있습니다. 문제 원문: https://leetcode.com/problems/remove-all-adjacent-duplicates-in-string/description/ 문제 풀이class Solution {public: string removeDuplicates(string s) { vector stack; for(a..

[c++/LeetCode-Stack] 155. MinStack 난이도: Medium키워드: Stack 문제 상수 시간 내에 push, pop, top 및 최소 요소를 검색하는 스택을 설계하십시오.MinStack 클래스를 구현하십시오:- MinStack()는 스택 객체를 초기화합니다.- void push(int val)는 요소 val을 스택에 넣습니다.- void pop()은 스택의 맨 위의 요소를 제거합니다.- int top()은 스택의 맨 위 요소를 가져옵니다.- int getMin()은 스택에서 최소 요소를 검색합니다.각 함수에 대해 O(1) 시간 복잡도를 가진 솔루션을 구현해야 합니다. 문제 풀이 - O(1) 시간 내에 min 값을 반환하기 위해 추가 메모리를 써서 min 값을 반환할 수 있게 min_stack을 추가로 선언한다.- min_stack 값에 ..

[c++/LeetCode-2DArray] 48. Rotate Image 난이도: Medium키워드: Array 문제 주어진 n x n 2차원 행렬은 이미지를 나타냅니다. 이 이미지를 90도(시계 방향)로 회전하십시오.이미지를 제자리에서 (in-place) 회전해야 하므로 입력 2차원 행렬을 직접 수정해야 합니다.다른 2차원 행렬을 할당하여 회전하지 마십시오. 문제 원문 : https://leetcode.com/problems/rotate-image/description/ 문제 풀이: 참고로, 이번 포스팅으로 정리한 코드는 속도가 빠른 solution은 아니다. 다만 문제 해결 과정과 같이 정리해보면 좋지 않을까 싶다.일단 문제를 이해하는 과정부터 시작해보면, 문제에서 제시한 조건을 간단한 예시를 통해 이해하는 것이 필요하다. 나는 3 x 3 예제를 사용해서 문제를 분석했다..

[c++/LeetCode-Array] 75. Sort Colors 난이도: Medium키워드: Array 문제주어진 배열 nums에는 빨간색, 흰색 또는 파란색으로 색칠된 n개의 객체가 있습니다. 이들을 그 자리에서 정렬하여 동일한 색상의 객체가 서로 인접하도록 만듭니다. 이때 색상은 빨간색, 흰색 및 파란색 순서로 배열됩니다.빨간색, 흰색 및 파란색을 각각 나타내기 위해 정수 0, 1 및 2를 사용할 것입니다.라이브러리의 정렬 함수를 사용하지 않고 이 문제를 해결해야 합니다. 문제 원문: https://leetcode.com/problems/sort-colors/description/ 문제 풀이 색상 개수가 많지 않으니까 target 색상을 바꿔가면서 sorting을 하자in_place 로 sorting을 해야하니까, swap해야할 index를 기억해가면서 swa..

[c++/LeetCode-Array] 56. Merge Intervals 난이도: Medium키워드: Array 문제 문제원문: https://leetcode.com/problems/merge-intervals/description/주어진 간격 배열에서, intervals[i] = [starti, endi]인 간격들이 있을 때, 겹치는 모든 간격을 병합하고, 입력된 모든 간격을 포괄하는 겹치지 않는 간격들의 배열을 반환하시오. 문제 풀이 겹치는 구간들을 합쳐주기위해서, intervals 를 start time 기준으로 sorting하고 merge를 진행한다. 그러면 sort는 O(n log n)이 보장되고, sorting 된 array에 대해서 merge만 해주면 되므로 O(n). 최종적으로 O(n log n) 복잡도로 해결. #include #include using na..

[c++/LeetCode-Array] 162. Find Peak Element 난이도: Medium키워드: Array 문제문제 원문: https://leetcode.com/problems/find-peak-element/description/ Peak 요소는 이웃보다 엄격하게 큰 요소를 뜻한다. 0부터 색인이 지정된 정수 배열 nums가 주어졌을 때, Peak 요소를 찾고 해당 색인을 반환하라. 배열에 여러 개의 Peak이 포함되어 있으면 어떤 Peak의 색인이든 반환할 수 있다.nums[-1] = nums[n] = -∞로 간주해도 된다. 즉, 배열 외부에 있는 이웃보다 요소는 항상 엄격하게 크다고 간주된다.O(log n) 시간 내에 실행되는 알고리즘을 작성해야 한다. 문제 풀이 문제 자체만 놓고 보면 Medium 난이도는 아니다. 가장 쉽게 생각해보면 O(n) 안에 itera..

[Hello! c++] constexpr const char *에 대해서 안녕하세요. 오늘 포스팅에서 다룰 내용은 constexpr const char * 에 대한 이야기입니다. 이 요상하게 생긴 문법이 맞는 표현인지 이야기해보도록 하죠. 우선, constexpr이 뭔가? constexpr는 일반적으로 const와 유사하지만, const 보다 좁은 개념으로 여겨집니다. 일단 알아둘 점은 constexpr를 쓰면 뒤에 오는 내용이 const라고 선언하는 것입니다. 그런점에서 const와 다를 게 없죠. 그러면 두 개가 같은 건가요? 아니오, constexpr는 const로 대체가 가능하지만, const는 constexpr로 항상 대체될 수 있는 것이 아닙니다. 무슨말이냐면, constexpr는 const처럼 뒤에 오는 식이 변하지 않는 "constant (상수)"임을 의미한다는..

[코딩/LeetCode150-(11)] 274. H-Index 본 글은 LeetCode Top Interview 150에 정리된 문제를 요약하고 이에 대한 개인적인 풀이를 포함하고있습니다. 본 포스팅 시리즈는 150 list의 순서를 따라서 게재됩니다. 풀이 언어는 python3을 사용합니다. 난이도: Medium 키워드: Array, Sorting 문제 문제 원문: https://leetcode.com/problems/h-index/description/?envType=study-plan-v2&envId=top-interview-150 정수 배열 citations 이 주어질 때 H-index를 반환해라 문제 풀이 class Solution: def hIndex(self, citations: List[int]) -> int: citations.sort(reverse..

이전 1 2 3 4 5 다음

티스토리툴바