[C#] 숫자 게임

프로그래머스 문제

https://school.programmers.co.kr/learn/courses/30/lessons/12987

풀이 후기

1. 분석

지니어스의 ＇흑과 백＇ (https://namu.wiki/w/흑과%20백)이 생각나는 문제. N보다 큰 무언가를 찾는 문제이기 때문에 Upper Bound가 생각이 났고, 연습하고 싶어서 그걸로 풀었다.

무언가를 효율적으로 찾는 것은 대충 이중탐색을 찍으면 반은 맞는 느낌?? 이다. Lower Bound와 Upper Bound는 이중탐색이 변형된 알고리즘인데, 이중탐색은 못 찾으면 -1 리턴하고 도망가지만, 저 둘은 start가 end를 넘을 때까지 계속 돌아간다.

사실 Lower와 Upper의 차이점은 부등호밖에 없다.

1. Lower는 N 이상을 찾는다. (mid가 N보다 작으면 start + 1),

   if(arr[start] < N)
   {
   	start = mid + 1;
   }

2. Upper는 N 초과를 찾는다. (mid가 N보다 작거나 같으면 start + 1)

   if(arr[start] <= N)
   {
   	start = mid + 1;
   }

그리고 이렇게 나온 index가 그냥 범위 터져서 뱉은 값일 수도 있으니, 마지막으로 비교하고 계산하면 끝이다.

2. 다른 방법

A의 출전 순서가 있긴 있는데, 생각해보면 대전 순서를 배열로 뱉는 것도 아니고 결과만 찾는 문제다. 그렇기에 A 순서를 바꿔서 계산하더라도(대충 내가 보기 편하게 바꾼 거고 나중에 다시 되돌릴게 ㅇㅇ 같은 느낌임) 딱히 문제 되는 건 없다. 배열 2개를 정렬하고 index 움직이면서 계산하면 대충 정답이 나올듯?

3. 실행 결과

4. 코드

using System;
using System.Linq;
using System.Collections.Generic;

public class Solution {
    public int FindMin(List<int> list, int n){
        var start = 0;
        var end = list.Count - 1;
        var mid = 0;
        
        while(start < end){
            mid = start + (end - start) / 2;
            
            if(list[mid] <= n){
                start = mid + 1;
            }
            else{
                end = mid;
            }
        }
        
        return end;
    }
    
    public int solution(int[] A, int[] B) {
        int answer = 0;
        var list = new List<int>();
        
        for(int i = 0; i < B.Length; i++){
            list.Add(B[i]);
        }
        list.Sort();
        
        for(int i = 0; i < A.Length; i++){
            var result = FindMin(list, A[i]);
            
            if(A[i] < list[result]){
                list.RemoveAt(result);
                answer++;
            }
        }
        
        return answer;
    }
}

mid를 저렇게 구한 이유는 정수형 범위 넘어가서 터지는 경우 방지용.

원래 배열에 -1를 넣어서 삭제 연산을 줄이려고 했으나, 그건 그것대로 복잡한 문제여서 단순하게 리스트를 써 봤는데 다행히 통과했다.