3015번 - 오아시스 재결합

💡 스택을 활용한 사고력을 키우자..

<오답 코드>

import sys

input = sys.stdin.readline

N = int(input())
cnt = 0

group = [0] * N
stack = []

for i in range(N):
    group[i] = int(input())

# 본인 보다 뒤만 카운트 하기
for j in group:
    
    while stack:
        if j >= stack[-1]:
            cnt += len(stack)
            stack.pop()
        else:
            break
    stack.append(j)

if len(stack) > 1:
    print(cnt + len(stack))
else:
    print(cnt)

• 이 문제는 내 기준 생각보다 너무 어려웠다..ㅋㅋㅋㅋㅋ 스택을 사용해서 풀어야 하는 것은 알고 있었지만, 나름 여러가지 방법론을 생각해 보았지만, 계속 15%를 넘기지 못하고 오류가 발생하였다.
• 위 코드는 기존 제공하는 입력 예시에는 적용이 되지만, "5 5 2 2 5"와 같이 동일한 사람들의 키를 제대로 처리하지 못하였다.

<정답 코드>

import sys

input = sys.stdin.readline

N = int(input())
cnt = 0
stack = []

for _ in range(N):
    height = int(input())
    same = 1  # 현재 키를 가진 사람의 개수

    # 스택에서 자신보다 작거나 같은 키 제거
    while stack and stack[-1][0] <= height:
        cnt += stack[-1][1]  # 해당 그룹의 사람들은 전부 볼 수 있음
        if stack[-1][0] == height:
            same += stack[-1][1]  # 같은 키가 연속되면 그룹화
        stack.pop()

    # 스택에 현재 키 추가
    if stack:
        cnt += 1  # 바로 앞의 사람과는 무조건 볼 수 있음
    
    stack.append([height, same])

print(cnt)

• 결국 핵심 포인트 "키가 동일한 사람들"을 어떻게 처리해야 하는지가 가장 중요했던 거 같다
• stack에 값을 넣어줄 때는 [height, count]로 값을 받도록 설정하였다. ( 키가 같은 경우를 처리하기 위해서)
• 일단 stack의 맨 위보다 키가 작은 사람이 들어오면, 일단 stack의 맨위에 포함되어 있는 그룹 (키가 동일할 경우) 들과 무조건 1번씩은 서로 보기 때문에 stack[-1][1]에 해당하는 count값을 더해주고, 더이상 키가 작은 사람은 의미가 없기 때문에 stack에서 제거해준다.
• 만약 stack의 맨 위와 키가 동일한 경우에는, stack 맨 위 값의 count를 1 더하여 주었다.

💡 코테스터디 중 나온 기발한 접근법

논리적인 접근이 정말 어려웠다고 모두들 생각하였다.
결국 대부분의 사람이 hint를 참고하여 풀었고, 거의 비슷한 방식으로 풀이했던 것 같다.