[Programmers] 입문) 머쓱이보다 키 큰 사람

 

위 문제를 읽자마자 떠오른 것이 2개 있다.

 

1. 배열 정렬

2. 바이너리 서치

 

우선 배열을 정렬해야 문제 해결이 가능하다고 생각했다.

그렇지 않고서야 모든 원소를 하나하나 살펴가며 카운트하는 시간낭비가 일어나기 때문이다.

 

두 번째로는 바이러니 서치가 필요하다 느꼈다.

 

우선 가장 기본적인 순차 탐색으로 코드를 짜보았다.

using System;

public class Solution {
    public int solution(int[] array, int height) {
        int answer = 0;
        
        Array.Sort(array);
        
        for (int k = array.Length - 1; k > 0; k--){
            if (array[k] < height) break;
            answer++;
        }
        
        return answer;
    }
}

 

다음은 이진트리 탐색을 통해 답을 구해보았다.

using System;
using System.Linq;

public class Solution {
    public int solution(int[] array, int height) {
        int answer = 0;
        
        Array.Sort(array);
        //array = array.Distinct().ToArray();
        
        if (height < array[0]) return array.Length;
        if (height > array[array.Length - 1]) return 0;
        
        int position = array.Length / 2;
        for (int k = 0; k < array.Length / 2; k++){
            if(array[position] > height){
                if(array[position - 1] <= height) {
                    answer = array.Length - position;
                    break;
                }
                position = position / 2;
            }
            else if(array[position] < height){
                position = array.Length - ((array.Length - position) / 2);
            }
        }
        
        return answer;
    }
}

 

확실히 두 방법을 비교하였을때 확실히 테스트 개수가 많지 않은 경우 반복문이 더 빠른 결과가 나왔다.

하지만 데이터 양이 비대해질 경우 이진탐색이 훨씬 용의할 것으로 생각한다.