1051. Height Checker

링크

Height Checker - LeetCode

 

정렬되지 않은 학생들이 있습니다.

학생들을 키순으로 정렬했을 때와 정렬하지 않았을 때를 비교했을 때 잘못 선 학생의 수를 구하시오.

 

[내가 푼 코드]

import java.util.Arrays;

class Solution {
    public int heightChecker(int[] heights) {
        int answer = 0;
        //줄을 순서대로 서지 않은 학생 배열을 복사한 배열.
        int[] expects = Arrays.copyOfRange(heights,0, heights.length);
        //배열을 정렬해서 줄을 제대로 선 학생 배열을 만들어줍니다.
        Arrays.sort(expects);


        for (int i = 0; i < heights.length; i++) {
            //각각의 인덱스를 비교해서 같지 않으면
            //제대로 줄을 서지 않은 것이므로 1을 더해줍니다.
            if (heights[i] != expects[i]) {
                answer++;
            }
        }

        return answer;
    }
}

무지성 정렬한 인덱스를 만든 후에

순서대로 줄을 서지 않은 학생 배열과 줄을 선 학생 배열의 인덱스를 비교해서 같지 않으면 틀린 학생의 수를 더해줬음.

정렬을 사용한다는 점과 배열을 새로 만들어야 한다는 점에서 좋은 코드 같지 않아보임.

근데 딱히 다른 방법이 생각이 안났음.

 

[리트코드 최다 추천 답안]

Java 0ms O(n) solution - no need to sort - LeetCode Discuss

class Solution {
    public int heightChecker(int[] heights) {
        int[] heightToFreq = new int[101];

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

        int result = 0;
        int curHeight = 0;

        for (int i = 0; i < heights.length; i++) {
            while (heightToFreq[curHeight] == 0) {
                curHeight++;
            }

            if (curHeight != heights[i]) {
                result++;
            }
            heightToFreq[curHeight]--;
        }

        return result;
    }
}

정렬이 필요 없는 리트코드 답안입니다.
키가 1~100사이인 것을 이용해 101크기의 인덱스를 만들고 각 인덱스의 키가 몇번 나왔는지 갯수를 추가합니다.
예를 들어 1,1,1,2,3,3가 나오면 {0,3,1,2,............,0,0}이 됩니다.
후에 heights를 이용하여 배열의 갯수만큼 나오는 것을 이용하여, 같은 수가 나오지 않으면 틀린 학생의 수를 더해줍니다.

 

키가 1~100 사이라는 제한이 있는 것을 활용해 잘 푼 문제.

해쉬맵을 사용해서 구현할 수도 있어보입니다.