티스토리

공부 기록

검색하기

블로그 홈

공부 기록

sysgongbu.tistory.com/m

소연쏘 님의 블로그입니다.

구독자: 15

방명록 방문하기

주요 글 목록

leetcode: Group Anagrams 그룹화 하기 위해 sorted된 string을 key로 해서 map에 넣도록 했다. import java.util.*; import java.util.stream.Collectors; import java.util.stream.Stream; class Solution { public List groupAnagrams(String[] strs) { List answer = new ArrayList(); HashMap map = new HashMap(); for (String str : strs) { String key = Stream.of(str.split("")).sorted().collect(Collectors.joining()); if (!map.containsKey(key)) { map.put(ke.. 공감수 0 댓글수 0 2021. 2. 14.
leetcode: Decode String 문제 조건 k[encoded_string] => encoded_string을 k번 반복 3a 또는 2[4] 등의 경우는 없다고 생각한다 먼저, 괄호 중 ']' 을 만나는 순간, 뒤에서부터 가장 먼저 만나게 되는 '[' 의 위치를 찾아 그 부분을 반복하는 문제이다. => 뒤에서 부터 꺼내는 것이니까 스택을 사용하자 예를 들어 예시2와 같이 `3[a2[c]]` 가 주어졌다고 해 보자 아래와 같이 일단 닫는 괄호를 만나기 전까지는 스택에 push를 한다. 그 다음 여는 괄호를 만나기 전까지 pop을 하며 stringbuilder에 더해주고, 여는 괄호까지 pop한 뒤에 top이 숫자가 될 수 있는지 확인한다. 숫자이면 pop해주고, stringbuilder를 그 숫자만큼 반복해준다. 결과를 스택에 다시 넣어주.. 공감수 0 댓글수 0 2021. 2. 14.
leetcode: Task Scheduler 문제 조건 cpu에 태스크가 들어올건데 태스크의 순서는 맘대로 실행할 수 있다. 각 태스크는 한 시간 단위로 수행되고, 태스크를 실행하거나 idle 상태에 있을 수 있다. 두 개의 동일한 태스크를 실행하기 위한 사이에는 최소 n개의 태스크/idle이 있어야 한다. 흠... 일단은 그냥 가장 자주 나오는 글자를 배치하고 그 사이에 n개의 빈 칸을 둔 뒤에 다른 애들을 적절히 배치하면 될 것 같다고 생각했다. class Solution { public int leastInterval(char[] tasks, int n) { int[] frequency = new int[26]; for (int task : tasks) { frequency[task - 'A']++; } Arrays.sort(frequency.. 공감수 0 댓글수 0 2021. 2. 7.
leetcode: Sliding Window Maximum 처음에는 단순하게 maxHeap을 이용해서 O(N)만에 풀면 되지 않을까 생각했다. 윈도우를 maxHeap에 넣고 움직이면서 맨 앞의 값은 빼고, 뒤에 새로 들어오는 값은 더해주는 방식으로 구현했다. import java.util.*; class Solution { public int[] maxSlidingWindow(int[] nums, int k) { int length = nums.length; int answer[] = new int[length - k + 1]; PriorityQueue maxHeap = new PriorityQueue(Collections.reverseOrder()); for (int i = 0; i < k; i++) { maxHeap.add(nums[i]); } answer[.. 공감수 0 댓글수 0 2021. 2. 7.
leetcode: Longest Increasing Subsequence 2021/01/15 - [알고리즘 공부/boj] - boj 3745: 오름세 boj 3745: 오름세 이 문제에서 주의해야할 점은 아래 2가지이다. EOF 처리 최장부분증가수열을 빠르게 구하기 완전탐색 => O(2^N) 1차 시도 - `동적 계획법`을 사용하여 문제를 풀어보았다. 결과는 50%에서 시간초과. => sysgongbu.tistory.com 위 문제와 동일하다. 지난번에 푼 기억이 있어서 비교적 수월하게 풀었다. 세그먼트 트리로도 한번 구현해 봐야하는데 언제하지... class Solution { public int lengthOfLIS(int[] nums) { int n = nums.length; int[] lis = new int[n]; lis[0] = nums[0]; int lastInd.. 공감수 0 댓글수 0 2021. 2. 7.
leetcode: Jump Game II 문제 조건 num 배열 원소는 음이 아닌 정수 배열의 마지막 요소까지 점프해서 무조건 도달 가능 => 0이 아닌 이상 1칸씩 가면 되니까 배열의 각 요소는 해당 위치에서 최대 점프 길이를 나타낸다. class Solution { public int jump(int[] nums) { int n = nums.length; if (n < 2) { return 0; } int maxPosition = nums[0]; int maxLength = nums[0]; int jumps = 1; for (int i = 1; i < n; ++i) { if (maxLength < i) { jumps++; maxLength = maxPosition; } maxPosition = Math.max(maxPosition, nums.. 공감수 0 댓글수 0 2021. 1. 31.
leetcode: Longest Increasing Path in a Matrix 먼저, 브루트포스로 모든 점에 대해 DFS를 돌려 가장 긴 path를 찾는 방법이 있을 것이다. 하지만 이 방법의 경우 시간초과가 발생한다. class Solution { public static int[] dr = { 1, -1, 0, 0 }; public static int[] dc = { 0, 0, 1, -1 }; public int longestIncreasingPath(int[][] matrix) { if (matrix.length == 0) { return 0; } int maxRow = matrix.length; int maxCol = matrix[0].length; int answer = 0; for (int i = 0; i < maxRow; ++i) for (int j = 0; j < m.. 공감수 0 댓글수 0 2021. 1. 31.
leetcode: Target Sum nums 배열에 있는 값을 적절히 더하고 빼서 target과 같은 값을 만들 수 있는 방법의 수를 구하는 문제이다. 일단 문제를 풀 수 있는 방법으로 가장 먼저 떠오른 것은 브루트 포스,,, 시간복잡도는 O(2^N)이다. class Solution { public int answer = 0; public int findTargetSumWays(int[] nums, int S) { findAll(nums, 0, 0, S); return answer; } public void findAll(int[] nums, int index, int sum, int target) { if (index >= nums.length) { if (sum == target) { answer++; } return; } findAl.. 공감수 1 댓글수 0 2021. 1. 27.
leetcode: Couples Holding Hands 커플 (2N-2, 2N-1)가 인접해서 앉고 싶은데, 그렇지 못하다면 최소로 swap하여 인접하게 앉을 수 있도록 하는 문제이다. 커플은 (2N-2, 2N-1)으로 (0,1), (2,3), (4,5), ...이므로 x의 파트너는 x가 짝수인 경우 x+1, 홀수인 경우 x-1이다. 먼저 array를 0부터 2자리씩 보기 시작하면서 해당 파트너와 인접하면 넘어가고, 인접하지 않으면 짝은 옆으로 데려와서 앉힌다. 즉, 소파에 첫번째 앉아있는 사람은 고정시키고 두번째 사람만 옮김으로써 커플을 완성하도록 한다. 시간복잡도는 O(N^2)이고 코드는 아래와 같다. class Solution { public int minSwapsCouples(int[] row) { int ans = 0; for (int i = 0; .. 공감수 1 댓글수 0 2021. 1. 24.
leetcode: Binary Tree Maximum Path Sum 이 문제는 트리를 어떤 방식으로든 순회했을 때, 그 합의 최대를 구하는 문제이다. 예를 들어 위 예제의 경우 최적의 순회 방법중 하나는 15 -> 20 -> 7 이고 그 합은 15 + 20 + 7 = 42이다. 먼저 저번에 공부했던 tree dp처럼 어떤 노드를 기준으로 해당 서브 트리의 최대값을 구할 수 있도록 하자고 생각했다. 즉, 리프 노드의 경우는 해당 노드에 적혀있는 수를 리턴하고, 그 이외는 아래에서부터 올라오면서 최대 값을 해당 노드에 저장하는 식이다. 이러한 경우 시간복잡도는 O(N)으로 볼 수 있으며 풀이는 아래와 같다. class Solution { int answer = Integer.MIN_VALUE; public int findMaxNode(TreeNode node) { if (n.. 공감수 0 댓글수 0 2021. 1. 24.
leetcode: Maximum Frequency Stack FreqStack has two functions: push(int x), which pushes an integer x onto the stack. pop(), which removes and returns the most frequent element in the stack. If there is a tie for most frequent element, the element closest to the top of the stack is removed and returned. 두가지 자료구조를 사용한다. frequency: (key, value) -> 값 key에 대한 빈도수 value를 저장한 자료구조 frequencyValueStack: (key, stack) -> 빈도수 key에 대해 값 sta.. 공감수 0 댓글수 0 2021. 1. 23.
leetcode: Range Sum Query - Mutable 세그먼트 트리란? 주어진 쿼리에 대해 빠르게 응답하기 위해 만들어진 자료구조로, 주로 구간 합을 다룰 때 많이 사용한다. 대부분 완전 이진 트리로 구성된다. 세그먼트 트리에서는 수를 바꾸는 과정 :: O(lgN) 수를 더하는 과정 :: O(lgN)으로 변하게 된다. M번 실행한다 치면 O(MlgN + MlgN) -> O(MlgN)이 걸리게 된다. class NumArray { int[] tree; int n; public NumArray(int[] nums) { if (nums.length > 0) { n = nums.length; tree = new int[n * 2]; buildTree(nums); } } private void buildTree(int[] nums) { for (int i = n, .. 공감수 0 댓글수 0 2021. 1. 10.
leetcode: 01 Matrix 방법1 - 각 cell에서 1인 부분을 큐에 넣고 bfs를 통해 0까지의 최소 거리를 찾는다. import java.util.*; class Solution { public static int dr[] = { 0, 0, 1, -1 }; public static int dc[] = { 1, -1, 0, 0 }; public int[][] updateMatrix(int[][] matrix) { Queue queue = new LinkedList(); for (int i = 0; i < matrix.length; i++) { for (int j = 0; j < matrix[i].length; j++) { if (matrix[i][j] != 0) { queue.add(new Position(i, j, 0)); .. 공감수 0 댓글수 0 2021. 1. 8.
leetcode: Number of Islands 전형적인 bfs문제이다. 시간복잡도는 O(grid 요소의 갯수)와 같다. import java.util.*; class Solution { public static int dr[] = { 0, 1, 0, -1 }; public static int dc[] = { 1, 0, -1, 0 }; public int numIslands(char[][] grid) { int answer = 0; for (int i = 0; i < grid.length; i++) { for (int j = 0; j < grid[i].length; j++) { if (grid[i][j] == '1') { answer++; grid[i][j] = '0'; bfs(i, j, grid); } } } return answer; } publi.. 공감수 0 댓글수 0 2021. 1. 7.
leetcode: Trapping Rain Water 브루트포스 방법으로 양 옆을 다 보는 방법의 경우 시간복잡도 O(N^2)이 걸릴 것이다. 이 문제의 경우 아래와 같이 왼쪽에 있는 높이 중에서 가장 높은 높이만 보고 있는 상태이므로 => 스택을 사용한다면 O(N)만에 문제를 풀 수 있다. 문제풀이 로직은 아래와 같다. 1. index를 오른쪽으로 움직이면서 스택의 맨 위에 담은 높이와 비교했을때 height[index]이 크거나 같으면 스택에 담는다. 2. 높이가 바뀌면 이전까지 물을 계산해서 answer에 더해주며, 이전 높이는 pop 시켜준다. import java.util.*; class Solution { public int trap(int[] height) { int answer = 0; Stack stack = new Stack(); int .. 공감수 0 댓글수 0 2020. 12. 27.
leetcode: Median of two sorted Arrays class Solution { public double findMedianSortedArrays(int[] nums1, int[] nums2) { int nums1Length = nums1.length; int nums2Length = nums2.length; int size = nums1Length + nums2Length; int nums1Index = 0; int nums2Index = 0; int mergedArray[] = new int[size]; int index = 0; while (true) { if (nums1Index >= nums1Length && nums2Index >= nums2Length) { break; } else if (nums1Index >= nums1Length) { .. 공감수 0 댓글수 0 2020. 12. 26.
leetcode: Letter Combinations of a Phone number class Solution { public List letterCombinations(String digits) { List answer = new ArrayList(); Map numberToString = new HashMap() { { put(2, "abc"); put(3, "def"); put(4, "ghi"); put(5, "jkl"); put(6, "mno"); put(7, "pqrs"); put(8, "tuv"); put(9, "wxyz"); } }; for (char ch : digits.toCharArray()) { int number = ch - '0'; answer = addCharacter(numberToString.get(number), answer); } return answer.. 공감수 0 댓글수 0 2020. 12. 26.
leetcode: Palindrome Partitioning 어차피 모든 경우의 수를 구하긴 해야한다. 하지만, 팰린드롬임을 한번 체크했다면 계속 그 글자가 팰린드롬인지 체크를 하지 않도록 어딘가 저장하는 방법은 없을지? => DP 팰린드롬 s의 서브스트링 s.substring(1, n-1) 또한 팰린드롬임을 이용하자. => DP[indexStart][indexEnd]: s.substring(indexStart, indexEnd)의 팰린드롬 여부 맨 첫 글자와 끝 글자가 같은 경우 중에서 팰린드롬이 될 수 있는 경우 1. 맨첫글자 위치 == 끝글자 위치 ex) "a" 2. 두 글자가 연속인 경우 ex) "aa" 3. 중간에 한 글자가 껴있는 경우 ex) "aba" 4. s.substring(첫 글자의 다음 글자, 끝 글자의 이전 글자)가 팰린드롬인 경우 impor.. 공감수 0 댓글수 0 2020. 12. 26.
leetcode: Contain With Most Water class Solution { public static int maxArea(int[] height) { int left = 0; int right = height.length - 1; int max = calcArea(left, right, height); while (left != right) { if (height[left] < height[right]) { left++; } else { right--; } max = Math.max(max, calcArea(left, right, height)); } return max; } public static int calcArea(int left, int right, int[] height) { return (right - left) * Math.min(.. 공감수 0 댓글수 0 2020. 12. 17.
leetcode: 4sum 문제 조건 배열이 중복되면 안됨 -> 그럼 hashset을 쓸까? list 내의 원소들이 순서를 바꾸어도 같은 객체로 인식해야하기 때문에 정렬을 해서 넣어주도록 했다. import java.util.*; import java.util.stream.Collectors; public class Solution { public static List fourSum(int[] nums, int target) { int length = nums.length; HashSet answer = new HashSet(); for (int i = 0; i < length; i++) { for (int j = i + 1; j < length; j++) { if (i == j) { continue; } for (int k = .. 공감수 1 댓글수 0 2020. 12. 17.

문의안내

티스토리
로그인
고객센터

티스토리는 카카오에서 사랑을 담아 만듭니다.