[programmers] 올바른 괄호, 주식 가격

💡 오늘의 학습 키워드
- 올바른 괄호
- 주식 가격

 

🥉  올바른 가격

문제 링크 : https://school.programmers.co.kr/learn/courses/30/lessons/12909

 

문제 설명

괄호가 바르게 짝지어졌다는 것은 '(' 문자로 열렸으면 반드시 짝지어서 ')' 문자로 닫혀야 한다는 뜻입니다.
예를 들어

1. "()()" 또는 "(())()" 는 올바른 괄호입니다.
2. ")()(" 또는 "(()(" 는 올바르지 않은 괄호입니다.

'(' 또는 ')' 로만 이루어진 문자열 s가 주어졌을 때, 문자열 s가 올바른 괄호이면 true를 return 하고,
올바르지 않은 괄호이면 false를 return 하는 solution 함수를 완성해 주세요.

제한사항
1. 문자열 s의 길이 : 100,000 이하의 자연수
2. 문자열 s는 '(' 또는 ')' 로만 이루어져 있습니다.

 

문제 회고

💡 어떤 문제가 있었고, 나는 어떤 시도를 했는지 그리고 새롭게 안 사실은 무엇인지

괄호 문제였고 스택을 사용해 해결할 수 있는 문제였습니다. 문제 해결 과정은 다음과 같습니다. 

1. 괄호 리스트를 순회합니다.
2. 스택에 값이 비어있다면 괄호 리스트에서 꺼낸 값을 저장합니다.
3. 스택에 값이 들어있고 스택 위에 열린 괄호가 있을 때, 괄호 리스트에서 꺼낸 값이 닫힌 괄호일 경우
   스택 위의 열린 괄호를 pop 하여 꺼내줍니다.
4. 괄호리스트를 모두 순회한 후 스택에 값이 없다면 True를 있다면 False를 반환합니다.

 

💡 내가 해결한 방식은?

def solution(s):
    # 괄호 문제 -> stack
    stack = []
    
    for ss in s:
        if stack and stack[-1] == '(' and ss == ')':
            stack.pop()
            continue
            
        stack.append(ss)
        
    
    if not stack:
        return True
    else:
        return False

 

---

🥈 주식 가격

문제 링크 : https://school.programmers.co.kr/learn/courses/30/lessons/42584

 

문제 설명

초 단위로 기록된 주식가격이 담긴 배열 prices가 매개변수로 주어질 때,
가격이 떨어지지 않은 기간은 몇 초인지를 return 하도록 solution 함수를 완성하세요.

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

 

문제 회고

💡 어떤 문제가 있었고, 나는 어떤 시도를 했는지 그리고 새롭게 안 사실은 무엇인지

전화번호 목록 문제와 같이 원소 간 비교를 통해 효율적인 탐색을 찾는 문제였습니다. 문제 해결 과정은 다음과 같습니다.

1. 정답 리스트를 0으로 초기화 합니다.
2. 메인 루프에서 가격 리스트를 순회합니다.
3. 현재 가격의 다음 값부터 시간 값을 추가하며 마지막 값까지 순회합니다.
4. 현재 가격이 더 크다면 누적한 시간값을 정답 리스트에 저장하고 break 해줍니다.
5. 현재 가격이 계속 작았다면 누적해온 전체 시간 값을 더하고 값을 리턴합니다.

 

단순 반복을 통한 구현에서도 문제 해결은 가능했지만 시간 복잡도가 O(n^)이 발생하여
효율성 부분에서 개선된 코드를 발견해야 했습니다.

 

스택을 사용했을 때 알고리즘의 시간 복잡도가 O(n)이 되는 이유는 다음과 같습니다.

1. 각 가격은 스택에 한번 추가되고 한 번 제거됩니다. 즉, 가격은 최대 두 번의 연산에 참여합니다.
2. 첫 번째 루프는 'n' 번 반복되며, 각 반복에서 스택 연산은 상수 시간 내에 이루어집니다.
3. 두 번째 루프는 스택에 남아있는 요소들을 처리하는데, 이 요소는 끝까지 가격이 떨어지지 않은 경우입니다.
   최악의 경우에도 모든 요소가 한 번씩 처리되므로 이는 'n'에 비례합니다.

 

💡 내가 해결한 방식은?

시간 복잡도 O(n^2) 

def solution_1(prices):
    # 가격이 떨어지지 않은 기간 구하기
    # 구간 탐색
    answer = [0] * len(prices)
    
    for i in range(len(prices)-1):
        time_cnt = 0
        for j in range(i+1, len(prices)):
            time_cnt += 1
            if prices[i] > prices[j]:
                answer[i] += time_cnt
                break
                
        if answer[i] == 0:
            answer[i] += time_cnt
                
    return answer

시간복잡도 O(n)

def solution(prices):
    stack = []  # 인덱스와 가격을 추적하는 스택
    answer = [0] * len(prices)  # 답을 저장할 배열, 초기값은 모두 0
    
    for i in range(len(prices)):
        # 스택이 비어있지 않고, 현재 가격이 스택 상단의 가격보다 작으면
        while stack != [] and stack[-1][1] > prices[i]:
            past, _ = stack.pop()  # 스택에서 요소를 꺼냄
            answer[past] = i - past  # 가격이 떨어지지 않은 기간을 계산하여 저장
        stack.append([i, prices[i]])  # 현재 인덱스와 가격을 스택에 추가

    # 스택에 남아있는 모든 요소에 대해 가격이 떨어지지 않은 기간을 계산
    for i, s in stack:
        answer[i] = len(prices) - 1 - i
    
    return answer  # 답을 반환

 

---

✍️  TIL

스택을 괄호 문제와 같이 값을 넣고 단순 조건문으로 빼는 과정은 어렵지 않다.
주식 가격 문제와 같이 각 원소의 변화를 측정하기 위한 문제는 stack을 활용한 로직이 눈에 바로 보이지 않아
정답 코드를 보아도 직접 그려보아야 이해되는 경우가 있어 다소 응용력이 필요하다.
비슷하지만 다른 유형으로 문제를 지속적으로 풀고 그려보는 과정이 반복되어야 체득이 가능할 것 같다.
스택을 자유롭게 활용하면 원소 비교 및 탐색 문제는 어려움 없이 구현할 수 있으니 감을 잃지 않도록 하자