알고리즘/배열
-
[알고리즘] Two Sum알고리즘/배열 2021. 4. 20. 11:07
Problem Key Point target - nums[i]를 Key로 loop의 index를 Value로 Map에 저장한다. 해당 Key값을 만족하는 nums[i] 요소를 찾으면 결과를 리턴한다. Code public class TwoSum { public void solution(int[] nums, int target) { // 01. ds 담을 그릇 int[] result = new int[2]; Map map = new HashMap(); // 02. for for (int i = 0; i < nums.length; i++) { if (map.containsKey(nums[i])) { result[0] = map.get(nums[i]) + 1; result[1] = i + 1; } else {..
-
[알고리즘] Daily temperatures (O)알고리즘/배열 2021. 4. 20. 11:01
Problem Key Point 온도가 높은 index가 나올 때까지 stack에 쌓아놓다가 조건을 만족할 때 stack에서 뽑아서 계산한다. Code public class DailyTemperature { public void solve(int[] nums) { Stack stack = new Stack(); int[] result = new int[nums.length]; for (int i = 0; i < nums.length; i++) { while (!stack.isEmpty() && nums[stack.peek()] < nums[i]) { int index = stack.pop(); result[index] = i - index; } stack.push(i); } System.out.prin..
-
[알고리즘] Merge Intervals (O)알고리즘/배열 2021. 4. 20. 10:50
Problem Key Point 종료 시간보다 큰 시작 시간이 나올 때 까지 before에 시간을 머지한다. Code public class MergeInterval { public List solution(List intervals) { if(intervals.isEmpty()) return intervals; List result = new ArrayList(); Collections.sort(intervals, (o1, o2) -> o1.getStart() - o2.getStart()); // print(intervals); Interval before = intervals.get(0); for (int i = 1; i < intervals.size(); i++) { Interval current ..
-
[알고리즘] Meeting Rooms II알고리즘/배열 2021. 4. 20. 10:34
Problem Key Point Priority Queue 일반적인 큐는 먼저 들어간 데이터가 먼저 나오는 구조이다. 우선순위 큐는 들어간 순서에 상관없이 일정한 규칙에 따라 우선 순위를 선정하고 우선 순위가 가장 높은 데이터가 먼저 나오게 된다. Java는 기본적으로 오름차순이고 내림차순으로 정렬이 필요한 경우 Comparator 클래스나 Comparable 인터페이스를 이용한다. // 종료 시간을 기준으로 오름차순 Queue priorityQueue = new PriorityQueue((o1, o2) -> o1.getEnd() - o2.getEnd())); Code public class MeetingRoom2 { public int solution(Interval[] intervals) { if(i..
-
[알고리즘] Jewels And Stones알고리즘/배열 2021. 4. 20. 10:21
Problem Key Point Set 컬렉션 요소의 저장 순서를 유지하지 않는다. 같은 요소의 중복 저장을 허용하지 않는다. Set charSet = new HashSet(); Code public class JewelsAndStones { public int solution(String jewels, String stones) { int count = 0; Set jset = new HashSet(); for (char jewel : jewels.toCharArray()) { jset.add(jewel); } for (char stone : stones.toCharArray()) { if (jset.contains(stone)) { count++; } } return count; } public st..
-
[알고리즘] License Key Formatting알고리즘/배열 2021. 4. 19. 14:50
Problem Key Point StringBuilder의 insert() StringBuilder sb = new StringBuilder(); sb.insert(length - i, "-"); StringBuilder.insert(int offset, String str) offset위치에 str 문자열을 집어넣는다. length - i는 뒤에서 i 번째 offset을 의미한다. Code public String solution(String str, int k) { str = str.replaceAll("-", ""); str = str.toUpperCase(); int length = str.length(); StringBuilder sb = new StringBuilder(); for (int i..
-
[알고리즘] K Closest Points to Origin알고리즘/배열 2021. 4. 19. 14:42
Problem Key Point Priority Queue (min heap) Queue priorityQueue = new PriorityQueue((a,b) -> (a[0]*a[0]+a[1]*a[1])-(b[0]*b[0]+b[1]*b[1])); Code public class KClosest { public int[][] solution(int[][] points, int k) { int[][] result = new int[k][2]; Queue pq = new PriorityQueue((a,b) -> (a[0]*a[0]+a[1]*a[1])-(b[0]*b[0]+b[1]*b[1])); for (int[] p : points) { pq.offer(p); } System.out.println(pq); i..
-
[알고리즘] Plus One알고리즘/배열 2021. 4. 19. 14:26
Problem Key Point 인덱스가 0보다 크거나 carry가 있을 때까지 루프를 돌린다. (number + 1) % 10이 0인 경우 carry가 있는 것으로 판단한다. 전체 요소들을 다 돌고 나서 carray가 있는 경우 배열의 크기+1의 새로운 배열을 만들고 리턴한다. Code public class PlusOne { public int[] solution(int[] digits) { int carry = 1; int index = digits.length - 1; while (index >= 0 && carry > 0) { digits[index] = (digits[index] + 1) % 10; if (digits[index] == 0) { carry = 1; } else { carry =..