[BOJ 1038] 감소하는 수

문제

감소하는 수

https://www.acmicpc.net/problem/1038

 

 

풀이

설명

N번째 감소하는 수를 구하는 문제입니다.

 

감소하는 수는 오른쪽 숫자가 왼쪽 숫자보다 작아야 합니다.

 

과정은 다음과 같습니다.

1. 10보다 작으면 바로 반환합니다.
2. 1부터 9까지의 숫자를 큐에 넣고 시작합니다.
3. 큐에서 숫자를 하나씩 꺼냅니다.
   1. 마지막 자릿수보다 작은 숫자를 뒤에 붙여 새로운 감소하는 수를 생성
   2. 각 새로운 수를 큐에 추가하고 카운트 증가
   3. N번째 수에 도달하면 바로 반환
4. 모든 가능한 감소하는 수를 생성했는데도 N번째 수에 도달하지 못하면 -1을 반환합니다.

 

예시 코드

function solution() {
  const N = Number(input());

  if (N < 10) return N;

  const queue = new Queue();
  for (let i = 1; i <= 9; i++) {
    queue.enqueue(i);
  }

  let cnt = 9;

  while (!queue.isEmpty()) {
    const num = queue.dequeue();
    const lastDigit = num % 10;

    for (let i = 0; i < lastDigit; i++) {
      const newNum = num * 10 + i;
      queue.enqueue(newNum);
      cnt++;

      if (cnt === N) return newNum;
    }
  }

  return -1;
}