Programmers 주식가격

💡문제 분석 요약

• 주식가격이 담긴 배열 prices가 주어진다.
• 각 원소별로 몇초간 떨어지지 않았는지 구한다. 1 2 3이라고 하면 순서대로 2초, 1초, 0초간 가격이 떨어지지 않은 것으로 본다.

💡알고리즘 설계

• 이중 for문을 사용해서 첫번째 원소를 나머지 원소와 쭉 비교하는데, 만약 가격이 떨어지는 순간이 나오면 break하고 그때까지의 time을 기록하면 된다고 생각했다. 그런데 이중 for문을 쓰면 시간이 초과될 것 같아서 해보고 오버되면 다르게 하려 했는데 오버되지 않았다.
  • 생각해보면, 일단 prices 길이가 10만이었기 때문에 이중for문이면 100억번 계산되는 건가 싶었다.
  • 그런데 중간에 자기보다 큰 수가 나오면 바로 break되기 때문에 저정도로 큰 계산이 되지는 않을 것으로 생각했다.

💡코드

def solution(prices):
    lst = []
    for i in range(len(prices)):
        ans = 0
        for j in range(i+1, len(prices)):
            if prices[i] <= prices[j]:
                ans += 1
            else:
                ans += 1
                break
        lst.append(ans)
    return lst

print(solution([1, 2, 3, 2, 3]))

💡시간복잡도

• 이중 for문을 사용해서 O(N^2)이 될 것으로 예상된다.

💡 틀린 이유

• 안쪽에 있는 for문에서 시작 지점을 i가 아니고 i+1부터 시작했어야하는데 i부터 비교해서 return 값이 더 크게 나오는 오류가 있었다.

💡 틀린 부분 수정 or 다른 풀이

• 앞서 팀원분이 푼 풀이를 보았는데 나의 풀이와 똑같았지만 if 처리가 더 간결해서 좋았다. 나는 if, else 둘 다 했는데 사실 코드를 보면 if든 else든 ans에는 1을 더해줘야함을 알 수 있다. 따라서 더 쉽게 하려면 처음부터 ans에 1을 더해주고, 앞의 가격이 뒤의 가격보다 클 때만 break해주는 식으로 하면 코드가 더 깔끔해질 것이다.
• 그리고 ans도 사실 time같은 변수명으로 해줬어야 더 직관적이고 좋았을 것 같다.

def solution(prices):
    lst = []
    for i in range(len(prices)):
        time = 0
        for j in range(i+1, len(prices)):
            time += 1
            if prices[i] > prices[j]:
                break
        lst.append(time)
    return lst

print(solution([1, 2, 3, 2, 3]))

💡 느낀점 or 기억할정보

• 변수명 항상 깔끔하고 직관적으로 짓기
• if-else에서 합칠 수 있는 건 합치기
• 시간복잡도 고려, O(N^2)은 지양하기