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

📌 문제 설명

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

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

🔹 로마 숫자 기본 규칙

숫자 로마 숫자

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

🔹 예외 규칙 (뺄셈 적용)

숫자 로마 숫자 설명

✅ 특정 숫자(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");
  });
});

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

📌 시간 복잡도 분석

연산 복잡도 설명

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

📌 최종 정리

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

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

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

[LeetCode] Trapping Rain Water - 효율적인 해결 방법 (Two Pointers)

📌 문제 설명

LeetCode의 "Trapping Rain Water" 문제는 높이 배열(height[])이 주어질 때, 빗물이 고일 수 있는 총량을 계산하는 문제입니다.

• height[i]: 각 기둥의 높이
• 각 기둥의 너비는 1로 고정
• 빗물이 얼마나 고일 수 있는지 계산해야 함

📌 문제 해결 과정

✅ 잘못된 접근 (Brute Force, O(N²))

모든 인덱스에서 왼쪽 최대(leftMax)와 오른쪽 최대(rightMax) 를 찾아 빗물을 계산하는 방법이 떠오를 수 있습니다.

export function trap(height: number[]): number {
  let water = 0;

  for (let i = 1; i < height.length - 1; i++) {
    const leftMax = Math.max(...height.slice(0, i + 1));
    const rightMax = Math.max(...height.slice(i));

    water += Math.max(0, Math.min(leftMax, rightMax) - height[i]);
  }

  return water;
}

🚨 문제점:

• Math.max(...arr)를 반복 호출해야 하므로 시간 복잡도 O(N²) 발생
• 배열이 길어질수록 매우 비효율적

📌 최적화된 해결 방법 (Two Pointers, O(N))

💡 핵심 아이디어: "양쪽에서 중앙으로 이동하며 작은 쪽을 기준으로 계산"

1. leftMax와 rightMax를 유지하면서 한 번의 순회로 해결
2. 작은 쪽(leftMax 또는 rightMax)을 기준으로 물을 계산
3. 양쪽 끝에서 중앙으로 이동하면서 빗물을 계산 (O(N))

✅ 작은 쪽을 기준으로 계산하는 이유:

• leftMax < rightMax라면 leftMax보다 높은 곳이 나오기 전까지 leftMax가 현재 위치에서 최대 물 저장 가능 높이
• 반대로 rightMax < leftMax라면 rightMax가 현재 위치에서 최대 물 저장 가능 높이

📌 최적화된 코드 (O(N))

export function trap(height: number[]): number {
  let left = 0, right = height.length - 1;
  let leftMax = 0, rightMax = 0;
  let water = 0;

  while (left < right) {
    if (height[left] < height[right]) {
      leftMax = Math.max(leftMax, height[left]);
      water += leftMax - height[left];
      left++;
    } else {
      rightMax = Math.max(rightMax, height[right]);
      water += rightMax - height[right];
      right--;
    }
  }

  return water;
}

📌 예제 분석

입력:

height = [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1];

Step-by-step 실행 과정

left right leftMax rightMax water 설명

✅ 최종 결과: 6 (가둘 수 있는 물의 양)

📌 시간 복잡도 분석

접근법 시간 복잡도 설명

✅ Two Pointers 사용하면 O(N)으로 해결 가능! 🚀

📌 최종 정리

1. 각 위치에서 고일 수 있는 물의 양 = min(leftMax, rightMax) - height[i]
2. 모든 인덱스에서 leftMax와 rightMax를 찾는 것은 O(N²)로 비효율적
3. "양쪽 끝에서 중앙으로 이동하면서 작은 쪽을 기준으로 물을 계산"하면 O(N)으로 해결 가능
4. O(N) 탐욕법(Two Pointers)로 해결 가능!

💡 이제 비슷한 문제에서 "양쪽에서 중앙으로 이동하는 방식"을 떠올려 보세요! 🚀

[LeetCode] Gas Station - 탐욕법(Greedy)으로 해결하기

📌 문제 설명

LeetCode의 "Gas Station" 문제는 각 주유소에서 얻을 수 있는 연료(gas)와 이동에 필요한 연료(cost)가 주어질 때, 전체 주유소를 한 바퀴 돌 수 있는 출발점을 찾는 문제입니다.

• gas[i]: i번째 주유소에서 얻을 수 있는 연료량
• cost[i]: i번째 주유소에서 다음 주유소로 이동하는 데 필요한 연료량
• 한 바퀴를 돌 수 있다면 출발 가능한 주유소의 인덱스 반환, 불가능하면 -1 반환
• 해결 가능한 경우는 유일함이 보장됨

