[LeetCode 12] Integer to Roman - 탐욕법(Greedy) 활용한 숫자 변환

[LeetCode] Integer to Roman - 탐욕법(Greedy) 활용한 숫자 변환

📌 문제 설명

LeetCode의 "Integer to Roman" 문제는 주어진 정수를 로마 숫자로 변환하는 문제입니다.

• 입력: 정수 num
• 출력: 해당 정수를 로마 숫자로 변환한 문자열

🔹 로마 숫자 기본 규칙

숫자 로마 숫자

1	I
5	V
10	X
50	L
100	C
500	D
1000	M

✅ 일반적인 로마 숫자는 큰 값부터 작은 값 순서로 표현됩니다.
예) 58 → LVIII (50 + 5 + 3)

🔹 예외 규칙 (뺄셈 적용)

숫자 로마 숫자 설명

4	IV	I는 V 앞에서 4 의미
9	IX	I는 X 앞에서 9 의미
40	XL	X는 L 앞에서 40 의미
90	XC	X는 C 앞에서 90 의미
400	CD	C는 D 앞에서 400 의미
900	CM	C는 M 앞에서 900 의미

✅ 특정 숫자(4, 9, 40, 90, 400, 900)는 작은 숫자가 큰 숫자 앞에 와서 뺄셈 역할을 합니다.

---

📌 해결 방법 (탐욕법 - Greedy Algorithm)

💡 핵심 아이디어

1. 큰 숫자부터 차례대로 변환해야 하므로 탐욕법(Greedy Algorithm) 활용
2. 큰 숫자부터 하나씩 확인하며 num에서 해당 값을 빼면서 로마 숫자 추가
3. 숫자가 0이 될 때까지 반복

✅ 코드 구현 (O(N) 복잡도)

export function intToRoman(num: number): string {
  // 1️⃣ 큰 값부터 매칭할 수 있도록 배열을 생성
  const romanMap: [number, string][] = [
    [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"],
  ];

  let result = "";

  // 2️⃣ 큰 값부터 순회하면서 숫자를 변환
  for (const [value, symbol] of romanMap) {
    while (num >= value) {
      result += symbol; // 3️⃣ 해당 로마 숫자를 추가
      num -= value; // 4️⃣ 숫자를 감소
    }
  }

  return result;
}

---

📌 예제 실행 과정

입력: num = 1994

1. 1994 >= 1000 → M 추가 → num = 994
2. 994 >= 900 → CM 추가 → num = 94
3. 94 >= 90 → XC 추가 → num = 4
4. 4 >= 4 → IV 추가 → num = 0

✅ 출력: "MCMXCIV"

---

📌 테스트 코드

describe("Integer to Roman", () => {
  it("converts numbers correctly", () => {
    expect(intToRoman(3)).toEqual("III");
    expect(intToRoman(58)).toEqual("LVIII");
    expect(intToRoman(1994)).toEqual("MCMXCIV");
  });
});

✅ 모든 테스트 케이스 통과! 🚀

---

📌 시간 복잡도 분석

연산 복잡도 설명

탐욕법 (Greedy Algorithm)

O(N)

숫자가 0이 될 때까지 최대 13번 반복

✅ 탐욕법을 활용하면 O(N)으로 최적화 가능! 🚀

---

📌 최종 정리

1. 큰 숫자부터 차례대로 로마 숫자로 변환해야 함 → 탐욕법 사용
2. 큰 값부터 매칭하는 배열을 만들고, 현재 숫자가 크면 반복해서 뺀다.
3. O(N) 시간 복잡도로 효율적으로 해결 가능!

💡 이제 유사한 문제에서도 "큰 값부터 탐욕적으로 처리하는 방식"을 고려해 보세요! 🚀

 

#LeetCode #IntegerToRoman #알고리즘 #TypeScript #탐욕법