Leetcode 100문제 도전 (32) 썸네일형 리스트형 [Leetcode 16/100] Online Stock Span - Medium 문제 풀이 방식 Deque을 사용했지만 스택 자료구조의 성질을 활용해서 풀이했다. 주의할 점 선형시간에 문제를 풀어야 하므로 처음부터 시간 복잡도를 생각하고 풀이를 접근해야 한다. 그리고 문제를 이해했다면 그림을 그려서 풀이를 생각해보는 것도 좋은것 같다. 아이디어를 생각해내면 구현은 쉬운 문제였지만, 아이디어를 생각하기는 쉽지 않았다. 소스코드 [Leetcode 15/100] Course Schedule - Medium 문제 풀이 방식 Graph에서 Cycle을 찾는 재귀 함수 구현 주의할 점 처음에 findCycle() 함수 설계를 잘못했는데 너무 오래 매달렸다. 초기 설계를 잘하고 아니다 싶으면 바로 포기한 후에 새로운 방식으로 구현하는 것도 하나의 방법일 것 같다. 또한, 그래프에서 Cycle을 찾는 구현 방법을 정확하게 숙지하는 것이 필요할 것 같다. 위상정렬로도 풀 수 있는 문제인데 학습하자 소스코드 class Solution { boolean[] visitied; List graph = new LinkedList(); public boolean canFinish(int numCourses, int[][] prerequisites) { visitied = new boolean[numCourses]; getGra.. [Leetcode 14/100] Find the Town Judge - Easy 문제 풀이 방식 LinkedList로 Graph를 구현하여 풀이 주의할 점 엣지 케이스를 주의 할 것, 시간 복잡도를 신경 쓸 것 그래프 문제를 많이 경험해보지 못해서 순수 구현으로 푼 느낌이다. 다른 discuss를 보고 풀이를 참고해서 다시 풀어봐야 할 것 같음.. 소스코드 class Solution { LinkedList res = new LinkedList(); int sizeFlag = 0; public int findJudge(int N, int[][] trust) { if(N == 1) return 1; makeGraph(N, trust); LinkedList judgeList = findByJundgeList(); if(sizeFlag > 1) return -1; return findByJ.. [Leetcode 13/100] Minimum Absolute Difference in BST - Easy 문제 풀이 방식 BST의 정렬된 특성 + inorder 재귀 구현 이용 inorder은 left -> selft -> right로 트리를 방문하므로 inorder로 트리를 순회했을 때, 순차적으로 방문할 수 있다. 주의할 점 트리 순회방식인 preorder, inorder, postorder를 이해하자 preorder : slef -> left -> right로 루트가 가장 먼저 나온다 inorder : left -> selft -> right 가장 왼쪽 노드가 먼저 나온다. (BST일 경우 정렬된 결과 볼 수 있음) postorder : left -> right -> root 루트가 가장 늦게 나온다. 소스코드 /** * Definition for a binary tree node. * public c.. [Leetcode 12/100] Maximum Subarray - Easy 문제 풀이 방식 kadane's algorithm을 활용한 풀이 구간의 최대 합을 구하기 위해 사용할 수 있는 알고리즘으로 주요 수식은 아래와 같다. S[i] = Math.max(arr[i], arr[i] + S[i-1]) S 배열은 이 구간까지의 최대 합으로 만약 최대 합보다 현재 인덱스 배열의 값이 크다면 초기화를 시켜주는 방식이다. 주의할 점 브루트 포스 방식으로 모든 배열을 탐색하게 될 경우 O(n^2)의 시간복잡도를 가진다. 그러나 시간을 그만큼 주지 않는 경우가 대부분이므로 O(n)으로 풀어야 success를 받을 수 있다. 소스코드 class Solution { public int maxSubArray(int[] nums) { if(nums.length == 0) return 0; int s.. [Leetcode 11/100] First Bad Version - Easy leetcode.com/problems/first-bad-version/ First Bad Version - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 문제 풀이 방식 Binary Search 활용, 이 문제에서는 isBadVersion이라는 API를 제공해주므로 활용해서 풀면 된다. 주의할 점 완전 탐색으로 LInear 시간 만큼 탐색하게 되면 TLE를 볼 수 있다. 소스코드 /* The isBadVersion API is defined in the par.. [Leetcode 10/100] Find the Smallest Divisor Given a Threshold - Medium leetcode.com/problems/find-the-smallest-divisor-given-a-threshold/ Find the Smallest Divisor Given a Threshold - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 문제 풀이 방식 이진 탐색을 활용한 구현 주의할 점 문제를 정확하게 이해하는 것이 가장 중요하다고 느꼈다. -> 문제를 한번에 이해하지 못해서 많은 시간이 소모 됨. 완전 탐색으로 시도할 경우 시간복잡도가 10^6 *.. [Leetcode 9/100] Beautiful Arrangement - Medium leetcode.com/problems/beautiful-arrangement/ Beautiful Arrangement - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 문제 풀이 방식 DFS를 활용하여 모든 경우의 수를 탐색하여 조건 처리 주의할 점 모든 경우의 수를 탐색하여 마지막에 조건을 처리하게 되면 TLE를 보게 된다. 그러므로 조건을 만족하지 않는 경우 재귀 함수를 호출하지 않도록 조건을 설정하는 것이 필수 소스코드 class Solution { in.. 이전 1 2 3 4 다음