📌 문제 해결 과정

✅ 직관적인 접근 (O(N²) 비효율적 방법)

처음에는 모든 주유소에서 출발을 시도하면서 한 바퀴를 도는 방식을 생각할 수 있습니다.

export function canCompleteCircuit(gas: number[], cost: number[]): number {
  let total = 0;
  const len = gas.length;

  for (let i = 0; i < len; i++) {
    for (let j = 0; j < len; j++) {
      const current = (i + j) % len;
      total += gas[current] - cost[current];
      if (total < 0) {
        total = -1;
        break;
      }
    }
    if (total >= 0) {
      return i;
    }
  }
  return -1;
}

하지만, 이 방식은 모든 주유소에서 출발을 시도하면서 한 바퀴를 도는지 확인하므로 O(N²) 시간이 걸려 비효율적입니다.

📌 최적화된 해결 방법 (탐욕법 - Greedy, O(N))

🚀 핵심 아이디어

1. 총 연료량(sum(gas))이 총 비용량(sum(cost))보다 작으면 절대 불가능 → -1 반환
2. 연료가 부족하면 출발점을 다음 주유소로 변경 (이전 주유소에서는 절대 출발 불가능)
3. 연료가 남아있다면 현재 출발점 유지

📌 코드 (O(N))

export function canCompleteCircuit(gas: number[], cost: number[]): number {
  let totalGas = 0;
  let totalCost = 0;
  let startIndex = 0;
  let currentGas = 0;

  for (let i = 0; i < gas.length; i++) {
    totalGas += gas[i];
    totalCost += cost[i];
    currentGas += gas[i] - cost[i];

    // 연료 부족 시, 출발 지점을 다음 주유소로 변경
    if (currentGas < 0) {
      startIndex = i + 1;
      currentGas = 0; // 새로운 출발점에서 다시 시작
    }
  }

  return totalGas >= totalCost ? startIndex : -1;
}

📌 코드 실행 과정 예제

입력:

gas  = [1, 2, 3, 4, 5]
cost = [3, 4, 5, 1, 2]

Step-by-step 실행 과정

i gas[i] cost[i] currentGas (남은 연료) startIndex (출발점)

✅ 최종 반환값: 3 (index 3에서 출발하면 한 바퀴 가능)

📌 시간 복잡도 분석

접근법 시간 복잡도 설명

✅ 탐욕법을 사용하면 O(N)으로 해결 가능! 🚀

📌 최종 정리

• 총 연료량 < 총 비용량이면 절대 불가능 (-1 반환)
• 연료 부족 시 출발 지점을 다음 주유소로 변경 (O(N) 순회 한 번만 수행)
• 탐욕법(Greedy)으로 최적화하여 O(N)에 해결 가능

💡 이제 비슷한 문제를 만나면 "탐욕법(Greedy) 접근"을 우선 고려해 보세요! 🚀

[LeetCode] Jump Game II - 최소 점프 횟수 찾기 (탐욕법 + DP)

문제 설명

LeetCode의 "Jump Game II" 문제는 배열의 시작점에서 끝점까지 최소한의 점프로 도달하는 문제입니다.

• nums[i]는 i번째 인덱스에서 최대 몇 칸까지 점프할 수 있는지를 나타냅니다.
• nums[0]에서 nums[n-1]까지 도달하는 최소 점프 횟수를 구해야 합니다.
• 항상 도달 가능하다고 가정됩니다.

📌 문제를 풀면서 생각한 과정

처음에는 "모든 경우를 탐색하면서 최소 점프 횟수를 찾는 방법이 있을까?" 라고 고민했습니다.
먼저 동적 계획법(DP) 방식으로 접근했지만 O(N^2)의 시간 복잡도로 인해 비효율적이었습니다.
이후 **탐욕법(Greedy Algorithm)**을 적용하면 O(N)으로 해결할 수 있음을 발견했습니다.

📌 DP (동적 계획법) 풀이 - 초기 접근 방법

✅ 핵심 아이디어

1. 각 인덱스까지 최소 점프 횟수를 저장하는 dp 배열을 사용
2. dp[i]는 인덱스 i에 도달하는 최소 점프 횟수를 의미
3. dp[i] = min(dp[i], dp[j] + 1)
   • j에서 i로 이동할 수 있는 경우 (j + nums[j] >= i)
   • dp[i]는 dp[j] + 1 (즉, j에서 한 번 점프해서 가는 방법이 기존보다 더 작다면 업데이트)

📌 DP 코드

