HyeGyeong
HyeGyeong 프로그래머를 꿈꾸며 JavaScript 공부 중

[Algorithm] 탑

[Algorithm] 탑

문제설명

  • 수평 직선에 탑 N대를 세웠습니다. 모든 탑의 꼭대기에는 신호를 송/수신하는 장치를 설치했습니다. 발사한 신호는 신호를 보낸 탑보다 높은 탑에서만 수신합니다. 또한, 한 번 수신된 신호는 다른 탑으로 송신되지 않습니다.

  • 예를 들어 높이가 6, 9, 5, 7, 4인 다섯 탑이 왼쪽으로 동시에 레이저 신호를 발사합니다. 그러면, 탑은 다음과 같이 신호를 주고받습니다. 높이가 4인 다섯 번째 탑에서 발사한 신호는 높이가 7인 네 번째 탑이 수신하고, 높이가 7인 네 번째 탑의 신호는 높이가 9인 두 번째 탑이, 높이가 5인 세 번째 탑의 신호도 높이가 9인 두 번째 탑이 수신합니다. 높이가 9인 두 번째 탑과 높이가 6인 첫 번째 탑이 보낸 레이저 신호는 어떤 탑에서도 수신할 수 없습니다.

문제: https://programmers.co.kr/learn/courses/30/lessons/42588

제한사항

  • heights는 길이 2 이상 100 이하인 정수 배열입니다.
  • 모든 탑의 높이는 1 이상 100 이하입니다.
  • 신호를 수신하는 탑이 없으면 0으로 표시합니다.

풀이

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

function solution(heights: number[]): number[] {
  const answer: number[] = Array(heights.length).fill(0); // heights의 길이만큼 0으로 채운 array 생성
  for (let i: number = 1; i < heights.length; i++) {
    // heights의 모든 요소를 반복
    for (let j: number = i - 1; j >= 0; j--) {
      // 뒤에 있는 탑의 길이보다 높은 탑에 레이저가 닿으므로 i번째 앞에서부터(i-1) 0번째까지 더 높은 탑이 있는지 체크
      if (heights[i] < heights[j]) {
        // 현재 탑보다 높은 탑이 있으면
        answer[i] = j + 1; // j+1 할당.
        break;
      }
      if (j === 0) {
        // 0번째는 앞에 다른 탑이 없으므로 무조건 0.
        break;
      }
    }
  }
  return answer;
}