[Swift] 백준_AC(5430)

문제

 

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

5430번: AC

 

 

 

풀이

 

reversed()의 시간복잡도가 O(1)이기 때문에 reversed()를 이용해서 구현해봤는데 시간초과가 나왔다. 

 

찾아보니 포인터로도 할 수 있을 것 같아 head와 tail 변수를 포인터로 생각하여 구현하였다.

어차피 뽑아내는 것은 앞에서만 뽑아내므로 reversed를 나타내는 변수를 두어 뒤집어진 상태에서는 tail을 하나 감소, 기본 상태에서는 head를 1 더해주었다.

 

이때 생각해야할건 tail보다 head가 큰 상태에서 D가 다시 나온다면 비어있는 상태에서 삭제하는 것이므로 error를 출력하도록 하였고, 명령어를 전부 수행한 뒤에도 head가 tail보다 크다면 원소 하나를 지웠거나 원래 []가 들어온 경우만 있으므로 그대로 []를 출력하도록 하였다.

import Foundation

let caseCount = Int(readLine()!)!
outer: for _ in 0..<caseCount {
    let command = readLine()!
    let _ = Int(readLine()!)!
    var numbers = readLine()!.dropFirst().dropLast().split(separator: ",")
    
    var isR = false
    var head = 0
    var tail = numbers.count - 1
    
    for char in command {
        if char == "R" {
            isR.toggle()
        } else {
            if tail < head {
                print("error")
                continue outer
            }
            if isR {
                tail -= 1
            } else {
                head += 1
            }
        }
    }
    if head > tail {
        print("[]")
    } else {
        if isR {
            numbers = numbers[head...tail].reversed()
        } else {
            numbers = Array(numbers[head...tail])
        }
        print("[\(numbers.joined(separator: ","))]")
    }
}

 

 

____________________________________________________________________________________________________

 

dropFirst()와 dropLast()로 하나씩 제거할 수 있는 것을 알게 되었다.

 

reversed를 이용하더라도 투포인터 같은 방법이 더 적게 걸릴 수도 있으므로 생각해야한다.