Coding Test/PriorityQueue (3) 썸네일형 리스트형 [Programmers] 42626번 - 더 맵게 1. 문제 파악문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/42626문제 정의: 배열에 저장된 요소값이 K 미만이면, 가장 작은 2개의 값을 주어진 공식에 대입해서 결과값이 k이상이 될수있도록 반복한다. 그리고 모든 값이 K 이상이면 공식에 대입한 회수를 반환해라. 만일, 모든 값들이 k 이상이 될수없다면 -1을 반환해라.문제의 제약 파악 (입력값 크기, 상수 조건)주어진 배열의 길이는 2 이상 1,000,000 이하: 시간복잡도가 O(NlogN) 이내여야 통과한다.2. 문제 풀이1. 브루트 포스로 문제 풀이 도출기존의 배열에서 오름차순 정렬을 한다. -> 정렬: O(nlogn)가장 작은 값을 가져와서 K보다 작다면, 가장 작은 두개.. [Leetcode] 973번 - 원점에 가장 가까운 k개의 점 1. 문제 파악문제 링크: https://leetcode.com/problems/k-closest-points-to-origin/description/문제 정의: 이차원 배열에 저장된 각 배열의 두 요소의 제곱 합이 가장 작은 순서대로 k개를 반환해랴.문제의 제약 파악 (입력값 크기, 상수 조건)1 2. 문제 풀이1. 브루트 포스로 문제 풀이 도출이차원 배열을 각 배열의 두 요소의 제곱 합을 오름차순으로 정렬: O(nlogn)정렬한 배열을 k개 만큼 복사해서 반환: O(k)public int[][] kClosest(int[][] points, int k) { // O(NlogN) Arrays.sort(points, (a, b) -> { int distA = a[0] * a[0] +.. [Leetcode] 23번 k개의 리스트 병합 1. 문제 파악문제 링크: https://leetcode.com/problems/merge-k-sorted-lists/문제 정의: 주어진 오름차순 k개의 연결리스트를 하나의 오름차순 리스트 병합해라.문제의 제약 파악 (입력값 크기, 상수 조건)0 0 2. 문제 풀이1. 브루트 포스로 문제 풀이 도출부르트 포스로 풀이하면, 리스트들을 모두 순회하면서 순차적 병합하는 것이다. 연결리스트의 개수는 k개이고 각 연결리스트의 노드 개수가 n개이면, 이는 for(0 로직이므로 O(kn)이 걸린다. 2. 핵심 문제 풀이 도출(문제 의도 파악): 어떻게 하면 시간 복잡도 내로 줄일수 있을까?시간복잡도 내로 풀기 위해서는 O(NlogN)이나 O(N)으로 풀어야한다. 각 연결리스트의 순회 시간만 하더라도 O(N)이 걸린다.. 이전 1 다음