[LeetCode/C#] 374. Guess Number Higher or Lower

 

문제링크 

374. Guess Number Higher or Lower

 

https://leetcode.com/problems/guess-number-higher-or-lower/description/

 

 

기억하면 좋을 것 

1. 중간값을 구할때 var mid = left - (right - left) / 2 를 하면 오버플로우를 피할 수 있다. 

물론 중간값을 left + right / 2 로 구할 수 있다. 그러나 컴퓨터가 32비트 정수를 사용한다면 표현할 수 있는 가장 큰 수는 2^32 로 left + right 했을 때 그 값을 초과할 수 있기때문에 중간값을 구할때 저 식을 많이 쓴다고한다. 

 

2. 32비트 정수에서 첫번째 비트는 부호비트. 나머지 31비트는 수를 표현하는데 사용된다. 따라서 부호있는 (signed integer ) 의 최댓값은 2^31 이다. 

 

3. 재귀함수를 호출할 때마다 컴퓨터의 메모리에는 스택 프레임이라는 것이 생성된다. 이 스택 프레임은 함수의 매개변수, 지역변수, 반환주소 등 함수의 실행에 필요한 정보를 저장한다. 이렇게 생성된 스택 프레임은 함수가 종료될 때까지 메모리에 남아있다. 재귀함수는 자신을 계속 호출하기때문에 호출 횟수만큼 스택 프레임이 계속 쌓인다. 이렇게 스택 프레임이 계속 쌓이는 것이 바로 함수 호출 스택에 대한 오버헤드 를 의미한다. 즉, 재귀함수의 호출 횟수가 많아질수록 메모리 사용량이 증가한다. While 문 같은 반복문을 사용했을시 함수를 호출하지않고 코드 블록을 반복실행하기 때문에 이런 오버헤드를 피할 수 있다. 

 

스택은 컴퓨터 메모리의 스택 영역에 생성되는 공간을 말한다. 스택 프레임은 다음과 같은 구성 요소를 가진다. 

a) 매개변수

b) 반환주소

c) 지역변수 

함수가 호출되면 먼저 매개변수가 스택에 쌓이고, 그 다음 반환주소가 스택에 쌓인다. 그 후 함수의 지역변수가 스택에 할당된다. 

이렇게 스택에 차례대로 저장되는 함수의 호출 정보를 스택 프레임이라고 한다. 

 

함수가 종료되면 스택 프레임은 소멸되고 스택에서 매개변수와 지역 변수가 제거된다. 그리고 반환 주소를 사용해 함수 호출 이전의 코드 위치로 돌아간다. 

이렇게 스택 프레임을 사용하면, 각 함수의 호출이 독립적인 메모리 공간을 가질 수 있기때문에 함수간 데이터가 서로 간섭하지 않도록 할 수 있다. 

 

소감

mid = left + (right - left)/2 로 오버플로우를 피할 수 있는 중간값 구하기를 배울 수 있어 좋았다. 

잊지말자.. 그리고 함수를 호출하면 스택 프레임이 생성된다 ~ !

 

해결 코드

 

/** 
 * Forward declaration of guess API.
 * @param  num   your guess
 * @return 	     -1 if num is higher than the picked number
 *			      1 if num is lower than the picked number
 *               otherwise return 0
 * int guess(int num);
 */

public class Solution : GuessGame {
    public int GuessNumber(int n)
{
    var l = 1;
    var r = n;

    while (l <= r)
    {
        var m = l + (r - l) / 2;

        var g = guess(m);

        if (g == -1 || g == 0)
        {
            r = m - 1;
        }
        else
        {
            l = m + 1;
        }
    }

    return l;
}
}

 

 

이진탐색 문제다. pick 값이 mid 보다 클 경우 left = mid + 1 로 설정해 mid+1 ~ n 까지를 탐색한다. 

pick 값이 mid 보다 작을 경우 right = mid - 1 로 설정해 1 ~ mid-1 까지를 탐색한다. 

 

Submission Detail