export function jumpDP(nums: number[]): number {
  const dp = new Array(nums.length).fill(Infinity);
  dp[0] = 0; // 시작점은 점프 0번

  for (let i = 0; i < nums.length; i++) {
    for (let j = i + 1; j <= i + nums[i] && j < nums.length; j++) {
      dp[j] = Math.min(dp[j], dp[i] + 1);
    }
  }

  return dp[nums.length - 1]; // 마지막 인덱스까지의 최소 점프 횟수 반환
}

📌 실행 예제 분석

nums = [2,3,1,1,4]

초기 dp 배열:

[0, ∞, ∞, ∞, ∞]

i nums[i] dp 배열 변경

✅ 최소 점프 횟수: dp[4] = 2

📌 DP의 문제점

• 시간 복잡도: O(N^2) (이중 반복문)
• 공간 복잡도: O(N) (dp 배열 사용)
• 비효율적이며, 최적화 필요

📌 탐욕법(Greedy) 풀이 - 최적해 도출 과정

✅ 핵심 아이디어

1. 최대한 멀리 갈 수 있는 곳(farthest)을 계속 갱신한다.
2. 현재 점프 내에서 최대 도달 가능 위치(currentEnd)를 확인한다.
3. 현재 위치가 currentEnd를 넘어서면 점프 횟수를 증가시키고 새로운 currentEnd를 설정한다.
4. 이 과정을 반복하면 최소 점프 횟수로 마지막 위치에 도달할 수 있다.

📌 탐욕법(Greedy) 코드

export function jump(nums: number[]): number {
  let jumps = 0;
  let currentEnd = 0;
  let farthest = 0;

  for (let i = 0; i < nums.length - 1; i++) {
    farthest = Math.max(farthest, i + nums[i]);
    if (i === currentEnd) {
      jumps++;
      currentEnd = farthest;
    }
  }

  return jumps;
}

📌 실행 예제 분석

nums = [2,3,1,1,4]

i nums[i] farthest currentEnd jumps 설명

✅ 최소 점프 횟수: 2

📌 탐욕법 vs DP 비교

방법 시간 복잡도 공간 복잡도 특징

✅ 탐욕법(Greedy)이 최적의 해결법! 🚀

📌 최종 정리

• DP는 직관적이지만, O(N^2) 복잡도로 비효율적
• 탐욕법(Greedy)은 O(N)으로 최적화 가능
• "현재 점프 내에서 가장 멀리 갈 수 있는 곳"을 선택하는 것이 최적의 해
• 추가 배열 없이 O(1) 공간복잡도로 해결 가능

💡 이제 비슷한 문제를 만나면 "탐욕법"을 우선 고려해 보세요! 🚀

LeetCode 13번 | 로마 숫자를 정수로 변환하기 (TypeScript 풀이)

이번 글에서는 LeetCode 13번 문제 "Roman to Integer" 를 TypeScript로 해결하는 방법을 다룹니다.
이 문제는 코딩 테스트나 개발자 면접에서 자주 등장하는 문자열 처리 & 수학적 규칙 적용 유형입니다.

🔹 문제 설명 (Roman to Integer)

로마 숫자는 다음과 같은 기호로 표현됩니다.

• I = 1, V = 5, X = 10, L = 50, C = 100, D = 500, M = 1000
• IV = 4, IX = 9, XL = 40, XC = 90, CD = 400, CM = 900 처럼 작은 값이 앞에 오면 감산됩니다.

주어진 로마 숫자 문자열을 정수로 변환하는 함수를 구현해야 합니다.

🔹 풀이 전략

1. 문자를 숫자로 변환하는 객체 (symbol 맵) 생성
2. 문자열을 순회하면서 현재 값과 이전 값을 비교
   • 이전 값보다 크다면 감산(-2 * prev) 적용
   • 그렇지 않다면 그대로 더하기
3. 최적화를 위해 symbol[c] 조회 최소화

🔹 TypeScript 풀이 코드

export function romanToInt(s: string): number {
  const symbol: Record<string, number> = {
    I: 1, V: 5, X: 10, L: 50, C: 100, D: 500, M: 1000,
  };

  let answer = 0;
  let prev = 0;

  for (const c of s) {
    const value = symbol[c];

    if (prev < value) {
      answer -= prev * 2;
    }
    answer += value;
    prev = value;
  }

  return answer;
}

✅ 시간 복잡도: O(n) (문자열 한 번 순회)
✅ 공간 복잡도: O(1) (고정된 크기의 symbol 맵 사용)

🔹 테스트 케이스

console.log(romanToInt("III")); // 3
console.log(romanToInt("IV")); // 4
console.log(romanToInt("IX")); // 9
console.log(romanToInt("LVIII")); // 58
console.log(romanToInt("MCMXCIV")); // 1994

