12. Integer to Roman

LeetCode 12번 풀이

이 글은 Obsidian에서 마이그레이션되었으며, 그 과정에서 AI의 도움을 받았습니다. 오류나 누락된 내용이 있다면 댓글로 알려주세요!

문제

Integer to Roman - LeetCode

풀이 1

아이디어

항상 현재 수보다 크지 않은 로마 숫자 값을 빼가며 기호를 이어 붙이는 방식 (Greedy)

코드

function intToRoman(num: number): string {
  const symbolTable = new Map([
    [1000, "M"],
    [900, "CM"],
    [500, "D"],
    [400, "CD"],
    [100, "C"],
    [90, "XC"],
    [50, "L"],
    [40, "XL"],
    [10, "X"],
    [9, "IX"],
    [5, "V"],
    [4, "IV"],
    [1, "I"],
  ]);

  const valueIter = symbolTable.keys();
  let answer: string[] = [];
  let currValue = valueIter.next().value;

  while (num > 0) {
    while (currValue > num) {
      currValue = valueIter.next().value;
    }
    const currSymbol = symbolTable.get(currValue)!;
    answer.push(currSymbol);
    num -= currValue;
  }

  return answer.join("");
}

시간 / 공간 복잡도

• 시간 복잡도: O(1)
• 공간 복잡도: O(1) (결과 생성을 위한 배열은 제외함)

풀이 2

아이디어

Map 말고 다른 자료구조를 생각하지 못해서 숫자를 순회하기 위해서 iterator를 썼는데, 다 풀고 생각해보니 iterator는 가독성 측면에서 썩 좋지 않은 것 같다. 여기서는 탐색 구간이 겹치는 부분이 없기 때문에 배열 기반으로 했어도 괜찮았을 것 같음

코드

function intToRoman(num: number): string {
    const symbols = ["M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"];
    const values = [1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1];

    let answer: string[] = [];

    for (let idx = 0; idx < values.length; idx++) {
        const value = values[idx];
        const cnt = Math.floor(num / value);
        if (cnt <= 0) continue;
        const symbol = symbols[idx];
        answer.push(symbol.repeat(cnt));
        num %= value;
    }

    return answer.join('');
};