[Stack] leetCode 1944. Number of Visible People in a Queue 풀이 - Python

알고리즘 풀이 게시글은 작성하기가 조금 번거로워서 게시글을 자주 안올리다보니, 공부 효과가 떨어지는 것 같아서 풀이법을 다시 열심히 블로깅하자고 결심.....했다...!

이번에 문제를 푼 플랫폼은 leetCode https://leetcode.com/problems/number-of-visible-people-in-a-queue/

영어로 되어있어서 문제 해석하는 재미도 있다. 히히

---

문제

There are n people standing in a queue, and they numbered from 0 to n - 1 in left to right order. You are given an array heights of distinct integers where heights[i] represents the height of the ith person.

A person can see another person to their right in the queue if everybody in between is shorter than both of them. More formally, the ith person can see the jth person if i < j and min(heights[i], heights[j]) > max(heights[i+1], heights[i+2], ..., heights[j-1]).

Return an array answer of length n where answer[i] is the number of people the ith person can see to their right in the queue.

 

n 명의 키가 담겨있는 배열 heights에서 각 위치의 사람이 볼 수 있는 사람 인원 수를 세면 되는 문제이다.

0부터 n - 1 위치에는 사람들이 순서대로 서있으며, 각 위치의 사람들 사이의 사람들이 그들보다 작으면 오른쪽의 사람들을 볼 수 잇다.

i < j 일 때, i 번째 사람은 min(heights[i], heights[j]) > max(heights[i+1], heights[i+2], ..., heights[j - 1]) 인 사람들만 볼 수 있다.

= i번째 사람은 자기보다 작고 가려지지 않은 사람만 볼 수 있다. 자기보다 큰 사람이 있는 경우 그 사람까지만 볼 수 있으며 그 뒤에 있는 사람은 볼 수 없다. 

 

제한조건

• n == heights.length
• 1 <= n <= 105
• 1 <= heights[i] <= 105
• All the values of heights are unique. : 사람들의 키는 유일하다. (중복되는 키가 없다)

예시

Input: heights = [10,6,8,5,11,9]
Output: [3,1,2,1,1,0]
Explanation:
Person 0 can see person 1, 2, and 4.
Person 1 can see person 2.
Person 2 can see person 3 and 4.
Person 3 can see person 4.
Person 4 can see person 5.
Person 5 can see no one since nobody is to the right of them.

---

풀이법

스택을 활용하면 될 것 같은데 사실 조금 헤맸다...!

다음과 같은 사람들의 키를 담은 배열 heights 가 있다.

1. 각 위치의 사람이 볼 수 있는 사람의 수를 기록할 리스트 answer을 선언하여 인원 수 만큼 0으로 초기화 해준다.

'오른쪽에 서 있는 사람'를 관리하기 위하여 스택으로 사용할 리스트 하나를 선언한다.

answer = [0] * len(height)
stk = []

 

2. loop를 도는데 제일 마지막에 서있는 사람부터 확인한다.

for idx in range(len(heights) - 1, -1, -1):
    count = 0    # 볼 수 있는 사람의 갯수
    
    # 오른쪽의 있는 사람이 idx번째 사람보다 작은 경우, 그 뒤의 사람도 볼 수 있다.
    while stk and heights[idx] > heights[stk[-1]]:
        stk.pop()
        count += 1    # idx 번째 사람보다 작은 사람 count 증가
    
    if stk:	          # 여전히 스택에 값이 있는 경우,
        count += 1    # 마지막으로 볼 수 있는 사람 추가 (나보다 커서 뒤의 사람을 가리는 녀석)
    
    answer[idx] = count
    stk.append(idx)    # 인덱스값 스택에 추가

idx 위치의 사람 기준으로 오른쪽에 서있는 사람을 스택으로 확인한다.

바로 오른쪽에 있는 사람이 현재 사람보다 작은 경우 그 뒤 사람도 볼 수 있기 때문에 pop()으로 스택에서 값을 제거한다.

