[백준] Swift AC implementation, 문자열

문제 :

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

5430번: AC

 

풀이 :

명령어 R과 D에 대해 각각 뒤집기, 첫 문자를 버리는 것을 메소드를 적용하면 된다. 하지만 R에 대해 문자열 reverse를 적용하면 시간복잡도가 O(n)이 걸리므로 

* 근데 queue 자료구조를 직접 구현할땐 reverse가 O(1)이라고 했는데 잘 모르겠다 .. 

R 명령어가 등장할때, isReverse.toggle()로 뒤집혔는지 아닌지를 프로퍼티로 저장한다.

그리고 D명령어를 수행할때 역시 removeFirst()는 시간복잡도가 O(n)이 걸리므로 head와 tail 포인터로 유효한 문자열의 인덱스 범위를 저장한다. 그러면 시간 복잡도 문제가 해결된다 !!

 

Swift 코드 : 

//
//  main.swift
//  SOMA👩🏻‍💻
//
//  Created by JoSoJeong on 2022/04/07.
//

import Foundation
var Tcase = Int(readLine()!)!
func do_command(_ n: Int, _ command: String, _ array: [Int]) -> String {
    var head = 0, tail = n-1
    var isReversed = false

    let arr:[Int] = array

    for i in command {
        if i == "R" {
            isReversed.toggle()
        }else if i == "D" {
            if head > tail {
                return "error"
            }
            if isReversed {
                tail -= 1
            }else {
                head += 1
            }
        }
    }
    
    if head > tail {
        return "[]"
    }else {
        if !isReversed {
          return "[" + arr[head...tail].map { String($0)}.joined(separator: ",") + "]"
        }else {
            return "[" + arr[head...tail].reversed().map { String($0)}.joined(separator: ",") + "]"
        }
    }
    
}

for _ in 0..<Tcase {
    let command = readLine()!
    let n = Int(readLine()!)!
    let arr = readLine()!.dropFirst().dropLast().split(separator: ",").map{Int(String($0))!}
    
    print(do_command(n, command, arr))
}

extension Array where Element: Hashable {
    mutating func remove(values: [Element]) {
        let set = Set(values)
        removeAll { set.contains($0) }
    }
}

 

시간초과의 흔적 ..