Swift) 백준 5430번 AC - G5

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

5430번: AC

전형적인 구현 문제. removeFirst()같은 배열 관련 내장 함수를 사용하면 시간초과가 뜨기에 다른 방식으로 구현해야 했고 명령어의 수 + 수열의 길이의 합이 70만이 최댓값 이였길래 여러 최적화가 필요했다. 기본적으로는 투포인터 알고리즘을 사용했다.

 

풀이

함수 P의 길이라 10만 이하이므로 만약 함수를 일일히 다 실행하면 시간초과가 뜸. 따라서 연속되는 명령어들을 묶는 방식으로 처리.

RRDDDDRD라는 함수가 입력되었을 때, 이를 RR, DDDD, R, D로 나누어서 처리.

 

R 함수의 경우 역순으로 만드는 함수인데, 짝수인 경우 원 상태로 돌아감으로, R이 홀수일 경우 reverse() 함수로 역순으로 배치하지는 않았다. reverse()함수가 시간복잡도가 O(n)이여서 시간 초과가 될것 같기도 하고, reversed()는 여러번 명령어를 받아야 해서 메모리 초과가 뜰 것 같아서 사용 안했다.  isReverse 변수를 두어 true경우 endPoint의 값을 빼도록, false일 경우 startPoint에 값을 더하도록 했다. 

 

D함수의 경우 D함수의 길이값을 이용해 isReverse의 값에 따라 시작, 끝 포인터의 값을 변경하도록 했다.

 

그리고 출력에서 그냥 배열을 출력하면 안되고, 따로 형식을 만들어서 출력해야한다. 

출력 형식이 [1,2,3]이다. 내부 숫자와 ","가 서로 붙어있어야 한다. swift에서는 "," 다음에 띄어쓰기가 들어가니 주의

import Foundation

let t = Int(readLine()!)!

func convertOrder(order: String) -> [String] {
    var result: [String] = []
    var lastOrder = order.first!
    var storage = ""
    for i in order {
        if i != lastOrder {
            result.append(storage)
            lastOrder = i
            storage = "\(i)"
        } else {
            storage.append(i)
        }
    }
    
    if storage != "" {
        result.append(storage)
    }
    
    return result
}

func printArr(arr: [Int]) {
    print("[\(arr.map {String($0)}.joined(separator: ","))]")
}


for _ in 0..<t {
    let p = readLine()!
    let n = Int(readLine()!)!
    var numArr = readLine()!.components(separatedBy: [",","[","]"]).filter {!$0.isEmpty}.map { Int($0)! }
    let orders = convertOrder(order: p)
    var flag = false
    var isReversed: Bool = false
    var startPoint = 0
    var endPoint = numArr.count-1

    for order in orders {
        if order.contains("R") {
            if order.count%2 != 0 {
                isReversed.toggle()
            }
        } else {
            if (endPoint - startPoint+1) >= order.count {
                if isReversed {
                    endPoint -= order.count
                } else {
                    startPoint += order.count
                }
            } else {
                flag = true
                print("error")
                break
            }
        }
    }
    if !flag {
        if startPoint >= n || endPoint < 0 {
            print([])
        } else {
            if isReversed {
                printArr(arr: numArr[startPoint...endPoint].reversed() as [Int])
            } else {
                printArr(arr: Array(numArr[startPoint...endPoint]))
            }
        }
    }
}

참고로 시간은 뒤에서 1등했다.