👨🏻‍💻 PS/LeetCode 150

[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, ..

[Java] 88. Merge Sorted Array

문제 파악 두 정수 배열 nums1 과 nums2 는 비내림차순(non-decreasing) 배열이다. 비내림차순 : 같은 크기의 원소가 존재할 수 있는 것 ex) 1 2 3 ex) 1 1 2 nums1 배열의 길이는 m+n 으로, 첫 m번째까지의 원소는 merged 되어야 하고 나머지 n개는 0으로 설정되어 있다. 그리고 그 n개의 0 에 nums2의 원소들이 들어가야하고 최종 결과는 비내림차순으로 반환하면 된다. 풀이 1️⃣ Array.sort() 가장 간단하게 떠오른 풀이이다. 먼저 nums1 배열의 0 부분에 nums2 배열의 원소를 입력한 후, Arrays.sort() 를 사용하는 것이다. 입력하는 방법은 간단하다. nums1의 m+1 번째 부터 m+n번째 까지 0으로 입력되어 있으므로 for(..