코딩테스트 연습 - 주식가격(스택/큐)

[문제]

초 단위로 기록된 주식가격이 담긴 배열 prices가 매개변수로 주어질 때,

가격이 떨어지지 않은 기간은 몇 초인지를 return 하도록 solution 함수를 완성하세요.

 

제한사항

• prices의 각 가격은 1 이상 10,000 이하인 자연수입니다.
• prices의 길이는 2 이상 100,000 이하입니다.

입출력 예

price	return
[1, 2, 3, 2, 3]	[4, 3, 1, 1, 0]

설명
1초 시점의 ₩1은 끝까지 가격이 떨어지지 않았습니다.
2초 시점의 ₩2은 끝까지 가격이 떨어지지 않았습니다.
3초 시점의 ₩3은 1초뒤에 가격이 떨어집니다. 따라서 1초간 가격이 떨어지지 않은 것으로 봅니다.
4초 시점의 ₩2은 1초간 가격이 떨어지지 않았습니다.
5초 시점의 ₩3은 0초간 가격이 떨어지지 않았습니다.

 

---

[1차 시도] - 2중 for문을 이용한 시도.

스택/큐 문제라는데 그건 모르겠고 일단 아무렇게나 생각나는대로 시도해봤다.

딕셔너리를 하나 만들고 이중으로 포문을 만들어 돌리면서 1씩 더해주거나 넘어가거나 하면 되지 않을까?

예를들어 0번부터 차례로 시작하는 for문 하나와 상위 for문의 다음번(0이면 1, 1이면 2 이런식으로..)부터 시작하는 for문 하나.

이렇게 포문을 이중으로 돌려서 뒤의 값이 앞의 값보다 크거나 같으면 가격이 떨어지지 않은 것이므로 +1을 해주고

그렇지않다면 pass를 해주었다. 

 

def solution(prices):
    dic = {}
    num = len(prices)
    
    for i in range(num):
        dic[i] = 0
    
    for i in range(num):
        for j in range(i+1, num):
            if prices[i] <= prices[j]:
                dic[i] += 1
            else:
                pass

    return list(dic.values())

 

테스트 케이스는 가볍게 통과하는 듯 했는데, 제출을 눌러보니 정확도 테스트는 모조리 틀렸고, 효율성은 전부 시간초과가 나왔다. 

비슷하지만 while과 pop을 이용해서 짜본 코드.

pop(0)를 해서 0번째 인덱스를 끌고오고 for문을 하나만 사용해서 돌렸다.

dictionary를 빼고 그냥 카운트라는 변수로 받아서 answer 리스트에 append 해주었다. 

def solution(prices):
    answer = []

    while len(prices) > 0:
        count = 0
        i = prices.pop(0)
        num = len(prices)
        for j in range(num):
            if prices[j] >= i:
                count += 1
            else:
                continue
        answer.append(count)
    
    return answer

로직이 같으니 당연한거겠지만 테스트케이스만 통과하고 정확도와 효율성은 모두 실패와 시간초과..

 

[2차 시도]  - 문제를 제대로 읽다...

문제를 오해하고 있었다. 3 2 1 1 이라는 배열이 주어지면 3은 1초뒤에 2로 떨어지기 때문에 1초동안 가격이 유지된 것으로 보아야 했다. 하지만 나는 여태까지 3에서 2로 떨어졌네? 응 0 하고 그냥 냅다 0을 반환했다. 어쩐지 맞는거 같은데 실패가 나오더라니.. 

 

어쨋든 그냥 배열과 현재 위치 마지막 위치를 넣어주면 그 주식의 가격이 몇초나 유지되었는지를 반환해주는 함수를 하나 정의하고 for문 안에서 그 함수가 돌아가면서 값을 반환하면 answer 리스트에 append 해주는 방식으로 정답을 도출해냈다. 

 

def solution(prices):
    def turn(list, n, m):
        count = 0
        for i in range(n+1, m):
            if list[n] > list[i]:
                count += 1
                break
            elif i == m:
                count = 0
            else:
                count += 1
        return count
    
    answer = []
    
    for i in range(len(prices)):
        answer.append(turn(prices, i, len(prices)))
        
    return answer

 

 

ps... 문제를 풀 때 자꾸 쉬워보인다고 무작정 풀려고 하는 이 성급함을 버리고 차근차근 읽어보고 제대로 푸는 연습을 더 해야겠다..