스택 이란?
위의 설명처럼 나중에 들어온것이 먼저 나아갈수있는 블럭쌓기 형식이라고볼수있다
1.문제
나는 일단 문제 이해부터가 몇시간동안 되지않았다
다른나라 언어인줄알았다 오름차순이라는데 왜 1,2,3,4,5,6,7,8 이 아닌것인가...
입력에 써 있는 말도 이해가 안갔다 모든게 이해가 안가서 리트코드 홈페이지에서 스택수열 문제를 찾아봤다
1) 참고문제
두 개의 정수 배열이 주어 pushed지고 popped각각 고유한 값 true이 있는 경우 이것이 초기에 비어 있는 스택에 대한 푸시 및 팝 작업 시퀀스의 결과였거나 false그렇지 않은 경우 반환합니다.
위의문제를 보고 이해가 갔다
입력의 첫출의 8 은 1~8까지 숫자배열 이란 뜻이고
그 다음줄 부터 순서대로[4,3,6,8,7,5,2,1] 의 배열인것이다
입력값은
8 과 [4,3,6,8,7,5,2,1]
그래서 1~8까지의 숫자배열을 스택을 사용해서 [4,3,6,8,7,5,2,1]로 만들라는 문제이다.
2. 풀이
class Solution:
def validateStackSequences(self, pushed: int, popped: List[int]) -> Union[str, List[str]]:
stack = []
result = []
j= 0
for i in range(pushed):
stack.append(i+1)
result.append("+")
while stack and j < len(popped) and popped[j] == stack[-1]:
j += 1
stack.pop()
result.append("-")
if j != len(popped):
return "NO"
return result
먼저 우리가 스택 설명에 써있던 블럭이 담긴그림을 생각하자
우리는 1~8까지의 블럭을 가지고있다. 해당 블럭을 [4,3,6,8,7,5,2,1] 순서대로 넣고 싶다
그러기위해 일단 빈통 stack과 정답을 적을 result를 준비해준다.
이후 stack.pop 숫자를 세어주기 위해 j를 0으로 선언한다.
이제 기본 준비는 끝났다 이제 stack에 블럭을 오름차순으로 일단 넣어주면서 result에 "+"를 넣어준다.
stack에 오름차순으로 넣다가 [4,3,6,8,7,5,2,1] 에 j 번째와 우리가 넣은 블럭의 숫자가 같다면
stack.pop()으로 제거 하고 result에 "-"를 넣어준다.
해당 반복문을 반복하다보면 result의 값이 ['+', '+', '+', '+', '-', '-', '+', '+', '-', '+', '+', '-', '-', '-', '-', '-'] 가 나온다 정답과 일치한다.
3. 느낀점
오늘의 경우 stack 이라는 자료는 잘 이해가 갔다.
하지만 문제를 이해하지못했다 이건 경험의 문제라서 이해하지 못한것같다 경험을 더 쌓으면 될것같다.
