[Leetcode] How Many Numbers Are Smaller Than the Current Number

https://leetcode.com/problems/how-many-numbers-are-smaller-than-the-current-number/

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.

---

배열이 주어집니다. 이 배열을 순회하면서 자기 자신보다 작은 값이 몇 개나 있는지 찾는 문제입니다.

[8,1,2,2,3]의 답은 [4,0,1,1,3]가 되는데요.

8보다 작은 수는 4개이고 1보다 작은 수는 없고, 2보다 작은 수는 1개, 3보다 작은 수는 3개가 되어 답이 결정됩니다.

일단 가장 쉬운 방법으로는 brute force 식으로 순회하는 것입니다.

실제로 이 방법으로 문제를 패스하였는데요.

더 좋은 방법으로는 정렬을 이용하면 될거같습니다.

for (int i = 0; i < nums.length; i++) {
	int cnt = 0;
    for (int j = 0; j < nums.length; j++) {
    	if (nums[j] < nums[i]) {
    		cnt++;
    	}
    }
    sol[i] = cnt;
}

이런식으로 전체적인 순회를 하게 됩니다. 시간 복잡도는 O(N^2) 이겠네요.

실제로 테스트도 성공하였습니다.

코드를 조금 수정하도록 하였습니다.

Arrays.sort(arr, Comparator.reverseOrder());

Map<Integer, Integer> tmp = new HashMap<>();

for (int i = 0; i < arr.length - 1; i++) {
	if (!arr[i].equals(arr[i + 1])) {
    	tmp.put(arr[i], arr.length - i - 1);
	}
}

내림차순으로 정렬한 배열을 순회하고 다음 원소와 값이 다르면 배열 길이에서 순회한 만큼 수를 빼줍니다.

그러면 8의 경우에 한번도 순회하지 않았지만, 다음 원소인 4와 비교하여 값이 달라서 전체 길이 5 - 0 - 1 하여 8보다 작은 원소는 4임을 알 수 있습니다.

그렇다면 7,7,7,7,7의 경우에는 어떨까요?

이 경우에는 다음 원소들이 계속해서 같이 때문에 if문을 실행하지 않습니다.

따라서 tmp라는 map에 put이 되지 않을 텐데요. 이 경우를 위해 다음 코드를 추가했습니다.

for (int i = 0; i < nums.length; i++) {
	if (!tmp.containsKey(nums[i])) {
		sol[i] = 0;
        continue;
	}
	sol[i] = tmp.get(nums[i]);
}

파라메터로 받았던 배열을 순회하면서 tmp 라는 맵의 키로 값을 가져옵니다.

하지만 키가 없을 경우에는 0을 넣어줌으로써 같은 값의 경우에도 처리가 됩니다.

생각보다 시간이 많이 빠르진 않는거 같은데요. 다른 분들은 어떻게 해결 했는지 찾아봐야 겠습니다.

아래는 전체 코드 입니다.

class HowManyNumbersAreSmallerThanTheCurrentNumber {
    public static int[] solution(int[] nums) {
        Integer[] arr = Arrays.stream(nums).boxed().toArray(Integer[]::new);
        Arrays.sort(arr, Comparator.reverseOrder());
        int[] sol = new int[nums.length];
        Map<Integer, Integer> tmp = new HashMap<>();

        for (int i = 0; i < arr.length - 1; i++) {
            if (!arr[i].equals(arr[i + 1])) {
                tmp.put(arr[i], arr.length - i - 1);
            }
        }

        for (int i = 0; i < nums.length; i++) {
            if (!tmp.containsKey(nums[i])) {
                sol[i] = 0;
                continue;
            }
            sol[i] = tmp.get(nums[i]);
        }

        return sol;
    }
}