스택에 여전히 값이 남아있는 경우는 나보다 커서 뒤의 사람을 모두 가리고 있는 상태인데,  나보다 크지만 가장 맨 앞에 있는 사람을 볼 수 있기 때문에 count 값을 증가시킨다.

볼 수 있는 사람을 모두 카운트 한 후에는 answer에 count 값을 기록하고 스택에 현재 idx값을 append()한다. 

 

idx = 5 일 때,

마지막 사람은 오른쪽에 사람이 없기 때문에 스택에 담긴 값이 없다.

따라서, 5번의 사람이 볼 수 있는 사람은 0명으로 answer[5] = 0 이다.

 

append 결과

 

 

 

 

 

 

 

 

다음 반복에서 사용할 idx값을 스택에 담아준다. => 이 값은 idx = 4일 때 오른쪽에 서있는 사람으로 사용된다.

idx = 4일 때,

pop() 후 append

오른쪽(stk[-1])에 5번 사람이 서있다. 5번째 사람은 4번째 사람보다 작기 때문에 5번째 사람을 볼 수 있고, 그 뒤엔 사람이 더 이상 없기 때문에 스택은 빈다(empty). 따라서 4번째 사람이 볼 수 있는 사람의 수는 1명 이다.

idx = 3 일 때,

append

바로 오른쪽의 사람은 4번 사람이다. 4번째 사람은 키가 11로 3번째 사람의 키(5) 보다 크기 때문에 4번째 사람밖에 볼 수 없다.

if stk: count += 1 코드로 3번째 사람이 볼 수 있는 사람의 수는 1이 된다.

 

 

idx = 2 일 때,

2번째 사람(8)의 오른쪽 사람인 3번째 사람(5)이 더 작다. 따라서 스택에서 3번째 사람은 제거되고, count 가 증가한다. 4번째 사람은 2번째 사람보다 크기 때문에 스택에서 제거되지 않지만 4번째 사람을 볼 수 있기 때문에 2번째 사람이 볼 수 있는 사람의 수는 2명 이다.

idx = 1 일 때,

1번째 사람의 키(6)은 두번째 사람의 키(8)보다 작기 때문에 스택의 값을 제거할 수 없다.

따라서 1번째 사람은 두번째 사람만 볼 수 있으며 1번째 사람이 볼 수 있는 사람의 수는 1명이다.

idx = 0 일 때,

0번째 사람의 키(10)는 1번째 사람보다 크다. while 반복문에서 1번째 사람이 제거되고, 2번째 사람(8)하고 키를 비교하게 된다.

2번째 사람 또한 0번째 사람보다 작기 때문에 2번째 사람이 스택에서 제거된다.

 

 

3번째 사람은 2번째 사람에 가려져 보이지 않고(2번째 사람이 볼 수 있는 사람을 처리할 때 스택에서 제거되었다.), 4번째 사람은 0번째 사람보다 크기 때문에  스택에서 제거되지 않는다. 하지만 0번째 사람은 마지막으로 스택에 남아있는 4번째 사람을 볼 수 있기 때문에 0번째 사람은 총 3명의 사람을 볼 수 있다.

 

 

 

실행결과

각 인덱스 위치의 사람이 볼 수 있는 사람의 수를 담은 배열 answer의 최종상태는 다음과 같다.

 

---

최종 코드

class Solution(object):
    def canSeePersonsCount(self, heights):
        """
        :type heights: List[int]
        :rtype: List[int]
        """
        stk = []
        answer = [0] * len(heights)
        
        for i in range(len(heights) - 1, -1, -1):
            count = 0
            
            while stk and heights[i] > heights[stk[-1]]:
                stk.pop()
                count += 1
                
            if stk:
                count += 1
            
            answer[i] = count
            stk.append(i)
            
        return answer

 

 

 

 

알고리즘을 쉽게 기술하기가 너무너무 어렵다.. 🥲 그래도 계속 블로깅 해서 글쓰기 능력을 향상시켜야지