[Python] 코드업 #3130 : 소들의 헤어스타일

https://codeup.kr/problem.php?id=3130

소들의 헤어스타일

 

입력

첫째줄에 소들의 수 : N

두번째 줄부터 N+1개 줄 만큼 소들의 키가 입력 된다. : H

 

출력

각 소들이 헤어 스타일을 확인할 수 있는 소들의 수를 출력한다.

 

이중 for문을 사용하면 시간초과가 난다.

stack으로 문제 풀이를 진행해야 한다.

 

 

Stack이란?

후입선출(LIFO: Last In First Out)

가장 나중에 넣은 데이터를 가장 먼저 꺼내는 방식

데이터를 일시적으로 저장하기 위해 사용하는 자료구조

 

 

 

각 소의 키가 입력될 때, 나를 볼 수 있는 소를 카운트하는 방식으로 stack을 사용해 문제를 풀이한다.

 

# Stack 사용
# 자신이 볼 수 있는 소가 몇 마리인지 파악하는 것이 아니라 자신을 볼 수 있는 소가 몇 마리인지 파악하는 것
class Stack: 
    def __init__(self):
        self.len  = 0
        self.list = []

    def push(self, num):
        self.list.append(num)
        self.len += 1

    def pop(self):
        if self.size() == 0:
            return -1
        pop_result = self.list[self.len-1]
        del self.list[self.len - 1]
        self.len -= 1

        return pop_result

    def size(self):
        return self.len
    
    def empty(self):
        return 1 if self.len == 0 else 0

    def top(self):
        return self.list[-1] if self.size() != 0 else -1


n     = int(input()) # 소들의 개수 입력
stack = Stack()      # stack 선언
cnt   = 0            # 볼 수 있는 소의 케이스 결과의 개수


for _ in range(n) : #{
    #print(stack.list, c)
    c = int(input()) # 소의 키를 입력으로 받음

    if stack.empty() : # stack이 비어있다면 c를 push 해줌
        stack.push(c)

    elif stack.top() <= c : # 만약 stack의 top이 c보다 작다면 c를 보지 못하므로 pop으로 삭제해줌
        stack.pop()
        while stack.top() <= c and stack.top() != -1 : # 마찬가지로 stack의 top이 c를 볼 수 있을 때까지 pop으로 삭제해줌
            stack.pop()
        stack.push(c)   # stack에 c 소의 스타일을 볼 수 있는 소들만 남아있으므로 push 해줌     
  
    else : stack.push(c) # stack에 c 소의 스타일을 볼 수 있는 소들만 남아있으므로 push 해줌   

    cnt += stack.size() - 1 # c를 볼 수 있는 소들의 수를 cnt에 더해준다.
#}

print(cnt)

stack을 공부하기 위해 class로 선언해서 풀이했지만, class로 선언하지 않고 바로 list에 stack을 적용해서 풀어도 된다.

 

이 블로그에 설명이 잘 되어 있어 참고했다.

[C/C++] 코드업(codeup) 3130번 소들의 헤어스타일