본문 바로가기
728x90
반응형

sort7

56. Merge Intervals 📌 문제 설명intervals 배열이 주어지고,각 원소는 [start, end] 형태입니다.겹치는 interval을 모두 병합해서 반환하세요.Input: intervals = [[1,3],[2,6],[8,10]]Output: [[1,6],[8,10]] 정렬: 시작 기준 정렬 완료 [[1,3], [2,6], [8,10]]초기값: merged = [[1,3]]다음 구간 [2,6] 확인:1,3의 끝(3)이 2,6의 시작(2)보다 큽니다. (겹침!)merged의 마지막을 [1, max(3, 6)] 즉, [1, 6]으로 업데이트합니다.다음 구간 [8,10] 확인:1,6의 끝(6)이 8,10의 시작(8)보다 작습니다. (안 겹침!)merged에 [8,10]을 새로 추가합니다.최종: [[1,6], [8,10]]cl.. 2026. 1. 18.
Max Min 주어진 숫자 배열에서 $k$개의 숫자를 골랐을 때, 가장 큰 값(max)과 가장 작은 값(min)의 차이가 최소가 되도록 만드는 문제입니다. 이 차이를 문제에서는 Unfairness(불공정함)라고 부릅니다. 1. 핵심 아이디어: 정렬(Sorting)가장 큰 값과 가장 작은 값의 차이를 줄이려면, 서로 값이 비슷한 숫자들끼리 모아야 합니다. 뒤죽박죽 섞여 있는 배열에서 비슷한 숫자들을 찾는 가장 쉬운 방법은 무엇일까요? 바로 정렬입니다.배열을 오름차순으로 정렬하면, 서로 이웃한 숫자들은 항상 차이가 가장 적은 숫자들이 됩니다. 2. 접근 방식배열 arr를 오름차순으로 정렬합니다.정렬된 배열에서 연속된 k개의 원소를 선택합니다. (정렬되어 있기 때문에, 연속된 k개를 골랐을 때 첫 번째 원소가 min이고 마.. 2026. 1. 16.
Minimum Loss 주어진 가격 배열에서 구매 가격이 판매 가격보다 크면서, 그 차이가 최소가 되는 경우를 찾는 알고리즘 문제입니다. 단, 구매 시점(인덱스)은 판매 시점보다 앞서야 합니다. 접근 방식: 정렬을 이용한 최적화단순하게 중첩 반복문(Brute Force)을 사용하면 시간 복잡도가 $O(n^2)$이 되어, 데이터가 커질 경우(최대 $10^5$) 시간 초과가 발생합니다. 따라서 정렬을 활용하여 $O(n \log n)$으로 해결해야 합니다.가격과 원래 인덱스 저장: 정렬 후에도 원래 몇 번째 연도였는지 확인해야 하므로, (가격, 인덱스) 쌍으로 데이터를 저장합니다.가격순 정렬: 가격을 내림차순(큰 순서대로)으로 정렬합니다.인접한 값 비교: 손실을 최소화하려면 정렬된 상태에서 서로 붙어 있는 값들을 비교해야 합니다.조.. 2026. 1. 16.
15. 3Sum 핵심은 중복된 조합을 피하면서 합이 0이 되는 세 숫자를 효율적으로 찾는 것입니다. 브루트 포스(3중 반복문)로 풀면 시간 복잡도가 O(n^3)이 되어 시간 초과가 날 가능성이 높다.따라서 정렬과 투 포인터(Two Pointers) 기술을 사용하여 O(n^2)의 효율로 해결하는 것이 정석이다. 💡 문제 해결 전략정렬: 먼저 배열을 오름차순으로 정렬합니다. 정렬을 하면 중복 숫자를 건너뛰기 쉽고, 투 포인터를 사용할 수 있게 됩니다.고정 포인트 선택: 반복문을 돌며 현재 숫자(nums[i])를 '첫 번째 숫자'로 고정합니다.투 포인터 활용: 고정된 숫자 이후의 범위에서 left 포인터(시작)와 right 포인터(끝)를 설정합니다.sum sum > 0: 합이 크므로 right를 왼쪽으로 옮겨 값을 줄입니다.. 2026. 1. 14.
148. Sort List 병합 정렬(Merge Sort) 알고리즘 아이디어를 떠올려야 하는 문제.병합 정렬은 연결 리스트를 정렬하는 데 적합하며, 시간 복잡도 O(nlog⁡n)와  연결 리스트에서 공간 복잡도를 O(1)로 유지할 수 있습니다.public class ListNode { public int val; public ListNode next; public ListNode(int x) { val = x; }}public class Solution { public ListNode SortList(ListNode head) { if (head == null || head.next == null) return head; // Step 1. Split the lis.. 2024. 6. 28.
2089. Find Target Indices After Sorting Array 0으로 시작하는 정수 배열 nums와 목표 요소 target이 주어집니다. 목표 인덱스는 nums[i] == target인 인덱스 i입니다. nums를 비감소 순서로 정렬한 후 nums의 목표 인덱스 목록을 반환하십시오. 목표 인덱스가 없으면 빈 목록을 반환합니다. 반환된 목록은 증가 순서로 정렬되어야 합니다. 예를 들어: 예제 1: 입력: nums = [1,2,5,2,3], target = 2 출력: [1,2] 설명: 정렬 후, nums는 [1, 2, 2 ,3,5]입니다. nums[i] == 2인 인덱스는 1과 2입니다. 예제 2: 입력: nums = [1,2,5,2,3], target = 3 출력: [3] 설명: 정렬 후, nums는 [1,2,2, 3 ,5]입니다. nums[i] == 3인 인덱스는 .. 2024. 3. 27.
Make Array Consecutive 2 주어진 정수 배열을 정렬하고, 배열 안의 연속된 숫자 사이에 빈 공간이 있을 때, 이 빈 공간을 채우기 위해 필요한 추가적인 숫자의 개수를 구하는 문제입니다. 예를 들어, 주어진 배열이 [6, 2, 3, 8]이라면, 이 배열을 정렬하면 [2, 3, 6, 8]이 됩니다. 그런데 3 다음에 4와 5가 빈 공간으로 존재하고, 6과 8사이에 7의 빈 공간이 존재하므로, 최소 3개의 추가 숫자가 필요합니다. 따라서 이 문제는 정렬된 배열에서 숫자들 사이의 갭을 계산하여 필요한 추가 숫자의 수를 구하는 것이 목표입니다. int solution(int[] statues) { Array.Sort(statues); int start = statues[0]; int cnt = 0; int idx = 1; for(int i.. 2023. 11. 22.
728x90
반응형

티스토리툴바