[99클럽 코테 스터디] 30일차 TIL - Arranging Coins

Hoxy?·2024년 8월 20일

99클럽 TIL 개발자취업 코딩테스트준비 항해99

99클럽 코테 스터디

목록 보기

30/42

오늘의 학습 키워드

</> 이분탐색

공부한 내용 본인의 언어로 정리하기

class Solution {
    public int arrangeCoins(int n) {
        long low = 1; 
        long high = n; 

        while(low <= high){
            long mid = low + (high - low) / 2; 
            long sum = mid * (mid + 1) / 2; 
            
            if(sum > n){ 
                high = mid - 1; 
            } else {
                low = mid + 1; 
            }
        }
       
        return (int)high;
    }
}

오늘의 회고

오늘 주제도 이분탐색이므로 어제 공부한 이분탐색을 이용해서 문제를 풀어보았다. 차이점은 반환값에 low가 아닌 high가 사용된 것과 주어진 값이 배열이었던 것과 다르게 정수n으로 주어졌다.

오늘 low가 아닌 high를 이용한 이유와 탐색의 조건이 sum > n인 이유는 아래에서 설명하겠다.

시작은 모든 값을 int로 사용해서 작성했었지만 코드 제출후 테스트과정에서 큰 값이 나와 실패된 후 모든 값을 long으로 변경하고 제출해야할 값만 int로 형변환을 해주었다.

long low = 1;
long high = n;

low는 탐색의 시작점으로 최소 계단의 수는 1개 이므로 1로 초기화를 해주었고 high는 탐색의 상한선으로 계단이라는 정의에는 맞지않지만 1개씩 쌓아서 계단을 만든다고 가정했을때 탐색할 수 있는 최대의 값이 주어진 동전의 값이므로 n으로 저장을 해주었다.

이후는 이분탐색의 공식에 맞게 작성하였다. low가 high보다 작거나 같을때 까지만 반복 탐색을 해주도록 하고 오늘의 mid값은 중간 값이기도 하지만 주어진 동전을 이용해서 만들 수 있는 잠재적인 최대 계단의 수를 나타내고sum은 그 최대 계단의 수에 필요한 최대 동전의 개수를 가리킨다.

while(low <= high){
	long mid = low + (high - low) / 2;
    long sum = mid * (mid+1) / 2;
}

이후 이분탐색으로 범위를 점점 좁혀나가며 값을 찾아나가면 된다. 하지만 오늘은 동전으로 만들 수 있는 최대 계단의 수를 찾아야 하므로 최대의 계단을 만드는데 필요한 동전의 수와 주어진 동전의 수를 비교해서 탐색을 하였다. 만약 동전의 수가 부족해서 만드는게 불가능하다면 이전 계단을 탐색하고 동전의 수가 많아서 가능하다면 다음 계단을 탐색하였다.

그렇게 되면 high는 탐색된 범위 내에서 주어진 n개의 동전으로 완전히 채울 수 있는 최대 계단의 수가 되며 low는 탐색된 범위 내에서 다음 계단을 만드는 것을 시도할 수 있는 위치, 즉 이 위치는 아직 검증되지 않은 상태로, 실제로는 n개의 동전으로 채울 수 없는 최초의 계단의 순서가 되는 것이다.

결론적으로 high는 완성할 수 있는 계단의 수, low는 완성할 수 없는 최초의 계단의 순서가 된다.

if(sum > n){
	high = mid - 1;
} else {
	low = mid + 1;
}

최종적으로 우리는 완성할 수 있는 계단의 수를 구해야 하므로 high를 반환해준다. 여기서 우리는 앞서 모든 값들을 long으로 생성해왔지만 반환은 int로 반환을 해야하므로 형변환을 해준다.

return (int)high;

아직 이분탐색의 원리를 100% 깨닿지 못했지만 문제를 풀고 공부를 하면서 점점 원리를 체감하며 깨달아가는 중이다. 문제를 많이 풀어야 코테가 수월해진다는 말이 확실히 체감이 되는 것 같다. 스터디가 얼마 남지 않았지만 종료 후에도 꾸준히 해야겠다는 의지가 점점 다져지는 것 같다.

AI 코드리뷰

현재 코드의 장점

이진 탐색 사용: 이진 탐색을 사용하여 O(log n) 시간 복잡도로 문제를 해결하고 있습니다. 이는 매우 효율적인 접근 방법입니다.
정확한 결과: 수학적인 계산을 정확하게 수행하며, 이진 탐색의 조건을 잘 설정하여 올바른 결과를 제공합니다.

현재 코드의 단점

변수 타입: long 타입을 사용하여 계산하고 int로 캐스팅하여 반환합니다. 이 문제에서 int로도 충분하지만, long 타입을 사용하는 이유가 필요하지 않을 수 있습니다.
계산의 안전성: 이진 탐색의 로직은 잘 작성되었지만, low와 high 값이 int 범위를 초과하는 경우를 고려하지 않았습니다.

시간 복잡도

O(log n) : 이진 탐색을 사용하기 때문에, 이 방법의 시간 복잡도는 O(log n)입니다.

개선할 점

불필요한 타입 변환 제거: low, high, mid를 int로 처리하여 코드의 간결성을 높일 수 있습니다.
불필요한 타입 변환 제거: long 타입의 계산을 int로 변경하여 코드를 간결하게 만들 수 있습니다.

AI 리뷰에 대한 개인적인 생각

sum의 값이 범위를 초과하는 경우가 있었기 때문에 long을 사용하여 오류를 최소화 시키기 위해 통일해주었다.

개선된 코드 리뷰

class Solution {
    public int arrangeCoins(int n) {
        int low = 1; 
        int high = n; 

        while (low <= high) {
            int mid = low + (high - low) / 2; 
            long sum = (long)mid * (mid + 1) / 2; 
            
            if (sum > n) { 
                high = mid - 1; 
            } else {
                low = mid + 1; 
            }
        }
       
        return high;
    }
}

개선된 버전의 장점