글 읽기 - [Swift] 33%에서 시간초과가 뜹니다

phe5389 2년 전 0

어디서 시간을 더 줄일 수 있을까요?..

import Foundation

class Solution {
    
    struct TestSet {
        let command: String
        let p: Int
        let arr: [Int]
    }
    
    var testSet = [TestSet]()
    
    init() {
        input()
        
    }

    func input() {
        let tc = Int(readLine()!)!
        
        for i in 0..<tc {
            var read = [String]()
            for _ in 0..<3 {
                read.append(readLine()!)
            }
            var arr = read[2].replacingOccurrences(of: "[", with: "")
            arr = arr.replacingOccurrences(of: "]", with: "")
            testSet.append(TestSet(command: read[0],
                                   p: Int(read[1])!,
                                   arr: arr.split(separator: ",")
                                    .compactMap{Int($0)})
            )
        }
        sol()
    }
    
    func sol() {
        for test in testSet {
            
            let command = Array(test.command)
            var arr = test.arr
            var flag = false // error를 위한 flag
            var i = 0
            var reverseCheck = false// reverse check를 위한 Bool
            
            while i < command.count {
                if command[i] == "R" {// 뒤집기
                    reverseCheck = !reverseCheck
                } else if command[i] == "D" {
                    if arr.count > 0 {
                        if !reverseCheck {//reverse 상태 아님
                            arr.removeFirst()// 앞에서 지워줌
                        } else {//reverse 상태임
                            arr.removeLast()// 뒤에서 지워줌
                        }
                    } else {
                        flag = true//remove할게 없음
                        break
                    }
                }
                i += 1
            }
            
            if flag == true {
                print("error")
            } else {
                if !reverseCheck {//reverse(=false) 안됐음
                    print(arr)
                } else {// reverse 됐음
                    let ans = arr.reversed().compactMap{ Int($0) }
                    print(ans)
                }
            }
            
        }
    }
}

Solution()

wapas 2년 전 0

52번째 줄

arr.removeFirst()// 앞에서 지워줌

에서 removeFirst() 메소드의 시간복잡도는 O(N)입니다.

따라서 func sol() 함수의 시간복잡도는 O(N^2)이므로 시간 초과가 발생합니다.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

[Swift] 33%에서 시간초과가 뜹니다

phe5389 2년 전 0

wapas 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말