배열 병합
예제 - LeetCode 80. Merge Sorted Array
1. 문제 이해
- 정렬된 두 배열을 병합하기
2. 요구사항 분석
- 입력
- nums1.length = m + n
- nums2.length = n
- 0 <= m, n <= 200
- 1 <= m + n <= 200
- 각 문자열의 요소는 0 또는 1
- -1,000,000,000 <= nums1[i], nums2[i] <= 1,000,000,000 -> int 범위
- 출력
- 없음, (nums1 배열에 채우기)
3. 해결 아이디어
- nums1, nums2에서 큰 값 순서대로 비교하면서 nums1 뒤에서 부터 채우기
4. 시간 복잡도 및 공간 복잡도 확인
- 시간 복잡도
- nums1, nums2를 한번씩 반복하므로 O(n + m)
- 공간 복잡도
- 고정된 개수의 변수만 사용하므로 O(1)
5. 구현
class Solution {
public void merge(int[] nums1, int m, int[] nums2, int n) {
// 1. 인덱스를 표시할 변수 할당
int i1 = m - 1; // nums1의 마지막 유효 원소 인덱스
int i2 = n - 1; // nums2의 마지막 인덱스
int i = m + n - 1; // 병합 결과를 저장할 nums1의 끝 인덱스
// 2. 뒤에서부터 비교하여 큰 값을 nums1의 뒤쪽에 삽입
while (i1 >= 0 && i2 >= 0) {
if (nums1[i1] > nums2[i2]) {
nums1[i--] = nums1[i1--];
} else {
nums1[i--] = nums2[i2--];
}
}
// 3. nums2의 남은 요소가 있다면 nums1에 복사
while (i2 >= 0) {
nums1[i--] = nums2[i2--];
}
}
}
특정 요소 제거
예제 - LeetCode 27. Remove Element
1. 문제 이해
- 배열에서 특정 값을 제거하고, 나머지 값을 앞으로 당기기(뒤에는 어떤 값이 있어도 됨)
2. 요구사항 분석
- 입력
- 0 <= nums.length, val <= 100
- 0 <= nums[i] <= 50
- 출력
- 제거 후 남은 요소의 갯수
3. 해결 아이디어
- 투 포인터
- 요소의 값을 확인할 인덱스, 요소를 저장할 인덱스 두 개의 포인터를 이용
- 특정 요소가 아닌 경우 배열에 채우고 특정 요소인 경우 요소의 값을 확인하는 인덱스만 이동
4. 시간 복잡도 및 공간 복잡도 확인
- 시간 복잡도
- nums 배열을 한번 순회하므로 O(n)
- 공간 복잡도
- 고정된 개수의 변수만 사용하므로 O(1)
5. 구현
class Solution {
public int removeElement(int[] nums, int val) {
// 1. 배열을 채우는 인덱스 변수 할당
int i1 = 0;
// 2. 배열을 전체 순회하며 주어진 값이 아닌 경우 배열에 채우기
for (int i2 = 0; i2 < nums.length; i2++) {
if (nums[i2] != val) {
nums[i1++] = nums[i2];
}
}
return i1;
}
}
정렬된 배열에서 중복된 값 제거
예제 - LeetCode 26. Remove Duplicates from Sorted Array
1. 문제 이해
- 오름차순으로 정렬된 배열에서 중복된 값을 제거한 후 각 원소가 하나씩 존재하도록 수정(정렬 유지)
2. 요구사항 분석
- 입력
- 1 <= nums.length <= 30,000
- -100 <= nums[i] <= 100
- 출력
- 제거 후 남은 요소의 갯수
3. 해결 아이디어
- 투 포인터
- 요소의 값을 확인할 인덱스, 요소를 저장할 인덱스 두 개의 포인터를 이용
- 배열의 이전 값과 비교하며 다를 경우(중복이 아님) 값 갱신, 같을 경우 요소의 값을 확인할 인덱스만 한칸 이동
4. 시간 복잡도 및 공간 복잡도 확인
- 시간 복잡도
- nums 배열을 한번 순회하므로 O(n)
- 공간 복잡도
- 고정된 개수의 변수만 사용하므로 O(1)
5. 구현
class Solution {
public int removeDuplicates(int[] nums) {
// 1. 요소를 저장할 인덱스 할당
int i = 0;
// 2. 배열을 순회하면서 중복된 요소 제거, j는 배열의 값을 확인할 인덱스
for (int j = 1; j < nums.length; j++) {
// 2-1) 이전 값과 동일하지 않다면 중복이 아니므로, 요소값 갱신
if (nums[j] != nums[i]) {
nums[++i] = nums[j];
}
// 2-2) 이전 값과 동일할 경우 i는 유지하고 j만 이동
}
return i + 1;
}
}
추가 예제 - LeetCode 26. Remove Duplicates from Sorted Array 2
이전의 예제에서 이전값 대신에 전전값을 확인하도록 수정하면 풀이 가능
구현
class Solution {
public int removeDuplicates(int[] nums) {
// nums.length가 2인 경우는 항상 성립
if (nums.length <= 2) return nums.length;
// 1. 요소를 저장할 인덱스 할당, 2개까지 가능하므로 2번 인덱스부터 확인
int i = 2;
// // 2. 배열을 순회하면서 중복된 요소 제거(2개까지 가능), j는 배열의 값을 확인할 인덱스
for (int j = 2; j < nums.length; j++) {
// 2-1) 전전 값과 동일하지 않다면 중복이 아니므로, 요소값 갱신
if (nums[j] != nums[i - 2]) {
nums[i++] = nums[j];
}
// 2-2) 전전 값과 동일할 경우 i는 유지하고 j만 이동
}
return i;
}
}
과반수 요소 찾기
예제 - LeetCode 169. Majority Element
1. 문제 이해
- 배열에서 과반수 이상 등장하는 요소 찾기
2. 요구사항 분석
- 입력
- 1 <= nums.length <= 50,000
- - 1,000,000,000 <= nums[i] <= 1,000,000,000
- 출력
- 과반수 이상 등장하는 요소(반드시 존재)
3. 해결 아이디어
- 보이어-무어 투표 알고리즘
- 후보를 하나 정하고 count 계산
- 후보와 같으면 count++, 다르면 count--
- count = 0일때는 새로운 후보로 갱신
- 마지막에 남은 후보가 과반수 이상 등장하는 요소
- 배열을 한번 더 순회하며 과반수인지 확인(현재 문제에서는 반드시 존재하므로 생략 가능)
4. 시간 복잡도 및 공간 복잡도 확인
- 시간 복잡도
- nums 배열을 한번 순회하므로 O(n)
- 공간 복잡도
- 고정된 개수의 변수만 사용하므로 O(1)
5. 구현
class Solution {
public int majorityElement(int[] nums) {
// 1. 후보와 후보의 갯수를 저장할 변수 할당
int candidate = 0;
int count = 0;
// 2. 배열을 순회하면 count 계산 및 후보 갱신
for (int num : nums) {
// 2-1) count가 0일 때는 후보 갱신
if (count == 0) {
candidate = num;
}
// 2-2) 현재 값과 후보가 같으면 +1, 다르면 -1
count += (num == candidate) ? 1 : -1;
}
return candidate;
}
}
배열 회전
예제 - LeetCode 189. Rotate Array
1. 문제 이해
- 배열을 오른쪽으로 k번 회전하기
2. 요구사항 분석
- 입력
- 1 <= nums.length <= 100,000
- nums[i]는 int 범위
- 0 <= k <= 100,000
- 출력
- 오른쪽으로 k번 회전한 배열
3. 해결 아이디어
- 배열 복사 후 덮어 쓰기
- 같은 크기의 배열 만들기
- k번 이동한 인덱스에 따라 배열에 값 채우기
- 배열 뒤집기
- 배열 전체 뒤집기
- 앞에서 부터 k개 뒤집기
- 나머지(n-k)개 뒤집기
- 순환 교체
- 현재 인덱스부터 (i + k) % n만큼 이동해가면서 값 변경
- 처음으로 돌아오면 다음 인덱스 부터 순환
- 모든 값이 순환되었다면 종료
4. 시간 복잡도 및 공간 복잡도 확인
- 시간 복잡도
- 배열 복사 후 뒤집기 : nums 배열을 한번 순회하므로 O(n)
- 배열 뒤집기 : nums 배열을 세번 순회하므로 O(n)
- 순환 교체 : nums 배열을 사이클(n, k의 최대공약수)만큼 순회하므로 O(n)
- 공간 복잡도
- 배열 복사 후 뒤집기 : 복사할 배열이 필요하므로 O(n)
- 배열 뒤집기 : 고정된 개수의 변수만 사용하므로 O(1)
- 순환 교체 : 고정된 개수의 변수만 사용하므로 O(1)
공간 복잡도에 이점이 있고, 직관적인 배열 뒤집기를 선택
5. 구현
class Solution {
public void rotate(int[] nums, int k) {
// 1. 배열의 크기와 순환할 값 할당
int n = nums.length;
k = k % n; // 1-1) k가 n보다 클 경우를 고려하여 나머지 계산
// 2. 전체를 뒤집고, 두 구간으로 나눠 다시 뒤집기
reverse(nums, 0, n - 1); // 전체 뒤집기
reverse(nums, 0, k - 1); // 앞 k개 뒤집기
reverse(nums, k, n - 1); // 나머지 뒤집기
}
// 배열 뒤집기 함수
private void reverse(int[] nums, int start, int end) {
// 앞, 뒤 인덱스를 각각 더하고 빼가며 값 변경하기
while (start < end) {
int temp = nums[start];
nums[start++] = nums[end];
nums[end--] = temp;
}
}
}
H-Index
예제 - LeetCode 274. Rotate Array
https://leetcode.com/problems/h-index/description/?envType=study-plan-v2&envId=top-interview-150
1. 문제 이해
- H-Index(인용 수가 h 이상인 논문이 h편 이상)을 만족하는 가장 큰 h 구하기
2. 요구사항 분석
- 입력
- 1 <= citations.length <= 5,000
- 0 <= citations[i] <= 1,000
- 출력
- h-index(정수)
3. 해결 아이디어
- 인용 수 기준으로 오름차순 정렬
- 현재 논문보다 인용 횟수가 많은 논문의 갯수(h) 구하기
- 현재 논문의 인용 횟수가 h이상이면 최대 h-index
4. 시간 복잡도 및 공간 복잡도 확인
- 시간 복잡도
- 배열의 정렬이 필요하므로 O(nlogn)
- 공간 복잡도
- 고정된 개수의 변수만 사용하므로 O(1)
5. 구현
class Solution {
public int hIndex(int[] citations) {
int n = citations.length;
// 1. 배열 오름차순 정렬
Arrays.sort(citations);
// 2. 배열을 순회하며 h-index 찾기
for (int i = 0; i < n; i++) {
// 2-1) 현재 논문보다 인용 횟수가 많은 논문의 갯수는 n - i
int h = n - i;
// 2-2) 현재 논문의 인용 횟수가 h를 넘었으면 최대 h-index(i가 커질수록 h가 작아지므로)
if (citations[i] >= h) {
return h;
}
}
return 0;
}
}
접두사-접미사
예제 - LeetCode 238. Product of Array Except Self
1. 문제 이해
- answer[i]는 nums[i]를 제외한 나머지 모든 요소의 곱이 되는 배열만들기
- 전체 곱 계산 후 nums[i]로 나누는 방식은 불가
2. 요구사항 분석
- 입력
- 2 <= nums.length <= 100,000
- -30 <= nums[i] <= 30
- 출력
- answer[i] 배열
3. 해결 아이디어
- 왼쪽 누적곱(prefix)와 오른쪽 누적곱(suffix)을 각각 저장
- answer[i] = 왼쪽 누적곱 * 오른쪽 누적곱
4. 시간 복잡도 및 공간 복잡도 확인
- 시간 복잡도
- 두 번의 배열 순회가 필요하므로 O(n)
- 공간 복잡도
- answer 배열이 필요하므로 O(n)
5. 구현
class Solution {
public int[] productExceptSelf(int[] nums) {
int n = nums.length;
// 1. 정답을 저장할 배열 할당
int[] answer = new int[n];
// 2. 왼쪽 누적곱을 계산하여 answer에 저장
answer[0] = 1;
for (int i = 1; i < n; i++) {
answer[i] = answer[i - 1] * nums[i - 1];
}
// 3. 오른쪽 누적곱을 저장하면서 answer와 곱함
int right = 1;
for (int i = n - 1; i >= 0; i--) {
answer[i] *= right;
right *= nums[i];
}
return answer;
}
}
랜덤Set 만들기
예제 - LeetCode 380. Insert Delete GetRandom O(1)
1. 문제 이해
- 삽입, 삭제, 랜덤 조회 연산의 시간 복잡도가 O(1)인 RandomizedSet 만들기
2. 요구사항 분석
- 입력
- val은 int 범위
- 각각의 메소드는 200,000번 이상 호출됨
- getRandom 메서드는 최소 한개 이상의 요소가 있을 때 호출됨
- 출력
- 메서드 결과
3. 해결 아이디어
- ArrayList : 인덱스를 통해 O(1) 랜덤 접근 가능
- HashMap : 원소에 해당하는 인덱스를 매핑하여 O(1) 접근 가능
- 삭제 시에는 마지막 원소와 교체 후 pop함으로 O(1) 수행 가능
4. 시간 복잡도 및 공간 복잡도 확인
- 시간 복잡도
- 리스트와 해시맵을 활용하여 해당 값에 바로 접근 가능하므로 O(1)
- 공간 복잡도
- n크기의 배열과 맵이 필요하므로 O(n)
5. 구현
public class RandomizedSet {
// 1. 리스트, 맵, 랜덤 초기화
private List<Integer> list;
private Map<Integer, Integer> map;
private Random rand;
public RandomizedSet() {
list = new ArrayList<>();
map = new HashMap<>();
rand = new Random();
}
// 2. 삽입
public boolean insert(int val) {
// 2-1) containsKey를 사용하여 중복을 바로 확인
if (map.containsKey(val)) return false;
// 2-2) 중복이 아닌 경우 맵과 리스트에 값, 인덱스 저장
map.put(val, list.size());
list.add(val);
return true;
}
// 3. 삭제
public boolean remove(int val) {
// 3-1) containsKey를 사용하여 중복을 바로 확인
if (!map.containsKey(val)) return false;
// 3-2) 맵을 통해 해당 요소의 인덱스를 바로 확인
int index = map.get(val);
// 3-3) 마지막 요소와 해당 요소를 교체 후 제거
int lastElement = list.get(list.size() - 1);
list.set(index, lastElement);
map.put(lastElement, index);
// 3-4) 마지막 요소 제거
list.remove(list.size() - 1);
map.remove(val);
return true;
}
// 4. 랜덤 조회
public int getRandom() {
// 4-1) 리스트의 인덱스 중 랜덤한 값을 선택 후 해당 요소 반환
int index = rand.nextInt(list.size());
return list.get(index);
}
}'코딩테스트 > 알고리즘' 카테고리의 다른 글
| 예제로 배우는 알고리즘 - 문자열 (0) | 2025.04.28 |
|---|---|
| 예제로 배우는 알고리즘 - 해싱 (0) | 2025.04.19 |
| 예제로 배우는 알고리즘 - 비트 마스킹 (0) | 2025.04.04 |
| 예제로 배우는 알고리즘 - 수학 (0) | 2025.03.29 |
| 예제로 배우는 알고리즘 - 투 포인터 (0) | 2025.03.06 |