[코딩 테스트 합격자 되기] stack의 심화 (내 기준)

고래강이 2025. 1. 8. 14:19

☄️ 문제 접근 및 내 생각

1. 문제를 짝지어서 pop하는 문제이므로 이전값과 현재값을 비교해서 같을경우에는 현재값을 추가하지 않고 이전값을 pop하면 될 것 같다. 그 외의 경우에는 정상적으로 stack을 사용해서 값을 쌓아나가면 될 것 같다.

소요시간: 15분

🌈 파이썬 코드

# 처음 코드
def solution_11(string):
    stack = []
    for i in string:
        if len(stack) == 0:
            stack.append(i)
            continue
        if i == stack[-1]:
            stack.pop()
        else:
            stack.append(i)
    return int(not len(stack) > 0)
    
# 개선된 코드
def solution_11(string):
    stack = []
    for i in string:
        if len(stack) != 0 and i == stack[-1]:
            stack.pop()
        else:
            stack.append(i)
    return int(not len(stack) > 0)

처음 코드를 보게 되면 if문이 2개 사용되었는데 이 부분을 수정할 수 있다. 왜냐면 and연산자를 통해서 stack.append()를 사용해야할 부분을 하나의 조건문으로 만들어서 사용할 수 있기 때문이다. 그렇기에 아래와 같이 수정할 수 있겠다.
int()의 경우에 boolean값을 넣었을 경우 참이면 1 거짓이면 0을 출력한다는 성질이 있기에 다음과 같이 사용할 수 있다. -GPT

🌈 자바스크립트 코드

function solution(string) {
  const stack = [];
  [...string].forEach((i) => {
    if (stack.length !== 0 && stack[stack.length - 1] === i) {
      stack.pop();
    } else stack.push(i);
    console.log(stack);
  });
  return !stack.length ? 1 : 0;
}

array.length를 array.length()로 사용했다가 몇 번 typeError를 일으켰다. 조심해야지

☄️ 문제 접근 및 내 생각

1. 문제에 대해서 이해를 전혀하지 못했다. return되는 배열이 의미하는 바를 이해하지 못해서 문제의 해결 방법을 조금씩 참고하면서 문제를 이해해보려 했다.
2. 일단 막대그래프를 생각하면서 문제를 풀어서 생각을 해보았다. y축의 값이 1이하로 떨어지지 않는시간이 1~5초이므로 4초 동안 price 1이 유지되었으니 return[0]은 4일 것이다. 순서대로 진행하다가 마지막 부분인 prices[3:]의 주식가격이 변동되지만 마지막 시점인 prices[4]는 유지한 시간이 없으므로 return[3:] 부분은 각각 1, 0이 되는 것 같다.
3. 문제에 대한 해석이 끝났으니 문제를 풀어보자
4. 처음 생각난 부분은 n이 주어졌을 때 1 ~ n까지의 수를 stack에 쌓아서 최종적으로 주어진 배열의 길이 -2만큼 for문을 돌려서 값을 구한 것에서 다시 for문을 돌려서 숫자의 개수를 return하도록 하는 문제인데 이렇게 구하면 O(n^2)이기에 조건에 맞지 않는다고 하니깐 다시 생각해보자.
5. 문제는 해설을 보면서 이해하는 걸로 했다

소요시간: 40분(문제 해석) + 60분(문제 풀이)

🌈 파이썬 코드

def solution(prices):
	n = len(prices)
    result = [0]*n
    stack = [0]

	for i in range(1, n):
    	while stack and prices[i] < prices[stack[-1]]:
        	j = stack.pop()
            result[j] = i - j
    	stack.append(i)
    while stack:
    	j = stack.pop()
        result[j] = n - 1 -j
    return result

가장 힘들었던 부분은 stack에 쌓이는 것이 range의 i값인데 prices[i] 값으로 착각을 해서 이해하는 데 오래걸렸다. 위 for문(들여쓰기가 버그가 났나? 저렇게 되누)은 하락하는 지점을 알려주는 구문이고 아래 while문은 그 지점을 제외한 나머지 유지하는 시간을 할당하는 구문이다.
실제로 n - 1 -j, i - j와 같이 위치를 나타내는 부분에 대해서 이해도가 좀 부족하다는 것을 많이 느꼈다...