1874 스택 수열

Today 12/24

스택 수열 (My Code)

let N = Int(readLine()!)!
var input = 1
var stack = [Int]()
var result = [Int]()
var output = [String]()

for _ in 1...N {
    result.append(Int(readLine()!)!)
}

while **result != []** {
    if stack.last == result[0] {
        stack.removeLast()
        **result.remove(at: 0)**
        output.append("-")
    } else {
        stack.append(input)
        if input > N {
            output = ["NO"]
            break
        }
        input += 1
        output.append("+")
    }
}
print(output.joined(separator: "\n"))

스택을 이용한 문제여서 배열을 통해 스택을 구현했다.

처음에는 input, stack, output이렇게 세 개의 배열로 구성했는데, 생각해보니 input의 경우에는 1부터 차례대로 들어가니까 그냥 int로 생성하고 ++해도 될 것 같아서 int로 대체했다.

NO가 출력되는 부분이 헛갈려서 반복문 다음에 그냥 조건문으로 처리해줄까 하다가 너무 조잡해질 것 같아서 최대한 반복문 안에서 처리하려했다.

NO가 출력될 때는 pop과는 관련이 없고 push해야할 때 push할 input이 없는 상황밖에 없다는 걸 깨닫았다.

그렇게 해결했는데, 시간이 너무 많이 걸렸다. 스택을 다루는 방법때문이라고 판단하고, 스택을 직접적으로 건드리는 작업을 최소화했다.

let N = Int(readLine()!)!
var input = 1
var stack = [Int]()
var result = [Int]()
var output = [String]()
var index = 0

for _ in 1...N {
    result.append(Int(readLine()!)!)
}

while **index <= N-1** {
    if stack.last == result[0] {
        stack.removeLast()
        **index += 1**
        output.append("-")
    } else {
        stack.append(input)
        if input > N {
            output = ["NO"]
            break
        }
        input += 1
        output.append("+")
    }
}
print(output.joined(separator: "\n"))

그렇게 보완한것이 직접적으로 output을 건드리지 않고, output에 index(pivot)를 달아서 현재 조건문이 어디를 바라보고 있는지 알 수 있도록 했다.

while 반복문 또한 output를 항상 빈 배열인지 확인하는 것 대신에 index를 통해서 output이 완료되었는지를 확인했다.

예상으로는 while에서 매 번 비교를 할 때마다 시간을 잡아먹은 것 같다.