⁉️ 탑의 레이저 통신 – 자바 코딩 테스트 풀이

❓ 문제 설명

 

KOI 통신연구소는 레이저를 이용한 비밀 통신 시스템을 개발 중입니다.
이를 위해 일직선 상에 N개의 높이가 서로 다른 탑을 세우고, 탑의 꼭대기에 레이저 송신기를 설치했습니다.

 

• 모든 탑은 **자신의 왼쪽 방향(즉, 앞쪽 탑들)**으로 레이저를 발사합니다.

• 레이저는 가장 먼저 만나는 하나의 탑에서만 수신됩니다.

• 수신 장치는 모든 탑의 몸체에 부착되어 있으며, 발사된 레이저는 본인의 앞쪽에 있는 탑 중 본인보다 높은 탑에서만 수신될 수 있습니다.

---

예시 설명

 

탑의 높이 배열이 [6, 9, 5, 7, 4]인 경우 :

탑 번호:   1  2  3  4  5
높이:     6  9  5  7  4
레이저:  ← ← ← ← ←

- 5번 탑(4)의 레이저 → 4번 탑(7)이 수신
- 4번 탑(7)의 레이저 → 2번 탑(9)이 수신
- 3번 탑(5)의 레이저 → 2번 탑(9)이 수신
- 2번 탑(9), 1번 탑(6)은 수신하는 탑이 없음

출력: 0 0 2 2 4

---

📌 제한 조건

 

• 1 ≤ N ≤ 500,000

• 각 탑의 높이 : 1 이상 100,000,000 이하

• 시간 복잡도 O(N²) 풀이로는 제한 시간 초과 가능 (추후 스택 기반 개선 가능)

---

🔍 문제 요약

 

• 각 탑은 왼쪽 방향으로 레이저를 쏜다.

• 자기보다 높은 탑이 처음 등장하는 곳까지 수신 가능

• 수신한 탑의 인덱스(1-based)를 출력, 수신 탑이 없으면 0

---

✅ 코딩

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        int totalTower = sc.nextInt();
        int[] tower = new int[totalTower];
        int[] receive = new int[totalTower]; // 수신 탑 인덱스 저장

        for (int i = 0; i < totalTower; i++) {
            tower[i] = sc.nextInt();
        }

        // 오른쪽 탑부터 왼쪽 탑들을 검사
        for (int i = totalTower - 1; i > 0; i--) {
            for (int j = i - 1; j >= 0; j--) {
                if (tower[j] > tower[i]) {
                    receive[i] = j + 1; // 인덱스는 1부터 출력
                    break;
                }
            }
        }

        for (int i = 0; i < totalTower; i++) {
            System.out.print(receive[i] + " ");
        }
    }
}

---

💡 해설

 

• 브루트포스 방식으로 각 탑마다 왼쪽에 있는 탑을 순회하며 확인

• i번째 탑의 왼쪽 탑들을 j로 순회하면서, 처음 자기보다 큰 탑을 찾으면 그 인덱스를 저장하고 break

• 시간복잡도는 O(N²)로, 최악의 경우 500,000 * 500,000은 시간 초과 발생할 수 있음

• ➕ 실제 대형 데이터에서는 스택을 이용한 O(N) 풀이가 필요