99클럽(2기) 코테 스터디 1일차 TIL (주식 가격)

---

99클럽 코테 스터디

2기는 유료로 바뀌었길래 살짝 고민했는데 한 회에 만원이 아니고 전체에 만원이라 할 만하다고 생각하여 또 참여하게 되었다. 1회차인 월요일부터 풀 참여할걸 그랬나 하는 생각이 들긴 한다.

문제가 1문제로 줄었는데, 쉬운 문제였지만 약간의 착각과 삽질 때문에 30분 가량 소요되었다.

1번 문제 주식 가격 : https://school.programmers.co.kr/learn/courses/30/lessons/42584

출처 : 프로그래머스

---

1번 문제 주식 가격

---

풀이 접근

되게 어렵게 접근했다가 삽질을 꽤나 했다. 뒤에서부터 세기 테크닉, 이진 탐색 등의 기법을 적용해서 풀려 했는데(이 방법으로도 풀려면 풀 순 있다), 그냥 앞에서부터 힙으로 해도 풀려서 풀었다. 그리고 다 풀고 생각해보니 그냥 스택 자료구조(파이썬은 그냥 list로 할 수 있음)로 더 효율적으로 풀 수 있어서 다시 풀었다.

99클럽에서 서로 다른 코드로 두 번 제출해 보는 건 처음이라, 두 코드 다 써두었다. 풀이의 근간이 되는 설명은 오히려 코드 2 설명에 많이 써두었으니 참고할 수 있을 것이다.

---

코드 1 (Python3, 통과, 최대 99.19ms, 19.4MB)

코드 2에서 설명하겠지만, 스택 대신에 힙을 쓸 필요가 없다(들어온 순서대로 오름차순이 보장되기 때문에).

그래도 시간복잡도가 10만 * log(1만)인거 치고 그리 오래 걸리진 않았다.

import heapq

def solution(prices):
    n = len(prices)
    answer = [0] * n
    heap = []
    for i in range(n):
        price = prices[i]
        while heap:
            mp, idx = heapq.heappop(heap)
            if price >= -mp:
                heapq.heappush(heap, (mp, idx))
                break
            answer[idx] = i - idx
        heapq.heappush(heap, (-price, i))
    while heap:
        mp, idx = heapq.heappop(heap)
        answer[idx] = n - idx - 1
    return answer

---

코드 2 (Python3, 통과, 최대 30.51ms, 19.4MB)

어차피, '아직 주가가 하락하지 않아서 들어갈 숫자가 확정되지 않은 지점'들은 시간순으로 오름차순으로 나열되게 된다.

예를 들면 아래와 같다.

1~5초 동안의 주가가 아래 그림과 같으면, 2초째의 주가는 1초만에 하락했으므로 answer의 두 번째 원소는 1로 확정되고, 1,3,4,5번째 원소는 아직 확정되지 않았다. 그리고 이 1,3,4,5번째 원소를 모으면(빨간색으로 표시), 시간순으로 오름차순(평행 포함)이 될 수밖에 없다.

만약 그 다음 순간인 6초에 주가가 살짝 꺾여 아래 그림과 같이 떨어진다면, 4,5초째의 결과(answer의 4,5번째 원소)는 각각 2,1로 확정된다. 그리고 아직 결과가 확정되지 않은 1,3,6초째(파란색으로 표시)의 주가는 여전히 오름차순(3,6초째의 주가가 같은 상황이어도 유효)이다.

즉, 이렇게 오름차순이 보장된 상황에서는, 스택 자료구조를 사용하여 미확정된 과거의 주가 중 제일 높은 주가부터(= 스택의 제일 마지막 원소부터) 다음 순간의 주가와 비교하고, 오름차순이 유지된다면 스택에 추가, 떨어진다면 스택에서 원소를 꺼내 해당 위치가 몇 초동안 지속된 건지 answer에 기록하는 식으로 진행할 수 있다.

힙 대신 스택을 사용하였더니 실행 시간이 1/3 가량으로 단축되었다. 다만 원래 힙을 썼을 때 최악의 상황으로는 log(1만), 즉 13배 가량이 더 들어야 되는데, 이와 같이 오름차순이 항상 보장되는 상황에서는 힙을 써도 스택과 다름없이 맨 뒤에서만 넣었다 뺐다 하였기 때문에 생각보다 큰 차이가 나지는 않은 것 같다.

코드 1에서도 그랬지만, 스택에 가격만 넣는게 아니고 가격과 함께 인덱스(시간)도 넣는 게 사소한 디테일!
-> 매니저님 피드백 : 오히려 스택에 가격을 안 넣고 인덱스(시간)만 넣어둬도 해당 시간의 주가는 prices[idx]로 알 수 있으므로 스택에 인덱스만 넣어도 된다.

def solution(prices):
    n = len(prices)
    answer = [0] * n
    stack = []
    for i in range(n):
        price = prices[i]
        while stack:
            if stack[-1][0] > price:
                idx = stack[-1][1]
                answer[idx] = i - idx
                stack.pop()
            else:
                break
        stack.append((price, i))
    for j in range(len(stack)):
        idx = stack[j][1]
        answer[idx] = n - idx - 1
    return answer