👨🏻‍💻 PS

[Java] 2. Add Two Numbers

문제 파악 비어있지 않은 두개의 연결 리스트가 주어진다. 음수가 아닌 정수의 숫자를 역순으로 연결리스트에 보관되어있다. ex. 342 인 경우 연결리스트에 [2] -> [4] -> [3] 으로 구성 연결리스트로 표현되는 두 정수의 합을 동일한 방식으로 연결리스트로 반환해야한다. 풀이 1️⃣ 💡 떠오른 Idea l1의 val과 l2의 val을 더하고 10으로 나눈 몫과 나머지를 구한다. 10으로 나눈 몫은 다음 노드들의 val 합에 더해주어야 한다. 나머지를 통해 노드 클래스를 만들어 이전 노드의 next 노드로 연결해준다. 그리고, l1 과 l2의 길이가 다를 수 있다. 따라서, l1 과 l2가 둘다 null이 아니라면 로직을 계속 수행해야한다. 또한, 몫으로 넘어온 값이 있는 경우 노드를 추가로 생성해..

Algorithm 기법 정리

공간 복잡도 O(1) 관련 Array Rotation Algorithm 참고 자료 https://www.geeksforgeeks.org/program-for-array-rotation-continued-reversal-algorithm/ 관련 문제 https://yinq.tistory.com/239 💡 핵심 IDEA 1. 회전 시, 밀려나는 부분과 밀려나지 않는 부분으로 2개의 블럭으로 나눈다. 2. 각 블럭을 역순으로 만든다. 3. 그리고 전체 블럭을 역순으로 만든다. Boyer-Moore 과반수 투표 알고리즘 참고 자료 https://sgc109.github.io/2020/11/30/boyer-moore-majority-vote-algorithm/ 관련 문제 https://yinq.tistory.co..

[Java] 141. Linked List Cycle