🔹 결론 및 정리

이 문제는 문자열 순회와 조건 비교를 활용한 최적화가 핵심입니다.
처음에는 단순 덧셈을 고려할 수 있지만, 감산 규칙을 적용하기 위해 이전 값과 비교하는 방식이 필요합니다.
코딩 테스트나 면접에서 자주 등장하는 유형이므로, TypeScript로 직접 구현하면서 연습해보는 것이 중요합니다.

📌 이해가 안 되는 부분이나 더 좋은 풀이가 있다면 댓글로 공유해주세요! 😊

#LeetCode #코딩테스트 #알고리즘 #타입스크립트 #로마숫자 #RomanToInteger #개발자 #프로그래밍 #면접문제

LeetCode Merge Sorted Array 문제 풀이: 초기 코드와 공간 복잡도 개선

이번 포스트에서는 LeetCode의 Merge Sorted Array 문제를 해결한 과정을 소개합니다. 처음에는 제가 작성한 초기 코드 방식으로 문제를 해결한 후, 추가 공간 사용 문제(공간 복잡도)를 개선하여 in-place 방식으로 최적화한 과정을 다룹니다.

문제 개요

Merge Sorted Array 문제는 두 개의 정렬된 배열을 하나의 정렬된 배열로 병합하는 문제입니다.

• 입력:
  • nums1: 크기가 m+n인 배열, 처음 m개의 요소는 유효한 값이며 나머지 n개는 추가 공간입니다.
  • nums2: n개의 요소로 구성된 배열.
• 목표:
  • nums1에 nums2의 요소들을 in-place로 병합하여 오름차순으로 정렬된 배열을 만드는 것입니다.

1. 초기 코드 접근 방식

먼저, 제가 작성한 초기 코드는 nums1의 유효한 부분을 새로운 배열(nums3)에 복사한 후, nums3와 nums2를 비교하며 작은 값부터 nums1에 채워 넣는 방식입니다.

초기 코드 예시

export function merge(
  nums1: number[],
  m: number,
  nums2: number[],
  n: number,
): void {
  const nums3 = nums1.slice(0, m);
  let i2 = 0;
  let i3 = 0;

  for (let index = 0; index < m + n; index++) {
    if (i2 >= n) {
      nums1[index] = nums3[i3++];
      continue;
    }

    if (i3 >= m) {
      nums1[index] = nums2[i2++];
      continue;
    }

    nums1[index] = nums2[i2] < nums3[i3] ? nums2[i2++] : nums3[i3++];
  }
}

이 방법은 시간 복잡도 O(m+n)로 효율적이나, nums1의 첫 m개 요소를 복사하기 위해 O(m)의 추가 공간을 사용합니다.

2. 공간 복잡도 개선: in-place 방식

문제의 in-place 조건을 완벽하게 만족하기 위해, 추가 공간 없이 nums1의 뒷부분부터 채워 나가는 방식으로 코드를 개선했습니다.
이 방식은 두 배열의 마지막 인덱스부터 비교하며, 큰 값을 nums1의 끝에 배치하는 방법으로 동작합니다. 이를 통해 공간 복잡도를 O(1)로 줄일 수 있습니다.

개선된 코드 예시

export function merge(
  nums1: number[],
  m: number,
  nums2: number[],
  n: number,
): void {
  let p1 = m - 1;         // nums1의 유효 부분 마지막 인덱스
  let p2 = n - 1;         // nums2의 마지막 인덱스
  let p = m + n - 1;      // nums1의 전체 마지막 인덱스

  while (p2 >= 0) {
    if (p1 >= 0 && nums1[p1] > nums2[p2]) {
      nums1[p] = nums1[p1];
      p1--;
    } else {
      nums1[p] = nums2[p2];
      p2--;
    }
    p--;
  }
}

이 개선된 방식의 주요 장점은 다음과 같습니다:

• 공간 절약: 추가 배열 없이 in-place로 작업합니다.
• 효율성: 두 배열의 마지막 요소부터 비교하여 한 번의 순회로 병합할 수 있습니다.

결론

초기 코드에서는 추가 공간을 사용해 문제를 해결했지만, in-place 방식으로 전환함으로써 공간 복잡도 문제를 개선할 수 있었습니다. 이번 문제 풀이를 통해 알고리즘 최적화와 효율적인 코딩의 중요성을 다시 한번 확인할 수 있었습니다.

이 글이 코딩 테스트 준비와 알고리즘 문제 해결에 도움이 되길 바랍니다!