🌟 레이저 탑 문제(BOJ 2493) 해결 과정 정리 🌟

문제 요약
🏙️ N개의 높이가 서로 다른 타워가 왼쪽→오른쪽 순서로 일직선 위에 서 있고,
🔫 각 타워에서 왼쪽 방향으로 레이저 신호를 발사한다.
🎯 이 신호는 가장 먼저 만나는 왼쪽 방향의 타워 하나만 수신 가능.
출력: 각 타워가 발사한 신호를 수신하는 타워 번호(없으면 0).

---

1️⃣ 처음 떠올린 브루트포스 접근 🚧

• 각 타워 i에 대해 왼쪽으로 j = i–1 → 0까지 순회
  • height[j] > height[i]인 최초의 j 찾기
• 시간 복잡도: 최악 (O(N^2))
• ❌ N ≤ 500,000 → 절대 불가능

---

2️⃣ 스택을 이용한 최적화 아이디어 💡

관찰 👀

• 오른쪽→왼쪽 순회 시,
  • 자신보다 작은 타워들은 수신 대상 대기
  • 자신보다 높은 타워가 나타나면 즉시 수신

스택 전략 🗂️

1. 오른쪽 끝(N-1) → 왼쪽(0) 순회
2. 스택에 (인덱스, 높이) 저장
   • 현재 높이 > 스택 최상단 높이 →
     • 스택 최상단 타워 pop
     • result[popIdx] = 현재인덱스 + 1
     • while 반복
   • 종료 후, 현재 타워도 push

⚙️ 결과

• 각 타워는 한 번만 push & pop → O(N)
• 순회 완료 후 스택에 남은 타워들은 수신자 없음 → 0

---

3️⃣ 구현 디테일 🔨

int[] result = new int[N];
Stack<int[]> stack = new Stack<>();

// 1) 오른쪽 끝 → 왼쪽 순회
for (int i = N-1; i >= 0; i--) {
    int curH = heights[i];

    // 2) 더 높은 타워 등장 시 pop & 결과 기록
    while (!stack.isEmpty() && curH > stack.peek()[1]) {
        int[] top = stack.pop();
        result[top[0]] = i + 1;  // 📌 1-based index
    }

    // 3) 현재 타워도 후보로 push
    stack.push(new int[]{i, curH});
}

// 4) 남은 타워들은 수신자 없음 → 기본값 0 유지

• 🛠️ 자료구조: Stack<int[]> (int[]{index, height})
• 🔢 1-based vs 0-based: 내부 연산은 0-based, 결과는 i+1

---

4️⃣ 예제 동작 과정 📝

heights = [6, 9, 5, 7, 4]

i = 4 (4️⃣) → stack empty → push(4,4)
i = 3 (7️⃣)
  → 7 > 4? ✅ → pop(4) → result[4]=4
  → stack empty → push(3,7)
i = 2 (5️⃣)
  → 5 > 7? ❌ → push(2,5)
i = 1 (9️⃣)
  → 9 > 5? ✅ → pop(2) → result[2]=2
  → 9 > 7? ✅ → pop(3) → result[3]=2
  → stack empty → push(1,9)
i = 0 (6️⃣)
  → 6 > 9? ❌ → push(0,6)

최종 result = [0, 0, 2, 2, 4]

---

5️⃣ 핵심 포인트 정리 📌

1. Brute-force 불가 🚫
   • (O(N^2)) 탐색은 500,000 규모에서 터무니없이 느림
2. 스택 한 번 순회 🔄
   • 오른쪽→왼쪽
   • 더 높은 타워 등장 시 한 번에 pop
3. 시간/공간 복잡도 📈
   • 시간: (O(N))
   • 공간: (O(N)) (스택 + 결과 배열)
4. 1-based vs 0-based 🔢
   • 내부 순회: 0-based
   • 출력 저장: i+1
5. 스택 저장값 🔒
   • int[]{index, height} → pop 시 인덱스·높이를 동시에 사용