Merge Sorted Array
정렬된 배열 병합
문제 설명
두 개의 정수 배열 nums1과 nums2가 비내림차순(오름차순 포함) 으로 정렬되어 주어집니다.
또한, 두 정수 m과 n이 주어지며, 이는 각각 nums1과 nums2에 포함된 실제 요소의 개수를 나타냅니다.
nums1과 nums2를 하나의 정렬된 배열로 병합하세요.
최종 병합된 배열은 함수의 반환값이 아니라, nums1 내부에 직접 저장되어야 합니다.
이를 위해 nums1은 길이가 m + n이며,
앞의 m개 원소만 유효한 값이고, 나머지 n개의 0은 빈 공간으로 제공됩니다
nums2는 길이가 n입니다.
예제 1
입력: nums1 = [1,2,3,0,0,0], m = 3
nums2 = [2,5,6], n = 3
출력: [1,2,2,3,5,6]
설명: 병합 대상 배열은 [1,2,3] 과 [2,5,6] 이며,
결과는 정렬된 [1,2,2,3,5,6] 입니다.
Plain Text
복사
예제 2
입력: nums1 = [1], m = 1
nums2 = [], n = 0
출력: [1]
설명: 병합 대상은 [1] 과 [] 이며 결과는 [1]입니다.
Plain Text
복사
예제 3
입력: nums1 = [0], m = 0
nums2 = [1], n = 1
출력: [1]
설명: m = 0이므로 nums1에는 유효한 값이 없으며,
[1]을 병합한 결과가 [1]입니다.
Plain Text
복사
제약 조건
•
nums1.length == m + n
•
nums2.length == n
•
0 <= m, n <= 200
•
1 <= m + n <= 200
•
10⁹ <= nums1[i], nums2[j] <= 10⁹
추가 과제 (Follow-up)
시간 복잡도 O(m + n) 으로 동작하는 알고리즘을 구현해보세요.
First Bad Version
첫 번째 불량 버전 찾기
문제 설명
당신은 **제품 관리자(Product Manager)**이며, 새 제품의 개발을 총괄하고 있습니다.
하지만 안타깝게도 최근 출시된 버전부터 품질 검사에 실패하고 있습니다.
각 버전은 이전 버전을 기반으로 개발되기 때문에,
어떤 한 버전이 불량이면, 그 이후의 모든 버전도 모두 불량입니다.
이제 n개의 버전이 있다고 가정합시다. 버전 번호는 [1, 2, ..., n]입니다.
당신은 이 중에서 가장 첫 번째로 불량인 버전을 찾아야 합니다.
(이 버전 이후로는 모두 불량이기 때문입니다.)
제공되는 기능
bool isBadVersion(int version)
{
return bad <= x;
}
C++
복사
이 함수는 해당 버전이 불량인지 여부를 알려줍니다.
목표
다음 조건을 만족하는 firstBadVersion(int n) 함수를 구현하세요:
•
isBadVersion(version) API 호출 횟수를 최소화할 것
예제
예제 1
입력: n = 5, bad = 4
출력: 4
설명:
isBadVersion(3) → false
isBadVersion(5) → true
isBadVersion(4) → true
결론적으로, 첫 번째 불량 버전은 4입니다.
int bad = 4; // bad 버전
Plain Text
복사
예제 2
입력: n = 1, bad = 1
출력: 1
Plain Text
복사
제약 조건
•
1 <= bad <= n <= 2^31 - 1
힌트
•
이진 탐색(Binary Search) 을 활용하면 효율적으로 해결 가능
•
가능한 한 적은 횟수로 isBadVersion()을 호출해야 하므로 선형 탐색은 비효율적
