백준 1038번 감소하는 수 :: 마이구미

이번 글은 백준 알고리즘 1038번 문제 "감소하는 수" 를 다뤄본다.

문제는 동적계획법으로 접근해야한다.

음이 아닌 정수 X의 자릿수가 가장 큰 자릿수부터 작은 자릿수까지 감소한다면, 그 수를 감소하는 수라고 한다. 예를 들어, 321과 950은 감소하는 수지만, 322와 958은 아니다. N번째 감소하는 수를 출력하는 프로그램을 작성하시오. 0은 0번째 감소하는 수이고, 1은 1번째 감소하는 수이다. 만약 N번째 감소하는 수가 없다면 -1을 출력한다.

하지만 본인은 도저히 동적계획법으로는 생각나지 않아, 브루트 포스(노가다)로 풀었다.

완전한 노가다는 아니라, 불필요한 과정을 제외시킴으로써, 시간 제한을 피할 수 있었다.

테스트케이스가 많은 것도 아니고, 노가다로 풀어도 충분히 시간 제한에 걸리지 않을 거라 판단했다. (핑계)

어떤 방법으로 풀더라도 문제는 풀면 되는 것이다 (핑계)

단순히 노가다로 풀릴 거라는 것을 캐치하는 것도 중요하지 않는가? (핑계)

문제는 간단하다.

본인의 접근 방법은 N번째 감소하는 수를 찾으면 되기 때문에, 0부터 감소하는 수가 맞는지 아닌지 판단했다.

감소하는 수인지 판단하기 위해 일의 자리부터 한자리씩 비교한다.

감소하는 수가 맞다면 비교한 수를 1 증가시켜 다음 수를 감소하는 수인지 판단한다.

감소하는 수가 아니라면 불필요한 수들은 생략한 후 다음 수를 감소하는 수인지 판단한다.

단순히 감소하는 수를 검사하는 코드는 아래와 같다.

한자리씩 비교할 때 쓰는 많이 쓰는 방식인, 나머지와 나눗셈 연산을 통해 구현할 수 있다.

// num - 검사하는 수, before - 한자리씩 비교할 때의 이전 수

while (num != 0) {
    if (num % 10 <= before) {
        break;
    }

    before = num % 10;
    num /= 10;
}

위와 같은 방법으로 모든 숫자를 검사하는 방법은 너무나 많은 시간이 걸리기 때문에 비효율적이다.

본인의 풀이에서 중요한 점은, 불필요한 수들을 건너띄었다는 것이다.

예를 들어, 11부터 19까지는 검사를 할 필요가 없다.

이러한 수들을 건너띄어 시간을 절약할 수 있었다.

그 방법으로는 jump라는 변수 하나를 이용했다.

while (num != 0) {
    if (num % 10 <= before) {
        break;
    }

    jump *= 10;
    before = num % 10;
    num /= 10;
}

jump 변수는 어떤 자릿수에서 감소하는 수가 아닌지 체크하는 목적으로 이용된다.

예를 들어, 수가 3110 백의 자리 때문에 감소하는 수가 아니다.

그렇기에 100을 더해줌으로써, 불필요한 검사를 건너띄어 3110 -> 3210 수로 변경한다.

이러한 과정을 jump 변수를 통해 해주게 된다.

위 방법으로도 불필요한 수들을 생략할 수 있지만, 위의 코드는 그다지 효율적이지는 않다.

예를 들어, 9875000 -> 9875010 -> 9875100 -> 9875110 이런 식으로 확실하게 건너띄지 못한다.

이러한 불필요한 수들을 효율적으로 생략할 수 있게 구현하는 방법은 다양하다.

// 일의자리부터 한자리씩 비교
while (num != 0) {

    if (num % 10 <= before) {
        isDsc = false;
    }

    // jump를 최대치로 늘리기 위함.
    if (!isDsc && num % 10 > before) {
        break;
    }

    // jump는 어떤 자릿수에서 감소하는 수가 아닌지를 식별한다.
    jump *= 10;
    before = num % 10;
    num /= 10;
}

감소하는 수가 아니면 바로 반복문을 중단시키지 않고, 감소하는 수가 아닌 경우의 자리가 어디까지 올라갈 수 있는 지 돌리는 방식이다.

확실히 이전보다 효율적이지만, 충분히 더 효율적이게 구현할 수도 있다.

아래 Github URL을 통해 전체 소스를 참고하길 바란다.

백준 알고리즘 1038번 "감소하는 수" 전체 소스

https://github.com/hotehrud/acmicpc/blob/master/algorithm/Brute-Force/1038.java