Sort Colors (색 정렬)
빨강, 하양, 파랑으로 색칠된 n개의 원소가 들어있는 배열 nums가 주어집니다.
정렬 라이브러리를 쓰지 않고, 같은 색끼리 인접하도록 제자리(in-place)에서 정렬하세요.
색은 정수 0, 1, 2로 표현하며, 정렬 결과의 순서는 0 → 1 → 2 입니다.
예시 1:
Input: nums = [2,0,2,1,1,0]
Output: [0,0,1,1,2,2]
Plain Text
복사
예시 2:
Input: nums = [2,0,1]
Output: [0,1,2]
Plain Text
복사
제약:
•
n == nums.length
•
1 <= n <= 300
•
nums[i]는 0, 1, 2 중 하나
추가 질문: 상수 extra space만 사용하면서, 한 번의 순회(one-pass)로 풀 수 있나요?
힌트
참고(쉬운 2-pass): 0/1/2 개수를 세고 그 개수만큼 다시 덮어쓰기
Top K Frequent Elements (빈도 상위 K개)
정수 배열 nums와 정수 k가 주어집니다.
가장 자주 등장하는 원소 k개를 반환하세요. 반환 순서는 어떤 순서든 괜찮습니다.
예시 1:
•
Input: nums = [1,1,1,2,2,3], k = 2
•
Output: [1,2]
예시 2:
•
Input: nums = [1], k = 1
•
Output: [1]
예시 3:
•
Input: nums = [1,2,1,2,1,2,3,1,3,2], k = 2
•
Output: [1,2]
제약:
•
1 <= nums.length <= 10^5
•
-10^4 <= nums[i] <= 10^4
•
k는 [1, 서로 다른 원소 개수] 범위
•
정답은 유일함이 보장됨
추가 질문: 시간 복잡도가 O(n log n)보다 더 좋아야 합니다.
Kth Largest Element in an Array (배열에서 k번째로 큰 원소)
정수 배열 nums와 정수 k가 주어집니다.
배열에서 k번째로 큰 값을 반환하세요.
주의: “서로 다른 값 기준 k번째”가 아니라, 정렬했을 때의 k번째입니다.
정렬 없이 풀 수 있나요?
예시 1:
Input: nums = [3,2,1,5,6,4], k = 2
Output: 5
Plain Text
복사
예시 2:
Input: nums = [3,2,3,1,2,4,5,5,6], k = 4
Output: 4
Plain Text
복사
제약:
•
1 <= k <= nums.length <= 10^5
•
-10^4 <= nums[i] <= 10^4
Find Peak Element (봉우리 원소 찾기)
배열에서 이웃한 원소들보다 엄격히 큰 원소를 peak(봉우리)라고 합니다.
0-indexed 정수 배열 nums가 주어질 때, peak 원소의 인덱스를 반환하세요.
peak가 여러 개면 그 중 아무거나 반환해도 됩니다.
또한 nums[-1] = nums[n] = -∞라고 가정합니다. 즉, 배열 바깥은 항상 더 작은 값으로 취급합니다.
요구: O(log n) 시간에 동작하는 알고리즘을 작성하세요.
예시 1:
Input: nums = [1,2,3,1]
Output: 2
Explanation: nums[2] = 3 이 양쪽 이웃보다 크므로 peak
Plain Text
복사
예시 2:
Input: nums = [1,2,1,3,5,6,4]
Output: 5
Explanation: 인덱스 1(값 2)도 가능, 인덱스 5(값 6)도 가능
Plain Text
복사
제약:
•
1 <= nums.length <= 1000
•
-2^31 <= nums[i] <= 2^31 - 1
•
모든 유효한 i에 대해 nums[i] != nums[i+1]
Search for a Range (구간 찾기)
비내림차순(오름차순, 중복 허용)으로 정렬된 배열 nums와 target이 주어집니다.
target 값이 처음 등장하는 위치와 마지막으로 등장하는 위치를 [start, end]로 반환하세요.
존재하지 않으면 [-1, -1]을 반환합니다.
요구: O(log n) 시간 복잡도로 풀어야 합니다.
예시 1:
Input: nums = [5,7,7,8,8,10], target = 8
Output: [3,4]
Plain Text
복사
예시 2:
Input: nums = [5,7,7,8,8,10], target = 6
Output: [-1,-1]
Plain Text
복사
예시 3:
Input: nums = [], target = 0
Output: [-1,-1]
Plain Text
복사
제약:
•
0 <= nums.length <= 10^5
•
-10^9 <= nums[i] <= 10^9
•
nums는 비내림차순
•
-10^9 <= target <= 10^9
Merge Intervals (구간 병합)
intervals[i] = [start_i, end_i] 형태의 구간 배열이 주어집니다.
서로 겹치는 구간들을 모두 병합한 뒤, 서로 겹치지 않는 구간들의 배열을 반환하세요.
예시 1:
Input: intervals = [[1,3],[2,6],[8,10],[15,18]]
Output: [[1,6],[8,10],[15,18]]
Explanation: [1,3]과 [2,6]이 겹치므로 [1,6]으로 병합
Plain Text
복사
예시 2:
Input: intervals = [[1,4],[4,5]]
Output: [[1,5]]
Explanation: [1,4]와 [4,5]는 겹치는 것으로 취급
Plain Text
복사
예시 3:
Input: intervals = [[4,7],[1,4]]
Output: [[1,7]]
Explanation: [1,4]와 [4,7]이 이어지므로 [1,7]
Plain Text
복사
제약:
•
1 <= intervals.length <= 10^4
•
intervals[i].length == 2
•
0 <= start_i <= end_i <= 10^4
Search in Rotated Sorted Array (회전된 정렬 배열에서 검색)
서로 다른 값으로 이루어진 오름차순 배열 nums가 있습니다.
이 배열이 어떤 인덱스 k를 기준으로 왼쪽으로 회전될 수 있습니다.
예: [0,1,2,4,5,6,7]가 k=3이면 [4,5,6,7,0,1,2].
회전된 배열 nums와 target이 주어질 때,
target이 존재하면 그 인덱스를, 없으면 -1을 반환하세요.
요구: O(log n) 시간 복잡도로 풀어야 합니다.
예시 1:
Input: nums = [4,5,6,7,0,1,2], target = 0
Output: 4
Plain Text
복사
예시 2:
Input: nums = [4,5,6,7,0,1,2], target = 3
Output: -1
Plain Text
복사
예시 3:
Input: nums = [1], target = 0
Output: -1
Plain Text
복사
제약:
•
1 <= nums.length <= 5000
•
-10^4 <= nums[i] <= 10^4
•
모든 값은 유일
•
nums는 오름차순 배열이 회전된 형태
•
-10^4 <= target <= 10^4
Meeting Rooms II (회의실 배정 II)
회의 시간 구간 배열 intervals가 주어집니다. 각 회의는 intervals[i] = [start, end] 입니다.
겹치지 않게 모든 회의를 배정하기 위해 필요한 최소 회의실 개수를 구하세요.
종료 시간이 t인 회의와 시작 시간이 t인 회의는 충돌로 보지 않습니다.
예시 1:
Input: intervals = [[0,40],[5,10],[15,20]]
Output: 2
Explanation: 한 회의실에 [0,40]. 다른 회의실에 [5,10] 후 [15,20].
Plain Text
복사
예시 2:
Input: intervals = [[4,9]]
Output: 1
Plain Text
복사
제약:
•
0 <= intervals.length <= 5000
•
0 <= start < end <= 1,000,000
권장 복잡도: O(n log n) 시간, O(n) 공간
힌트: start 배열과 end 배열을 각각 정렬한 뒤, 두 포인터로 “현재 진행 중인 회의 개수”의 최대값을 구하면 됩니다.
Search a 2D Matrix II (2D 행렬 검색 II)
m x n 정수 행렬 matrix에서 값 target이 존재하는지 효율적으로 찾는 알고리즘을 작성하세요.
이 행렬은 다음 성질을 가집니다.
•
각 행은 왼쪽에서 오른쪽으로 오름차순 정렬
•
각 열은 위에서 아래로 오름차순 정렬
예시 1:
Input: matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 5
Output: true
Plain Text
복사
예시 2:
Input: matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 20
Output: false
Plain Text
복사
제약:
•
m == matrix.length
•
n == matrix[i].length
•
1 <= n, m <= 300
•
-10^9 <= matrix[i][j] <= 10^9
•
각 행/열은 오름차순 정렬
•
-10^9 <= target <= 10^9