문제 파악 연결 리스트의 헤드가 주어진다. 그리고 이 연결 리스트가 사이클을 이루는지 결정해야한다. 풀이 1️⃣ Set 자료구조를 이용한 풀이 💡 떠오른 Idea 노드를 set 자료구조에 입력하고, 다음 노드로 진행하기 전에 진행할 노드가 set에 입력되어있는지 확인한다. 진행할 노드가 set에 입력되어있었다면, 사이클임을 알 수 있다. 위 아이디어를 바탕으로 코드를 작성하였다. public class Solution { public boolean hasCycle(ListNode head) { Set set = new HashSet(); ListNode now = head; set.add(now); while (now != null) { ListNode nextNode = now.next; if (set..

[Java] 3. Longest Substring Without Repeating Characters

문제 파악 문자열 s가 주어진다. 문자가 반복되지 않는 가장 긴 부분 문자열을 반환해야한다. 풀이 1️⃣ Queue 를 이용한 풀이 💡 떠오른 Idea 문자열을 순회하면서, Queue에 문자를 입력한다. 단, 입력하기 전, 입력하려는 문자가 Queue에 이미 존재한다면 그 문자를 제거하고 입력한다. 만약 pwwkew 문자열인 경우 첫 p는 큐에 없으므로 큐에 입력한다. Queue = [ p ] 두번째 w로 아직 큐에 없으므로 큐에 입력한다. Queue = [ p, w ] 세번째 w는 이미 큐에 존재하는 문자이므로 큐에 문자 w가 없어질때까지 pop 한다. 그리고 입력한다. Queue = [ w ] ... 이런식으로 진행되면서 중복되는 문자가 없는 부분 문자열이 큐에 갱신된다. class Solution ..

[Java] 209. Minimum Size Subarray Sum

문제 파악 정수 배열 nums 와 양수 target 이 주어진다 부분 집합의 합이 target 과 동일하거나 이상 값을 갖는 최소 길이를 반환해야한다. 없다면, 0을 반환한다. 풀이 1️⃣ 투 포인터 풀이 💡 떠오른 Idea 투포인터 방식으로 부분합을 구하다가, target과 동일하거나 그 이상 값이 되면 기록한다. 그리고, 왼쪽 포인터를 옮긴 뒤에 다시 탐색을 한다. class Solution { public int minSubArrayLen(int target, int[] nums) { int ans = Integer.MAX_VALUE; int left = 0, right = 0; int sum = 0; while (right = target 이 되는 부분 찾기 int find = target + f..

[Java] 167. Two Sum II - Input Array Is Sorted

문제 파악 비 내림차순으로 정렬되어 있는 정수 배열 numbers 가 주어진다. 배열에서 target 값을 만들 수 있는 값 2개를 찾아, 해당 값의 인덱스를 반환해야한다. ( index1 < index2 ) 풀이 1️⃣ 투 포인터 방식 💡 떠오른 Idea 인덱스 0 부터 시작하는 left 와 배열의 끝에서 시작하는 right 포인터를 정의한 뒤, 두 값의 합이 target 보다 크면 right 포인터를 감소시키고 target보다 작으면 left 를 증가시키는 방식으로 구현하면 될 것이라 판단했다. 왜냐하면, 비 내림차순으로 정렬되어 있고 정답이 무조건 존재하는 배열로 주어지기 때문에 가능하다고 판단했다. 그리고 시간복잡도도 O(N) 으로 해결할 수 있기 때문이다. class Solution { publ..

[Java] 125. Valid Palindrome

문제 파악 모든 대문자를 소문자로 변환 후, 숫자와 알파벳이 아닌 문자를 제거한 문자가 뒤로 읽었을때와 앞으로 읽었을때가 같으면 palindrome 이라고 한다. palindrome 이 맞으면 true를, 아니면 false를 반환하라 풀이 1️⃣ StringBuilder 사용 풀이 💡 떠오른 Idea 먼저, 공백과 문자 혹은 숫자가 아닌 것들을 제거해서 붙이는 작업이 필요하다. 그리고, 역순으로 나열한 문자와 동일한지 확인해서 palindrome 인지 확인하면 될 것이다. class Solution { public boolean isPalindrome(String s) { StringBuilder sb = new StringBuilder(); char[] arr = s.toLowerCase().toCha..

[Java] 55. Jump Game

문제 파악 정수 배열 nums 가 주어지고, 첫번째 인덱스에서 시작한다. 인덱스에 주어진 값은 최대로 점프할 수 있는 값이다. 마지막 인덱스에 도달할 수 있으면 true 를 없으면 false를 반환해야한다. 풀이 1️⃣ 내가 떠올린 아이디어는 다음과 같다. 현재 위치에서 가장 멀리 뛸 수 있는 인덱스를 확인한다. 만약 가장 멀리 뛸 수 있는 위치가 배열의 마지막 인덱스 ( nums.length - 1 ) 이상이라면 true 를 반환한다. 현재 위치에서 가장 멀리 뛸 수 있는 인덱스 까지 순회하면서, 다음으로 가장 멀리 갈 수 있는 인덱스를 찾고 이동한다. [2, 3, 1, 1, 4] 를 예시로 들자면, 현재 위치 0인 2에서 갈 수 있는 인덱스는 1과 2이고 인덱스 1은 (1 + 3) = 4번 인덱스 까..

[Java] 122. Best Time to Buy and Sell Stock 2

문제 파악 i날 주식 가격은 prices[i] 과 같이 배열 형태로 주어진다. 매일 주식을 살지 팔지 결정해야한다. 결과적으로 얻어지는 최대 수익을 반환해야한다. 풀이 1️⃣ 내림 차순으로 바뀌는 순간 수익 계산 풀이가 잘 떠오르지 않아서 몇 가지 예시를 들어봤다. Case 1. 1, 6, 7, 100 위 경우는 1에 사서 6에 팔고 7에 사서 100에 팔면, 1에 사서 100에 파는것보다 손해이다. 6~7 에 공백이 생기기 때문이다. Case 2. 1, 6, 5, 100 위 경우는 1에 사서 6에 팔고, 5에 사서 100에 팔면, 1에 사서 100에 파는 것보다 이득이다. 5~6 교집합 부분이 생겨 추가적인 이득이 될 수 있다. Case 3. 1, 6, 6, 100 위 경우는 1에 사서 6에 팔고 6에..

[Java] 121. Best Time to Buy and Sell Stock

문제 파악 i날 주식 가격은 prices[i] 과 같이 배열 형태로 주어진다. 최대로 수익을 반환해야한다. 만약, 어떠한 수익도 얻지 못한다면 0 을 반환한다. 풀이 1️⃣ 이중 for문 풀이 - 시간 초과 가장 먼저 떠오른 풀이는, 파는 날을 고정하고 파는 날 이전의 가격들을 순회하면서 최댓값을 구해야겠다고 생각했다. class Solution { public int maxProfit(int[] prices) { int ans = 0; for (int i = 1; i < prices.length; i++) { int sell = prices[i]; for (int j = 0; j < i; j++) { int buy = prices[j]; int profit = sell - buy; if (profit ..

[Java] 189. Rotate Array

문제 파악 정수 배열 nums 가 주어진다. 음수가 아닌 k 만큼 오른쪽으로 배열을 회전시켜야 한다. 풀이 1️⃣ 배열 2개를 이용한 풀이 먼저, 입력으로 주어진 k를 한번 전처리 해야한다. 왜냐하면, 길이가 N인 배열 nums를 N번 rotate 하면 원상태로 돌아오기 때문에 k를 N으로 나눈 나머지만큼만 rotate 한다고 볼 수 있기 때문이다. 그러면, 이동시킬 원소의 개수는 k%N 개가 된다. 이동 시킬 부분을 tmp라는 배열을 정의해서 내용을 복사해둔다. 그리고 뒤에서부터 이동시킨다. 그리고 보관해두었던 내용을 앞에 붙여주면 된다. class Solution { public void rotate(int[] nums, int k) { int N = nums.length; k = k % N; int..

[Java] 169. Majority Element

문제 파악 크기가 n인 배열 nums 가 주어진다. n/2 보다 많이 등장하는 수를 반환해야한다. 풀이 1️⃣ 해시 활용 바로 간단하게 떠오른 풀이이다. 먼저, 배열을 순회하면서 원소를 key 값으로 원소가 나타난 횟수를 value 값으로 map에 기록한 뒤, map을 한번 더 순회하면서, 나타난 횟수가 n/2 보다 큰 경우 반환하는 방식이다. import java.util.*; class Solution { public int majorityElement(int[] nums) { int n = nums.length; int result = nums[0]; HashMap map = new HashMap(); for (int num : nums) { map.put(num, map.getOrDefault(n..

[Java] 80. Remove Duplicates from Sorted Array II

문제 파악 nums 는 비내림차순 정수 배열이며, 최대 2개까지 중복될 수 있도록 나머지 중복은 제거해야한다. 그리고, 상대적인 위치를 유지해야한다. 주어진 조건에 맞게 중복을 제거한 원소의 개수 k를 반환해야한다. nums 배열 외 다른 배열을 사용하면 안된다. 풀이 1️⃣ 포인터 방식 nums 배열만 사용해야하기 때문에, nums 배열의 원소들을 갱신해나가며 중복을 최대 2개까지 허용하면서 중복을 제거해야겠다고 생각했다. 먼저, 갱신할 수 있는 조건이 뭔지 생각해봤다. 원소가 달라지는 순간 갱신하고 포인터를 이동 원소가 같은 경우 중복된 원소가 2개까지는 허용되므로, 2개까지는 갱신하고 포인터를 이동 단, 3개부터는 갱신하지 않고 원소가 달라지는 순간까지 포인터를 움직일 수 없음 위 조건을 먼저 생각..

[Java] 26. Remove Duplicates from Sorted Array

문제 파악 nums는 비내림차순 배열이다. 중복되는 원소들을 1개의 원소들로 바꾸고, 상대적인 위치는 유지해야한다. 즉, [1, 1, 2, 2, 3] 인 경우, [1, 2, 3, _, _ ] 으로 만들어야 한다는 것이다. 그리고, 중복을 제거한 수의 개수 k를 반환해야한다. 풀이 1️⃣ 포인터 방식 먼저, unique 한 원소를 갱신하기 위한 포인터가 필요하다는 생각을 했다. 그리고, 배열 nums 를 순회하면서 값이 달라지는 인덱스를 먼저 추출해봐야겠다고 생각했다. for(int i=1; i

[Java] 27. Remove Element

문제 파악 정수 배열 nums와 val이 주어진다. 배열 nums 에서 val과 일치하는 원소를 모두 제거해야한다. 그리고 nums 배열에서 val과 일치하지 않는 원소의 개수를 반환해야한다. 일치하지 않는 원소의 개수가 k 일 때, nums의 k번 인덱스 까지는 val과 일치하지 않는 원소들로 채워넣어야 한다. 풀이 1️⃣ Arrays.sort() 사용 먼저, 문제 조건을 보니 nums 배열의 원소 최댓값은 50임을 알 수 있었다. 따라서, nums 배열에서 val과 일치하는 원소를 51로 모두 변환해두고 정렬을 수행하면, 배열의 뒷부분으로 밀려나 있을 것으로 예상했다. import java.util.*; class Solution { public int removeElement(int[] nums, ..