본문 바로가기

LeetCode/Array

 (9)
[Medium] 973. K Closest Points to Origin (Facebook / Meta) #문제 설명 Leetcode 973번 문제는 x, y축 위의 좌표들이 배열로 주어지고, 정수 k가 주어진다. 이 문제에서는 (0,0) 에 가장 가까운 좌표 k개를 포함한 array를 return하는 문제이다. #문제 풀이 #풀이 1 class Solution{ public int[][] kClosest(int[][] points, int K) { Arrays.sort(points, (p1, p2) -> p1[0] * p1[0] + p1[1] * p1[1] - p2[0] * p2[0] - p2[1] * p2[1]); return Arrays.copyOfRange(points, 0, K); } } 모든 점을 원점까지의 거리에 따라 정렬한 다음 가장 가까운 상위 k개의 점을 얻는 풀이 이다. Time comp..
[Easy] 217. Contains Duplicate #문제 설명 Leetcode 217번 문제는 주어진 정수 배열에 중복된 숫자가 들어있는지 알아내는 문제이다. 배열에서 중복이 발생되면 true, 중복이 없다면 false를 return 하면 된다. #문제 풀이 1. HashSet이용 풀이 Set에는 중복 데이터를 담을 수 없다는 특성이 있다. 이 특성을 활용하면 문제를 쉽게 풀수있다. class Solution { public boolean containsDuplicate(int[] nums) { Set set = new HashSet(); for(int i = 0; i < nums.length;i++){ if(!set.add(nums[i])){ return true; } } return false; } } 먼저 HashSet를 만들고 array의 각 정..
[Medium] 238. Product of Array Except Self (애플 코딩 테스트 문제) Leetcode 238번 문제는 정수로 채워진 array가 주어지고, 원래의 index에있는 값을 제외한 모든 index의 값을 곱한 값이 들어있는 array를 return하는 문제이다. class Solution { public int[] productExceptSelf(int[] nums) { int product = 1; for(int i = 0; i < nums.length;i++){ product *= nums[i]; } int[] arr = new int[nums.length]; for(int i = 0; i < nums.length;i++){ if(nums[i] == 0){ arr[i] = product; } else{ arr[i] = product / nums[i]; } } return a..
[Medium] 39. Combination Sum #Backtracking 풀이 class Solution{ public List combinationSum(int[] nums, int target) { List list = new ArrayList(); backtrack(list, new ArrayList(), nums, target, 0); return list; } private void backtrack(List list, List tempList, int [] nums, int remain, int start){ if(remain < 0) return; else if(remain == 0) list.add(new ArrayList(tempList)); else{ for(int i = start; i < nums.length; i++){ temp..
[Medium] 53. Maximum Subarray Leetcode 53번 문제는 주어진 array에서 주어진 값을 더했을때 가장 합이 큰 subarray를 찾는 문제이다. #Brute Force 풀이 class Solution { public int maxSubArray(int[] nums) { int max = nums[0]; for(int i=0; i
[Easy] 35. Search Insert Position Leetcode 35번 문제는 주어진 정렬된 array에서 target을 찾는 문제이다. 만약 target이 array안에 없다면, insertion point를 찾는 문제이다. Searching algorithm의 time complexity는 O(log n) 이어야 한다. Time complextiy와 array가 sorted 돼있다는 점을 고려하면 Binary Search Algoritm를 써서 풀수 있다. #풀이 public int searchInsert(int[] A, int target) { int low = 0, high = A.length-1; while(low target) high = mid-1; else low = mid+1; } return low; } Binary Search후에 ..
[Easy]1672. Richest Customer Wealth Leetcode 1672번 문제는 integer array를 담고 있는 array가 주어진다. 각 array를 더했을 때 가장 값이 큰 값을 return 하면 된다. 간단한 nested for-loop의로 풀 수 있다. class Solution { public int maximumWealth(int[][] accounts) { int res = 0; for(int i =0;i
[Easy] 1. Two Sum Example 1: Input: nums = [2,7,11,15], target = 9 Output: [0,1] Explanation: Because nums[0] + nums[1] == 9, we return [0, 1]. Example 2: Input: nums = [3,2,4], target = 6 Output: [1,2] Example 3: Input: nums = [3,3], target = 6 Output: [0,1] Leetcode 1번 문제 Two Sum에서는 하나의 배열과 하나의 target value 가 주어지며, 배열에서 두 개의 값을 더했을때 target value와 같아지는 index를 가지고있는 배열을 반환하는 문제이다. #Brute force 방식 O(n^2) class Sol..

티스토리툴바