알고리즘/리트코드
leetcode - 350. Intersection of Two Arrays II
[문제 바로가기] 1. 유형 구현, 정렬 2. 문제 분석 두 배열의 교집합을 구하는 문제였습니다. 요즘 Stream을 공부 중인데, for을 최소한으로 사용을 연습을 위해 풀어봤습니다. 3. 코드 static public int[] solution(int[] nums1, int[] nums2) { List list = new ArrayList(); Map n = new HashMap(); Map m = new HashMap(); Arrays.stream(nums1).forEach(x -> n.put(x, n.getOrDefault(x, 0) + 1)); Arrays.stream(nums2).forEach(x -> m.put(x, m.getOrDefault(x, 0) + 1)); for (int k : n..
329. Longest Increasing Path in a Matrix
leetcode.com/problems/longest-increasing-path-in-a-matrix/ Longest Increasing Path in a Matrix - 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 + DP + 백트래킹 풀이: 완전탐색으로 DFS로 풀면 시간초과가 난다. 따라서 나는 DP를 선택했다. 그럼에도 불구하고 마지막 테스터케이서 4개에서 시간초과가 났다. 따라서 백트래킹..
581. Shortest Unsorted Continuous Subarray
leetcode.com/problems/shortest-unsorted-continuous-subarray/ Shortest Unsorted Continuous Subarray - 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 문제: 문자 배열이 주어진다. 이것을 오름차순으로 만들기 위해 수정해야하는 배열의 길이를 구하시오. 즉, 1번 케이스에서 6 4 8 10 9 부분을 오름차순 정렬하면 전체가 오름차순이 된다. 이떄의 길이는 5이므로 5를 리턴한다. 접근법:..
621. Task Scheduler
leetcode.com/problems/task-scheduler/submissions/ Task Scheduler - 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 접근법 그리디한 문제 해석. 같은 업무일 경우 최소 N만큼 떨어져 있어야한다. ["A","A","A","B","B","B"], n = 2인 경우 A B _ A B _ A B 처럼 업무를 처리해야한다. 풀이 1) 가장 많이 나오는 알파펫 파악 2) idle을 감소 먼저 가장 많이 나오는 문자를 구해야..
리트코드 - 데일리과제(3/30) Russian Doll Envelopes
1. 접근법 다이나믹프로그래밍 2. 로직 이 문제는 LIS를 사전에 알아야 풀 수 있는 문제다. LIS를 구현하는 법은 o(n^2) 부터 nlogn 까지 있다. 나같은 경우는 n^2으로 풀이를 했다. 1) 오른차순 정렬 2) 현재 인덱스 전까지 비교하며 메모리제이션 한다. 3. 코드 class Solution { public int maxEnvelopes(int[][] envelopes) { Arrays.sort(envelopes, new Comparator(){ public int compare(int pair1[], int pair2[]){ if(pair1[0] == pair2[0]){ return pair1[1] - pair2[1]; } return pair1[0] - pair2[0]; } }); ..
리트코드 데일리과제(3/27) - palindromic-substrings
leetcode.com/problems/palindromic-substrings/ Palindromic Substrings - 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 1. 유형 구현 2. 풀이 번역 1) 앞과 뒤에서 읽었을때, 같은 문장을 고른다. 2) 시작과 끝 값이 다르면 다른 문장으로 정의한다 투포인터를 활용해서 문제 해결. 3. 풀이 class Solution { public int countSubstrings(String s) { List lis..
리트코드 데일리과제(3/26) - 916. Word Subsets
leetcode.com/problems/word-subsets/ Word Subsets - 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 1. 유형 구현 2. 풀이 접근법 1) 해쉬맵 B의 각 요소별 최대값을 해쉬맵으로 구현한다. 즉, B [e, oo] 라고 치면 라고 저장하는 방법이다. 그리고 마지막에 A도 같은 방식으로 딕셔너리를 만들어주고, 딕셔너리B하고 비교하여 A딕셔너리가 B의 딕셔너리보다 더 크면 포함관계다. 예를들어 A의 facebook이 있다면, ..
리트코드 데일리과제(3/25) - Pacific Atlantic Water Flow
leetcode.com/problems/pacific-atlantic-water-flow/ 1. 유형 BFS 2. 풀이 각 셀마다 bfs를 돌려주면 된다. 이때, 문제에서 요구한 조건대로, 대서양과 태평양에 닿았는지만 체크. 둘다 닿았으면 가능한 셀 다른 풀이 모범답안에서는 bfs를 단 두번만 호출해서 풀었다. 이런 식으로 태평양에서 bfs를 돌려주고, 대서양에서 bfs를 돌려서 경계선을 구한다. matix를 탐색하며 경계선만 체크해주면 된다. 3. 코드 class Solution { static boolean visit[][]; static int dr[] = {-1,1,0,0}; static int dc[] = {0,0,-1,1}; static int rowSize, colSize; static in..
리트코드 데일리과제(3/24) - Advantage Shuffle
leetcode.com/explore/challenge/card/march-leetcoding-challenge-2021/591/week-4-march-22nd-march-28th/3683/ 1. 유형 우선순위큐 2. 풀이 - B의 데이터 보다 A배열이 최소의 차이로 큰 값을 찾으면 됩니다. 이를 위해서, A를 정렬 B는 우선순위큐를 사용해서 정렬 마지막으로 A배열에서 투포인터를 사용 3. 코드 class Solution { public int[] advantageCount(int[] A, int[] B) { int answer[] = new int[A.length]; Arrays.sort(A); PriorityQueue pq = new PriorityQueue(new Comparator(){ @Over..
리트코드 데일리과제(3/22) - Vowel Spellchecker
leetcode.com/explore/challenge/card/march-leetcoding-challenge-2021/591/week-4-march-22nd-march-28th/3681/ Explore - LeetCode LeetCode Explore is the best place for everyone to start practicing and learning on LeetCode. No matter if you are a beginner or a master, there are always new topics waiting for you to explore. leetcode.com 1. 유형 해시맵 2. 풀이 문제 해석 쿼리가 단어 목록의 단어(대소문자 구분)와 정확히 일치하면 동일한 단어를 반..