본문 바로가기

🧩 Algorithm19

LeetCode : 155. Min Stack 문제 링크 문제 먼저 읽기 푸시, 팝, 탑, 최소 요소 검색을 일정 시간 내에 지원하는 스택을 구현하시오. 어떻게 풀까? 생각 ArrayList 혹은 int[]로 구현해볼 수 있다. 수도코드 class MinStack { private List stack; private List minStack; // 최소값 저장 스택 public MinStack() { // 스택 초기화 this.stack = new ArrayList(); this.minStack = new ArrayList(); } public void push(int val) { if (stack.size() == 0) { // 첫요소일 때. 처음에 이부분을 생각하지 못해서 emptyStackException이 발생했었다. this.minStack.. 2023. 9. 1.
LeetCode : 150. Evaluate Reverse Polish Notation 문제 링크 문제 먼저 읽기 문자 배열이 주어집니다. 문자는 각각 사칙 연산 1글자씩이거나 숫자인데 Reverse Polish Notation (후위 표기법)산술식을 나타냅니다. 연산의 결과를 반환하세요. Input: tokens = ["10","6","9","3","+","-11","*","/","*","17","+","5","+"] Output: 22 Explanation: ((10 * (6 / ((9 + 3) * -11))) + 17) + 5 = ((10 * (6 / (12 * -11))) + 17) + 5 = ((10 * (6 / -132)) + 17) + 5 = ((10 * 0) + 17) + 5 = (0 + 17) + 5 = 17 + 5 = 22 그 외 조건 1 2023. 8. 31.
LeetCode : 167. Two Sum II - Input Array Is Sorted 문제 링크 문제 먼저 읽기 오름차순으로 정렬되고 인덱스 1부터 시작하는 배열이 주어집니다. 합하여 특정 목표 숫자를 만드는 두 인덱스를 정수 배열로 반환하세요. 반환되는 정수 배열은 [index1, index2] 로 길이가 2이며 index1 < index2 입니다. 반드시 하나의 해결책이 있습니다. 동일한 요소를 2번 쓸 일은 없습니다. 어떻게 풀까? 생각 2개의 pointer로 합을 비교합니다. pointer는 양 끝에 위치하여 한쪽 방향으로만 움직이게 합니다. target number와 같으면 멈추고 반환합니다. 수도코드 class Solution { public int[] twoSum(int[] numbers, int target) { int pointerA = 0; int pointerB = n.. 2023. 8. 27.
LeetCode : 125. Valid Palindrome 문제 링크 문제 먼저 읽기 어떤 문자 s가 주어질 때, Palindrome 조건인 문자열이면 ture를 반환합니다. Palindrome 는 모든 대문자를 소문자로 변환 후 영어 혹은 숫자가 아닌 문자를 제거한 후 앞뒤가 같은 문자를 말합니다. Input: s = "A man, a plan, a canal: Panama" Output: true 어떻게 풀까? 생각 양 끝부터 중앙으로 향하는 포인터를 사용하여 다른 것이 나오면 false를 반환해보면 어떨까? 이경우 시간복잡도 O(n/2)가 될 것이라 예상됩니다. 영어나 숫자가 아닌 다른 문자가 나오면 다음으로 문자를 가르키도록 합니다. 수도코드 class Solution { public boolean isPalindrome(String s) { int po.. 2023. 8. 27.
LeetCode : 189. Rotate Array 문제 링크 문제 먼저 읽기 정수 배열 nums 가 주어집니다. 배열을 오른쪽으로 k 번 숫자를 이동시킵니다. Input: nums = [1,2,3,4,5,6,7], k = 3 Output: [5,6,7,1,2,3,4] Explanation: rotate 1 steps to the right: [7,1,2,3,4,5,6] rotate 2 steps to the right: [6,7,1,2,3,4,5] rotate 3 steps to the right: [5,6,7,1,2,3,4] Follow up 최대한 다양한 방법으로 풀어보세요. 적어도 3가지 방식으로 풀 수 있습니다. 제자리에서 O(1) 의 공간 복잡도로 풀 수 있을까요? 어떻게 풀까? 생각 index에 k-1만큼 더해주고 최대값으로 나눈 나머지를 i.. 2023. 8. 25.
LeetCode : 169. Majority Element 문제 링크 문제 먼저 읽기 크기가 n인 nums 정수 배열이 주어집니다. 요소 안에서 과반수 요소인 정수를 반환합니다. O(1) 로 풀 수 있는 방법이 있는 것 같다. Input: nums = [2,2,1,1,1,2,2] Output: 2 어떻게 풀까? 생각 nums가 정렬되어 있지 않다는 점을 어떻게 풀지 고민이 되었다. 각 숫자가 얼마나 나오는지 개수를 셀 수 있다. (Map collection 사용) 매번 이 방법을 사용해왔었다. 혹은 등장하는 숫자 개수가 2개이므로, 최소한의 변수로 과반수를 체크할 수 있지 않을까? 수도코드 class Solution { public int majorityElement(int[] nums) { int major = 0; // 과반수인 숫자를 저장한다. int co.. 2023. 8. 25.
LeetCode : 80. Remove Duplicates from Sorted Array II 문제 링크 문제 먼저 읽기 오름차순으로 정수 nums 가 주어진다. 각 고유 요소가 최대 두 번만 나타나도록 중복된 요소를 같은 배열안에서 제거합니다. 요소의 상대적 순서는 동일하게 유지해야 합니다. java는 배열 길이를 변경할 수 없으므로, 결과를 배열 nums의 index 0부터 배치합니다. 중복 제거한 후 요소가 개수를 반환합니다. Input: nums = [1,1,1,2,2,3] Output: 5, nums = [1,1,2,2,3,_] 어떻게 풀까? 생각 이제 요소가 몇개씩 가능한지 저장해야합니다. 순서를 그대로 유지하며 저장되는 개수를 저장해야하므로, 지금 포인터가 요소를 저장할 수 있는 개수를 초기화하며 풀 수 있지 않을까요? 별도의 자료구조를 더 정의하는 것은 메모리를 추가로 더 사용하므로.. 2023. 8. 25.
LeetCode : 26. Remove Duplicates from Sorted Array 문제 링크 LeetCode - The World's Leading Online Programming Learning Platform Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 문제 먼저 읽기 정수 배열 nums는 오름차순으로 정렬되어 주어진다. 중복된 요소를 제거하자. 요소의 상대적인 순서는 동일하게 유지해야 한다. nums를 변경해야한다. 고유 요소 수보다 큰 index의 나머지 요소는 상관없다. 고유 요소 수를 정수 반환한다. 어떻게 풀까? 생각 같은 방식으로 포인터로 .. 2023. 8. 25.

티스토리툴바