[LeetCode] 1051. Height Checker

leetcode.com/problems/height-checker/

Height Checker - LeetCode

보자마자 떠오른 방법은 정렬한 배열을 만들어서 비교하는것

나중에 풀이를 검색해보니, 대부분이 사람들이 해당 방식을 사용했다.

오늘 추가로 알아낸 점은 Arrays 라이브러리의 copyOf를 사용할 필요없이 clone(); 메서드로 쉽게 배열을 복제할 수 있다는 것! Arrays.copyOf는 예전에 배열 정렬할 때 사용했었는데, 크기가 다른 배열을 만들 때 사용하기 좋았다.

class Solution{
    public int heightChecker(int[] heights) {
        int [] expected = heights.clone();
        Arrays.sort(expected);

        int check = 0;
        for(int i=0;i<heights.length;i++){
            if(heights[i] != expected[i]){
                check++;
            }
        }

        return check;
    }
}

---

NEW

counting sort 라는 방법도 있었다.

배열의 크기가 주어진 것(최대 100)을 이용해서 freq 라는 이름의 배열을 하나 만든다. 

여기에는 해당 수가 몇 개 있는지를 저장하는데 hash 방식이랑 비슷한 것 같다.

 

예를 들어, [1,1,4,2,1,3] 이라는 배열이 있을 경우, 하단과 같이 저장된다.

height 가 배열 index로 들어가게 되므로, 오름차순이 된 상태라 가정했을때 [1,1,1,2,3,4] 여야하므로 같으면 freq 배열을 하나씩 줄이고 다르면 result 변수를 증가시키는 방식으로 진행된다.

freq[1] = 3
freq[2] = 1
freq[3] = 1
freq[4] = 1

for문을 돌며 freq 가 0 이 아닌 index를 찾는다 즉, 여기서는 1,2,3,4 가 된다. 인덱스를 찾았다면 이 인덱스값과 heights[i] 값이 같은지 파악하고, 같다면 오름차순 정렬이 된것이므로 freq[index] 를 하나 줄이고 넘어간다. 다르다면, 오름차순 배열이 되지 않은 것이므로, result 변수를 증가시킨다. 해당 방식으로 for문을 모두 돌면 오름차순 정렬되지 않은 갯수를 구할 수 있다.

class Solution{
    // counting sort
    // make an array : 1 <= heights.length <= 100
    public int heightChecker2(int[] heights) {
        int [] freq = new int [101];

        for (int height : heights) {
            freq[height]++;
        }

        int result = 0;
        int index = 0;
        for(int i=0;i<heights.length;i++){
            while (freq[index] == 0){
                index++;
            }

            if(index != heights[i]){
                result++;
            }
            freq[index]--;
        }

        return result;
    }
}

🔹 동작방식을 좀 더 이해하기 쉽게 적어본 내용

counting sort 라는 방식은 처음봤는데, 굉장히 흥미로웠다. 새로운 방식을 배우는 건 어렵지만 늘 재밌다. 👏