[백준] (Swift) 1874번 - 스택 수열

 

문제 링크

https://www.acmicpc.net/problem/1874

반응형

1874번: 스택 수열

 

나의 풀이

문제를 이해하는데 시간이 조금 걸렸지만, 이해하고 나니 어려운 문제는 아니었다.

• 문제의 첫번재 입출력을 예시로 들어보았다. (8 4 3 6 8 7 5 2 1)
• 입력을 해석해보면, 처음 숫자 8을 기준으로 8 번 입력 받을거고, 수열은 4,3,,,, 이렇게 될 것이다. 라는 의미이다.
• 따라서 n을 8 로 두고 for 문을 이용하여 뒤에 8번 입력을 받자.
• 그리고 문제를 해석해보면, stack을 이용해서 4,3,6,8,7,5,2,1 이라는 수열을 만들고 싶은데, stack이 어떻게 동작하는지를 알고싶다는 뜻이다. 따라서 오름차순으로 구성가능한 빈스택을 만들어주자. (stack 배열 생성)
• 그리고 stack의 동작방식을 알 수 있도록 answer라는 배열을 만들어 +.- 를 넣어줄것이다.
• ---------------------------------------------------------------------------------
• 수열의 처음 수로 4가 오기 위해서는 다음과 같은 과정이 필요하다.
  • stack은 Last in First Out 정책을 따르기 때문에 [1, 2, 3, 4] 라는 stack이어야만 4가 출력 가능하다. (맨 뒤에있는 수가 가장 처음에 출력되어야하므로)
  • 따라서 count 변수를 만들어 하나씩 더해가면서 stack에 넣어주고, [1,2,3,4] stack을 만들어주었다. 마찬가지로 stack에는 1,2,3,4 라는 수가 push되는 것이기 때문에 동시에 + 를 answer배열에 넣어주었다.
  • 그리고 한 번 스택으로 들어간 숫자는 중복되지 않는다고 하였기에 +=1 씩 count에 더해주었다.
• 처음수로 4를 뽑아내기 위해 stack에서 4를 뽑아버릴 것이다.
  • stack에서 popLast() 메서드를 통해 4를 뽑아주었다. 이제 남은 stack = [1,2,3] 이다.
  • 마찬가지로 stack의 동작을 출력해야하는 answer 배열에 -를 넣어준다. 지금 answer=[+,+,+,+,-]이다.
• 다음 수열로 와야하는 수는 3이다. 3은 지금 바로 stack에서 추출이 가능하다. 
  • count는 5가 되었고, num은 3이니까 while 조건은 만족하지 않아 거치지 않는다. (push를 건너뛴다.)
  • if 문으로 가는데, stack.last = 3 이고 num=3 이니, 같기 때문에 if 문을 통과하며 pop 과정을 수행한다.

이런식으로 반복하면서 동작을 하게끔 코드를 아래처럼 구성했다. 

//push : + , pop : -, 불가능한 경우 : NO
//처음 수 n , 이후 n 번 입력 받음

import Foundation

let n = Int(readLine()!)!

var count = 1
var stack: [Int] = []
var answer: [String] = []


for _ in 0..<n {
    
    let num = Int(readLine()!)!
    
    while count <= num {
        stack.append(count)
        answer.append("+")
        count += 1
    }
    
    if stack.last == num {
        stack.popLast()
        answer.append("-")
    } else {
        print("NO")
        exit(0)
    }
    
}

print(answer.joined(separator: "\n"))