[코딩연습] Arranging Coins 동전 배열하기

LeetCode 문제 중 난이도 Easy인 Arranging Coins 이다. 문제링크는 포스팅의 맨 마지막에 추가하였다. 언어는 Java를 사용했다.

  문제해석

총 n개의 동전을 가지고 k번째 줄에는 k개의 동전이 오도록 계단모양으로 배열해보자.

주어진 n으로 만들 수 있는 온전한 계단의 최대 라인수를 찾아라.

n은 음수가 아닌 정수로 부호가 있는 32비트 정수의 범위내에 있다.

k번째까지 계단모양을 채우려면 동전의 갯수가 1+2+3+...+k개 필요하다. 1부터 k까지의 숫자의 합은 k(k+1)/2이다. 그러면 n≥k(k+1)/2을 만족하는 k를 찾아야 한다. 중학생 때 배운 완전제곱식을 이용하여 k에 관한 형태로 바꾸어준다.

결과적으로 k는 2n+0.25의 제곱근에서 0.5를 뺀 값보다 작거나 같을 것이다. 구하려는 값은 해당 부등식을 만족하는 자연수 k의 최댓값이므로 좌변의 식에서 소수점을 버림하면 자연수 k의 최댓값을 구할 수 있다. 입력값 n은 정수만 담을 수 있는 int 자료형이므로 소수점 계산을 하기 위해 double 자료형을 이용한다. 코드로 작성하면 다음과 같다.

class Solution {
    public int arrangeCoins(int n) {
        
        if(n<2) return n;
        
        double result = (Math.sqrt(2*n+0.25))-0.5;
        return (int)result;
    }
}

double 자료형이 익숙하지 않다면 삐멜소프트웨어 엔지니어 - 자바 변수와 자료형(float,double) 포스트를 참고하자.

잘 돌아갈 것 같지만 문제가 하나 있다. 문제에서 n은 32-bit signed integer라고 하였다. 이게 무슨 말이냐 하면 32비트 중 가장 첫번째 비트는 부호비트로 쓰인다는 것이다. 32-bit signed integer로 나타낼 수 있는 범위는 -2,147,483,648 ~ 2,147,483,647이다. 삐멜소프트웨어 엔지니어 - 자바 변수와 자료형(byte,short,int,long)

input으로 받는 n에 2를 곱한 값이 2^31 이상이면 맨앞의 sign bit가 1이 되어 음수로 바뀐다. 이 문제를 해결하기 위해 long자료형을 이용하자. 아래는 이해를 돕기 위한 코드고 실제로 사용할 때에는 L만 붙여주면 자동으로 long자료형으로 바뀐다.

class Solution {
    public int arrangeCoins(int n) {
        
        if(n<2) return n;
        long twoN = 2*(long)n;
        
        double result = (double)(Math.sqrt(twoN+0.25))-0.5;
        return (int)result;
    }
    
}

문제 해결 완료!

class Solution {
    public int arrangeCoins(int n) {
        
        if(n<2) return n;
        
        double result = (double)(Math.sqrt(2L*n+0.25))-0.5;
        return (int)result;
    }
}

시간복잡도는 O(1), 공간복잡도는 O(1)이다.

문제출처 - https://leetcode.com/problems/arranging-coins/