https://leetcode.com/problems/best-time-to-buy-and-sell-stock/description/?envType=study-plan-v2&envId=top-interview-150 문제 정수배열 price[] 가 주어질 때, price[i] 은 i 날에 물건의 값이다. 이 때 물건을 사는 날과 파는 날을 정해 가장 높은 이익을 구하는 문제이다. 이익을 낼 수 없을 때는 0을 반환해야 한다. 풀이 최소 가격을 의미하는 변수만 가지고 있으면 쉽게 풀 수 있다고 생각하였다. 따라서 최대 이익을 의미하는 max 변수의 초기값을 0으로 놓고, 최소 가격을 의미하는 minNum 을 계속 업데이트 해주며 max 값을 구한다. class Solution { public int max..
https://leetcode.com/problems/rotate-array/description/?envType=study-plan-v2&envId=top-interview-150 문제 정수 배열 nums 가 주어질 때 k 번 만큼 오른쪽으로 이동한 결과값을 출력하는 문제이다. 풀이 처음에는 새로운 배열을 만들고 정렬을 하여 풀었으나 in-place 방식만 허용을 하는 것 같다. 따라서 reverse 전략이 필요하다. 전체 배열의 길이만큼 reverse 하고 배열을 k 길이만큼 나누어 따로 reverse 하여 다시 정렬을 한다. class Solution { public void rotate(int[] nums, int k) { k %= nums.length; int n = nums.length; r..
https://leetcode.com/problems/majority-element/description/?envType=study-plan-v2&envId=top-interview-150 문제 정수 배열 nums 와 정수 배열의 길이 n 이 주어졌을 때, 배열에서 가장 많은 요소를 출력하는 문제이다. 풀이 문제 조건에 가장 많은 요소는 항상 n/2 보다 크다고 했으므로 다음과 같은 풀이가 가능하다. class Solution { public int majorityElement(int[] nums) { int count = 0; int element = 0; for (int num : nums) { if (count == 0) { element = num; } if (num == element) { co..
https://leetcode.com/problems/remove-duplicates-from-sorted-array-ii/description/?envType=study-plan-v2&envId=top-interview-150 문제 [Remove Duplicates from Sorted Array] 문제와 거의 같지만 중복으로 올 수 있는 숫자의 개수가 2개까지 가능하다. 풀이 문제에서는 in-place 방식으로 해결을 원하지만 아쉽게도 나는 자료구조를 하나 더 선언하여 해결하였다. 또 다른 정수 배열을 선언하고 카운팅 정렬을 이용해 풀었다. 음수의 경우도 생각해야 하기 때문에 문제에서 주어진 정수의 범위 3000에 추가로 3000을 더하여 전체 카운팅 정수 배열 길이를 6000으로 정하였다. clas..
https://leetcode.com/problems/remove-duplicates-from-sorted-array/?envType=study-plan-v2&envId=top-interview-150 문제 오름차순 정수 배열 nums 가 주어졌을 때 같은 숫자가 한 번만 오게끔 중복을 제거하는 문제이다. 문제 조건으로는 in-place 알고리즘을 사용하고 반환값으로 중복을 제거한 정수 배열 길이를 출력하라고 요구하고 있다. 풀이 class Solution { public int removeDuplicates(int[] nums) { int index = 1; for (int i = 0; i < nums.length - 1; i++) { if (nums[i] != nums[i + 1]) { nums[in..
https://leetcode.com/problems/remove-element/?envType=study-plan-v2&envId=top-interview-150 문제 정수 배열 nums 와 정수 val 이 주어졌을 때, nums 배열에서 val 을 제거 하고 제거한 배열의 길이를 출력하는 문제이다. 단, 문제에서 in-place 방식으로 풀 것을 요구하고 있다. in-place 방식은 새로운 자료구조를 추가하지 않고 주어진 자료구조에서 문제를 해결하는 방식을 말한다. 풀이 class Solution { public int removeElement(int[] nums, int val) { int index = 0; for (int i = 0; i < nums.length; i++) { if (nums[..
https://leetcode.com/problems/merge-sorted-array/?envType=study-plan-v2&envId=top-interview-150 문제 두 개의 정수 배열 num1 과 num2 가 오름차순으로 정렬되어 주어지고 각 배열의 요소의 개수를 나타내는 m, n 이 주어질 때 num1 과 num2 를 오름차순으로 정렬된 하나의 배열로 병합하는 문제이다. 문제의 조건으로는 최종 결과값은 함수에서 반환되지 않고, 배열 num1 내부에 저장되어야 한다. 풀이 class Solution { public void merge(int[] nums1, int m, int[] nums2, int n) { for (int i = 0; i < n; i++) { nums1[m + i] = nu..