LeetCode는 프로그래밍 문제를 풀며 코딩 실력을 향상할 수 있는 온라인 플랫폼입니다. 다양한 알고리즘 및 데이터 구조 문제를 제공하며, 면접 대비에 유용합니다. 해당 문제는, LeetCode Problems에서 볼 수 있는 난이도 '쉬움 (Easy)' 단계인 "How Many Numbers Are Smaller Than The Current Number" 문제입니다.
--> https://leetcode.com/problems/how-many-numbers-are-smaller-than-the-current-number/description/
문제 :
Given the array nums, for each nums[i] find out how many numbers in the array are smaller than it.
That is, for each nums[i] you have to count the number of valid j's such that j != i and nums[j] < nums[i].
Return the answer in an array.
Example 1 :
Input : nums = [8,1,2,2,3]
Output : [4,0,1,1,3]
Explanation: For nums[0]=8 there exist four smaller numbers than it (1, 2, 2 and 3).
For nums[1]=1 does not exist any smaller number than it.
For nums[2]=2 there exist one smaller number than it (1).
For nums[3]=2 there exist one smaller number than it (1).
For nums[4]=3 there exist three smaller numbers than it (1, 2 and 2).
Example 2 :
Input : nums = [6,5,4,8]
Output : [2,1,0,3]
Example 3 :
Input : nums = [7,7,7,7]
Output : [0,0,0,0]
Constraints :
- 2 <= nums.length <= 500
- 0 <= nums[i] <= 100
이 문제는 주어진 정수 배열 nums에 대해, 각 요소 nums[i]보다 작은 숫자들의 개수를 찾아 반환하는 문제입니다. 각 요소에 대해 nums[j] < nums[i]를 만족하는 유효한 인덱스 j의 개수를 세어야 합니다.
class Solution {
public int[] smallerNumbersThanCurrent(int[] nums) {
int[] res = new int[nums.length];
for (int i = 0; i < nums.length; i++) {
int count = 0;
for (int j = 0; j < nums.length; j++) {
if (nums[i] > nums[j]) {
count++;
}
}
res[i] = count;
}
return res;
}
}
이 코드는 주어진 정수 배열 nums에서 각 요소보다 작은 요소의 개수를 찾고, 그 결과를 배열로 반환하는 문제를 해결합니다.
코드 구조
- 결과 배열 초기화:
- 결과를 저장할 배열 res를 nums와 같은 크기로 초기화합니다.
-
javaCopy codeint[] res = new int[nums.length];
- 이중 반복문을 통한 비교:
- 외부 반복문은 nums 배열의 각 요소 nums[i]에 대해 순회합니다.
- count 변수를 초기화하여 각 nums[i]보다 작은 수의 개수를 셉니다.
- 내부 반복문은 nums의 모든 요소 nums[j]를 탐색하여 nums[i] > nums[j] 조건을 만족하는지 확인합니다.
- nums[i] > nums[j]이면 count를 증가시킵니다.
- 내부 반복문이 끝나면, res[i]에 count를 저장하여 nums[i]보다 작은 수의 개수를 기록합니다.
-
javaCopy codefor (int i = 0; i < nums.length; i++) { int count = 0; for (int j = 0; j < nums.length; j++) { if (nums[i] > nums[j]) { count++; } } res[i] = count; }
- 결과 반환:
- 최종적으로 res 배열을 반환합니다. 이 배열에는 각 요소에 대해 더 작은 수의 개수가 저장되어 있습니다.
시간 복잡도
- O(n^2) : 이중 반복문을 사용하여 배열의 모든 쌍을 비교하므로 시간 복잡도는 O(n^2)입니다. 여기서 n은 배열의 길이입니다.
- 첫 번째 반복문은 n번 반복하고, 두 번째 반복문도 n번 반복합니다. 따라서 총 연산 횟수는 n * n입니다.
공간 복잡도
- O(n) : 결과를 저장할 res 배열이 필요합니다. 이 배열의 크기는 nums와 같으므로 O(n)의 공간을 사용합니다.
코드의 장점과 한계
장점
- 간단함 : 코드가 간단하고 직관적입니다. 각 요소를 다른 모든 요소와 비교하여 작은 수의 개수를 세는 명확한 로직을 사용합니다.
- 빠른 구현 : 브루트 포스 접근법으로 간단히 구현할 수 있어, 문제의 제약이 작은 경우에 유용합니다.
한계
- 비효율성 : 큰 입력 크기에 대해서는 비효율적일 수 있습니다. O(n^2)의 시간 복잡도를 갖기 때문에 최악의 경우 500 * 500 = 250,000번의 비교가 필요합니다.
- 최적화 부족 : 더 효율적인 알고리즘(예: 정렬을 사용한 O(n log n) 솔루션)과 비교하여 최적화가 부족합니다.
그래서 시간 복잡도가 더 낮은, 해시맵과 Arrays.sort() 메소드를 쓴 코드가 하나 있습니다 :
class Solution {
public int[] smallerNumbersThanCurrent(int[] nums) {
int[] sortedNums = nums.clone();
Arrays.sort(sortedNums);
HashMap<Integer, Integer> numCounts = new HashMap<>();
for (int i = 0; i < sortedNums.length; i++) {
numCounts.putIfAbsent(sortedNums[i], i);
}
int[] res = new int[nums.length];
for (int i = 0; i < nums.length; i++) {
res[i] = numCounts.get(nums[i]);
}
return res;
}
}
- 배열 복사 및 정렬 :
- 주어진 배열 nums를 sortedNums라는 배열로 복사합니다. 이렇게 하면 원본 배열 nums를 보존할 수 있습니다.
- sortedNums 배열을 오름차순으로 정렬합니다.
- 해시맵을 사용한 작은 수의 개수 계산 :
- numCounts라는 해시맵을 사용하여 정렬된 배열에서 각 숫자의 첫 번째 등장 위치를 저장합니다.
- 이 인덱스는 현재 숫자보다 작은 숫자의 개수를 나타냅니다.
- putIfAbsent 메서드를 사용하여 숫자가 처음 등장할 때만 인덱스를 저장합니다.
- 결과 배열 생성 :
- 결과를 저장할 배열 res를 nums와 같은 크기로 초기화합니다.
- 원본 배열 nums의 각 요소에 대해, 해당 숫자보다 작은 숫자의 개수를 numCounts에서 가져와 res에 저장합니다.
- 결과 반환 :
- 최종적으로 결과 배열 res를 반환하여 각 요소에 대해 더 작은 숫자의 개수를 제공합니다.
시간 복잡도
- O(n log n) : 주된 시간 복잡도는 배열 정렬에 의해 결정됩니다. 정렬은 O(n log n) 시간이 소요됩니다. 그 이후의 해시맵 생성과 배열 순회는 O(n) 시간 복잡도를 가지므로 전체적으로 O(n log n)입니다.
공간 복잡도
- O(n) : 추가적인 저장 공간은 sortedNums 배열과 numCounts 해시맵에 사용됩니다. 모두 입력 배열의 크기와 비례하여 O(n)의 공간 복잡도를 가집니다.
전 코드보다 더 나은 점
- 효율성 :
- 이전 코드에서는 이중 반복문을 사용하여 시간 복잡도가 O(n²)였으나, 현재 코드는 O(n log n)으로 효율성을 크게 개선했습니다. 정렬과 해시맵을 통해 불필요한 반복을 제거했습니다.
- 가독성 :
- 코드가 구조적으로 더 깔끔하며 이해하기 쉬워졌습니다. 정렬을 사용하여 문제를 단순화하고, 해시맵으로 각 요소의 작은 숫자 개수를 쉽게 찾을 수 있습니다.
- HashMap 활용 :
- 해시맵을 사용하여 각 숫자에 대한 정보를 효율적으로 저장하고 조회하여, 중복 계산을 줄이고 성능을 향상했습니다.
- 일관된 성능 :
- 정렬 기반 접근 방식은 다양한 입력 크기와 값에 대해 일관된 성능을 제공합니다. 반면에, 브루트 포스 방식은 입력이 클수록 성능이 급격히 저하될 수 있습니다.
이런 노력에도 불구하고 제 코드는 최고로 효율적이지 못했습니다. 해서, 다른 유저분의 코드를 보고 납득이 됐습니다 :
class Solution {
public int[] smallerNumbersThanCurrent(int[] nums) {
int max = -1;
for(int num : nums){
max = Math.max(max, num);
}
int[] count = new int[max + 1];
for(int num : nums){
count[num]++;
}
int[] prefix = new int[count.length + 1];
for(int i = 1 ; i < prefix.length; i++){
prefix[i] = prefix[i - 1] + count[i - 1];
}
int[] res = new int[nums.length];
for(int i = 0 ; i < nums.length; i++){
res[i] = prefix[nums[i]];
}
return res;
}
}
// Hamata 유저의 코드
이 분은, 친절하게 코드 설명 및 시간 / 공간 복잡도 설명을 해주셨는데요, 하신 거 번역해서 공유하겠습니다 :
접근 방법
- 최댓값 찾기 :
- 첫 번째 반복문에서는 배열 nums에서 가장 큰 숫자를 찾습니다. 이는 count 배열의 크기를 결정하는 데 사용됩니다.
- 각 숫자의 발생 횟수 세기 :
- 두 번째 반복문에서는 nums의 각 숫자의 발생 횟수를 count 배열에 저장합니다. count[i]는 nums에서 숫자 i가 몇 번 나오는지를 저장합니다.
- 누적 합 계산 :
- prefix 배열을 사용하여 count 배열의 누적 합을 계산합니다. 즉, prefix[i]는 count 배열의 0부터 i-1까지의 요소들의 합을 저장합니다.
- 결과 계산 :
- 마지막 반복문에서는 prefix 배열을 사용하여 결과를 계산합니다. nums의 각 요소에 대해 해당 요소보다 작은 숫자의 개수를 찾아 res 배열에 저장합니다.
복잡도
- 시간 복잡도 : O(n) : 배열을 한 번 순회하면서 필요한 모든 작업을 수행하기 때문에 시간 복잡도는 O(n)입니다.
- 공간 복잡도 : O(n) : count 및 prefix 배열의 크기가 최댓값에 비례하므로 공간 복잡도는 O(n)입니다.
요약
이 접근 방법은 주어진 배열에서 각 숫자보다 작은 숫자의 개수를 효율적으로 계산하는 방법입니다. 먼저, 배열에서 가장 큰 숫자를 찾아 count 배열을 초기화하고, 각 숫자의 발생 횟수를 기록합니다. 그런 다음, prefix 배열을 통해 count 배열의 누적 합을 계산하여, 결과 배열을 생성합니다. 이 방법은 시간과 공간 복잡도가 모두 O(n)으로 효율적입니다.
'LeetCode' 카테고리의 다른 글
| [LeetCode] - 896. Monotonic Array (0) | 2024.08.02 |
|---|---|
| [LeetCode] - 349. Intersection of Two Arrays (0) | 2024.08.02 |
| [LeetCode] - 2706. Buy Two Chocolates (0) | 2024.08.02 |
| [LeetCode] - 961. N-Repeated Element in Size 2N Array (0) | 2024.08.02 |
| [LeetCode] - 867. Transpose Matrix (0) | 2024.08.02 |
