✅ stack

문제

링크

풀이

1. 문제 접근

스택에 push하는 순서는 반드시 오름차순만 가능하므로 push는 1에서 n까지의 수를 순서대로 stack에 push 한다.
push 하다가 stack의 top이 나올 순서가 되면 pop해준다.

2. 자료구조 선택과 그 이유

문제에서 스택을 예를 들어 설명했으므로 stack 사용

3. 문제 해결 로직 (풀이법)

스택에 push하는 순서는 반드시 오름차순만 가능하므로 push는 1에서 n까지의 수를 순서대로 stack에 push 한다.
push 하다가 stack의 top이 나올 순서가 되면 pop해주고 나와야 하는 숫자가 다 나왔다면 그다음 넣다가 잠깐 멈췄던 수를 마저 push한다.

의사코드

j=0
for(i : 1 ~ n){
	stack.push(i)
    vector.push_back('+') // vector에 필요한 연산을 저장
    
    whlie(!stack.empty){ // arr는 입력된 수열
    	if(arr[j] == stack.top){
			vector.push_back('-')
			stack.pop
            j++
        }
    }
    
    if(!stack.empty) print(NO)
    else print(vector)
}

4. 시간 복잡도 분석

O(N^2)

5. 문제에서 중요한 부분

stack에 넣을 때마다 이전 상태에서 나와야 할 수를 판별하는게 중요한 문제였다.