Portfolio

문제

Given an integer n, return all the numbers in the range [1, n] sorted in lexicographical order.

You must write an algorithm that runs in O(n) time and uses O(1) extra space.

Example 1:


Input: n = 13
Output: [1,10,11,12,13,2,3,4,5,6,7,8,9]

Example 2:


Input: n = 2
Output: [1,2]

Constraints:

1 <= n <= 5 * 104

풀이

효성

아니 문제가 너무 쉽네여.. ㄷㄷ 이럴 수가..


/**
 * @param {number} n
 * @return {number[]}
 */
var lexicalOrder = function(n) {
    return Array(n).fill(0).map((n, i) => i + 1).sort();
}

으아닛 이렇게 푸는 거였군요


/**
 * @param {number} n
 * @return {number[]}
 */
var lexicalOrder = function(n) {
    const result = [];

    const pushFromTo = (start, end) => {
        while(start <= end && start <= n) {
            result.push(start);
            pushFromTo(start * 10, start * 10 + 9);
            start += 1;
        }
    }

    pushFromTo(1, 9);

    return result;
}

재영

시간복잡도가 O(N), 여분의 공간복잡도가 O(1)여야 한다.

반복문으로 해결하는 게 맞는 것 같다. 재귀 역시 공간복잡도를 많이 차지하기 때문이다.

10으로 최대로 곱할 수 있을 때까지 곱한다.

이후 1씩 더하면서 푸시를 하며, 10을 다 채우면 모든 연산을 수행했으므로 10으로 나눈다.

이를 반복하면서 주어진 길이를 채우면 끝이다.

재귀로 푸는 것이 정말 편하다는 것을 느꼈던 문제다.


// extra space O(1)
// 이 문제의 point - 공간복잡도를 최대한 줄여야겠다!
// 재귀함수 - 가장 직관적이라서.
// 재귀 - 스택이 쌓인다. O(N) 13000
// -> 반복문을 써야겠다...? 어떻게???????? - 답을 봤읍니다. 3시간 고민하다가...
// 시간복잡도 - O(N) / 공간복잡도 - O(N) -(순수 O(N))
const getSortedArray = (n) => {
  const res = [1]; // 반환할 결과값.

  while (res.length < n) { // n만큼 채울 때까지.
    let now = res.at(-1) * 10; // ES13 -1번째 인덱스 n = 999 1000

    while (now > n) {
      now = Math.floor(now / 10); // 100

      now += 1; // 110

      while (now % 10 === 0) {
        now = Math.floor(now / 10);
      }
    }

    res.push(now);
  }

  return res;
};

const lexicalOrder = (n) => {
  return getSortedArray(n);
};

console.log(lexicalOrder(13));

Lexicographical Numbers

문제

풀이