리트코드 LeetCode Height Checker

문제 : https://leetcode.com/problems/height-checker/

Height Checker - LeetCode

 

풀이 : 선형시간 정렬 (계수정렬)

2021.10.05 - [알고리즘/알고리즘] - 선형시간 정렬

선형시간 정렬

 

구현 JAVA

class Solution {
    public int heightChecker(int[] heights) {
	        
		 int min = Integer.MAX_VALUE;
		 int max = Integer.MIN_VALUE;
		 
		 for(int h : heights) {
			if(min>h) min = h;
			if(max<h) max = h;
		 }
		 
		 return countingSort(heights, min, max);
		 
		 
	 }
	 
	 public int countingSort(int[] arr, int min, int max) {
		 
		 int[] count = new int[max-min+1];
		 int[] out = new int[arr.length];

		 //각 요소별 갯수 세기
		 for(int a: arr) {
			 count[a-min]++;
		 }
		 //각 요소별 첫 위치값을 구하기 위해 값을 누적
		 for(int c = 1; c<count.length; c++) {
			 count[c] += count[c-1];
		 }
		 for(int i = 0; i<arr.length; i++) {
			 int countIndex = arr[i]-min;
			 int outIndex = count[countIndex]-1;
			 out[outIndex] = arr[i];
			 //값을 셋팅 후 요소의 위치값을 줄여나감
			 count[countIndex]--;
		 }
		 
         int answer = 0;
		 for(int i =0; i<arr.length; i++) {
			 if(arr[i] != out[i]) {
				 answer++;
			 }
		 }
		 
		 return answer;
	 }
}