[99클럽 코테 스터디] 30일차 TIL 이분탐색

 

 

오늘의 문제는 LeetCode

 

441. Arranging Coins

 

 

문제

 

 

 

문제 설명 

정수 n이 주어집니다. n개의 동전으로 계단을 만들려고 할 때 계단은 i번째 행의 i개의 동전이 있는 k개의 행으로 구성됩니다. 

계단의 마지막 행이 불완전 할 수 있다고 할 때 완전하게 지을 수 있는 계단 행의 수를 구하는 문제입니다. 

 

예를 들어 n이 5라면 위 그림에서 확인할 수 있듯이 동전으로 완전하게 만들 수 있는 계단 행의 수는 2 이므로 2를 반환하면 됩니다. 

 

 

 

문제 풀이 시간 

권장 풀이 시간은 60분이었고, 저는 18분이 걸렸습니다.

 

 

 

문제 접근 방식

계단의 높이만큼 필요한 동전의 개수를 빼는 방식을 통해 문제를 해결했습니다. 먼저 계단의 개수를 나타내는 변수 cnt와 각 계단에 필요한 동전의 개수를 나타내는 변수 i를 선언합니다. 

그 다음 반복문을 사용해 n이 현재 계단을 만들 수 있는지 조건을 통해 확인하고 n에서 i만큼의 동전을 빼고 i를 증가시킵니다. 위 과정을 반복하다가 n이 i 보다 작아서 계단을 더 이상 만들 수 없게 되면 만들어진 계단의 개수를 반환합니다. 

 

 

 

문제 풀이

class Solution {
    public int arrangeCoins(int n) {
        
        int cnt = 0;
        int i = 1;

        while (n >= i) {
            n -= i;
            i++;
            cnt++;
        }
        return cnt;
    }
}

 

 

코드 개선하기 

계단의 개수를 나타내는 변수를 선언하는 대신 반복문 안에서 i를 활용하는 방식으로 변경하면 코드를 더 효율적으로 개선할 수 있습니다. 

 

예를 들어 n이 5인 경우 아래와 같이 동작합니다. 

i	n
1	5 - 1 = 4
2	4 - 2 = 2
3	2 - 3 = -1

마지막 세 번째 계단을 만드는 경우 n이 음수가 되기 때문에 더 이상 계단을 만들 수 없는데도 불구하고 i가 3으로 증가된 상태이기 때문에 i - 1 을 반환해줍니다. 

class Solution {
    public int arrangeCoins(int n) {
        
        int i=1;
        
        while(n>0){
            i++;
            n-=i;
        }
        return i-1;
    }
}

 

 

 

 

 

 

 

 

 

이렇게 오늘 30일차 TIL을 작성해 보았습니다.