[TIL-20260212] 코딩 테스트 복습 - 탑(Tower) 문제

 

🍀 To Do List

✔️ 코테 강의 - stack

✔️ 사이드 프로젝트 - 유저 정보 조회 api, access token 유효성 체크 api, dev 배포

 

👩🏻‍💻 Today I Learned ...

 

탑(Tower) 문제

 

https://www.acmicpc.net/problem/2493

 

 

이중 for문 방식

입력: [6, 9, 5, 7, 4]

시각화:
🔫 🔫 🔫 🔫    레이저의 방향(왼쪽으로)
   I
   I
   I     I
I  I     I
I  I  I  I
I  I  I  I  I
6  9  5  7  4

출력: [0, 0, 2, 2, 4]

 

• 각 탑에서 왼쪽 방향으로 레이저를 발사
• 자신보다 높거나 같은 탑을 만나면 수신됨
• 오른쪽부터 역순으로 탐색하면서 왼쪽 탑들을 확인

 

def get_receiver_top_orders(heights):
    n = len(heights)
    result = [0] * n # 신호를 수신하는 탑이 없으면 0으로 표시

    # 오른쪽부터 역순 탐색
    for i in range(n - 1, -1, -1):
        # 현재 탑의 왼쪽 탑들을 확인
        for j in range(i - 1, -1, -1):
            # 현재 탑보다 높거나 같은 탑을 찾으면
            if heights[j] >= heights[i]:
                result[i] = j + 1  # 1-indexed 위치 저장
                break

    return result

 

• 각 탑에서 왼쪽 방향으로 레이저를 발사한다.
• 자신보다 높거나 같은 탑을 만나면 수신된다.
• 오른쪽부터 역순으로 탐색하면서 왼쪽 탑들을 확인한다.

 

Stack 활용 방식

 

 

💡 Stack이란?

• 한쪽 끝으로만 자료를 넣고 뺄 수 있는 자료 구조
• 기능
  • `push(data)` : 맨 앞에 데이터 넣기
  • `pop()` : 맨 앞의 데이터 뽑기
  • `peek()` : 맨 앞의 데이터 보기
  • `isEmpty()`: 스택이 비었는지 안 비었는지 여부 반환해주기

 

초기: [6, 9, 5, 7, 4]
                  ↑
                 pop

1. pop(4) → [6, 9, 5, 7]과 비교 → 7 찾음 → answer[4] = 4
2. pop(7) → [6, 9, 5]와 비교 → 9 찾음 → answer[3] = 2
3. pop(5) → [6, 9]와 비교 → 9 찾음 → answer[2] = 2
4. pop(9) → [6]과 비교 → 없음 → answer[1] = 0
5. pop(6) → []와 비교 → 없음 → answer[0] = 0

• 배열을 Stack처럼 사용한다.
• 맨 뒤(오른쪽)부터 `pop()` 하면서 처리한다.
• `pop()`된 값과 남은 배열(왼쪽 탑들)을 비교한다.
• 자신보다 높거나 같은 탑을 찾으면 해당 위치 저장한다.

 

def get_receiver_top_orders_stack(heights):
    answer = [0] * len(heights)

    while heights:
        # 맨 뒤(오른쪽) 탑 꺼내기
        height = heights.pop()

        # 남은 배열(왼쪽 탑들)을 역순으로 탐색
        for index in range(len(heights) - 1, -1, -1):
            # 자신보다 높거나 같은 탑 발견
            if height <= heights[index]:
                # 현재 남은 배열의 길이 = 원래 배열에서의 인덱스
                answer[len(heights)] = index + 1
                break

    return answer