[LeetCode] - 1051. Height Checker

LeetCode는 프로그래밍 문제를 풀며 코딩 실력을 향상할 수 있는 온라인 플랫폼입니다. 다양한 알고리즘 및 데이터 구조 문제를 제공하며, 면접 대비에 유용합니다. 해당 문제는, LeetCode Problems에서 볼 수 있는 난이도 '쉬움 (Easy)' 단계인 "Height Checker" 문제입니다.

--> https://leetcode.com/problems/height-checker/description/

 

문제 : 

A school is trying to take an annual photo of all the students.

The students are asked to stand in a single file line in non-decreasing order by height.

Let this ordering be represented by the integer array expected where expected[i] is the expected height of the ith student in line.

You are given an integer array heights representing the current order that the students are standing in.

Each heights[i] is the height of the ith student in line (0-indexed). Return the number of indices where

heights[i] != expected[i].

---

Example 1 :

Input : heights = [1,1,4,2,1,3]

Output : 3

Explanation : heights: [1,1,4,2,1,3] expected: [1,1,1,2,3,4] Indices 2, 4, and 5 do not match.

 

Example 2 :

Input : heights = [5,1,2,3,4]

Output : 5

Explanation : heights: [5,1,2,3,4] expected: [1,2,3,4,5] All indices do not match.

 

Example 3 :

Input : heights = [1,2,3,4,5]

Output : 0

Explanation : heights: [1,2,3,4,5] expected: [1,2,3,4,5] All indices match.

 

Constraints :

• 1 <= heights.length <= 100
• 1 <= heights[i] <= 100

---

이 문제에서 학생들이 키 순서대로 정렬되어 사진을 찍으려고 합니다. 학생들이 서 있는 현재의 키 순서가 주어졌을 때, 예상되는 정렬된 키 순서와 비교하여 잘못된 위치에 서 있는 학생들의 수를 구하는 문제입니다.

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

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


    }
}

 

이 코드는 학생들이 서 있는 현재의 키 순서가 주어진 배열 heights를 정렬하여 예상되는 키 순서 배열 expected와 비교하여 잘못된 위치에 서 있는 학생들의 수를 계산합니다.

1. 배열 복사 및 정렬 :
   • heights 배열을 clone() 메소드를 사용하여 복사한 후, expected 배열에 저장합니다.
   • expected 배열을 Arrays.sort() 메소드를 사용하여 오름차순으로 정렬합니다.
2. 비교 및 잘못된 위치 계산 :
   • 원래 heights 배열과 정렬된 expected 배열을 인덱스별로 비교합니다.
   • 두 배열이 다른 값을 가지는 인덱스를 세어서 wrong 변수에 저장합니다.
3. 결과 반환 :
   • wrong 변수를 반환하여 잘못된 위치에 서 있는 학생들의 수를 반환합니다.

시간 복잡도 :

• 배열 복사 : O(n)
  • heights.clone() 메소드는 배열의 모든 요소를 복사하는 데 O(n) 시간이 걸립니다.
• 배열 정렬 : O(n log n)
  • Arrays.sort(expected) 메소드는 배열을 정렬하는 데 O(n log n) 시간이 걸립니다.
• 배열 비교 : O(n)
  • 두 배열을 비교하는 루프는 O(n) 시간이 걸립니다.

따라서 전체 시간 복잡도는 O(n) + O(n log n) + O(n) = O(n log n)입니다.

공간 복잡도 :

• 배열 복사 : O(n)
  • expected 배열은 heights 배열을 복사한 것이므로 추가적인 O(n) 공간을 사용합니다.
• 기타 변수 : O(1)
  • wrong과 i와 같은 추가적인 변수는 상수 공간을 사용합니다.

따라서 전체 공간 복잡도는 O(n)입니다.

---

내 코드 Runtime 결과