BOJ-5430 AC Swift

문제

선영이는 주말에 할 일이 없어서 새로운 언어 AC를 만들었다. AC는 정수 배열에 연산을 하기 위해 만든 언어이다. 이 언어에는 두 가지 함수 R(뒤집기)과 D(버리기)가 있다.

함수 R은 배열에 있는 수의 순서를 뒤집는 함수이고, D는 첫 번째 수를 버리는 함수이다. 배열이 비어있는데 D를 사용한 경우에는 에러가 발생한다.

함수는 조합해서 한 번에 사용할 수 있다. 예를 들어, "AB"는 A를 수행한 다음에 바로 이어서 B를 수행하는 함수이다. 예를 들어, "RDD"는 배열을 뒤집은 다음 처음 두 수를 버리는 함수이다.

배열의 초기값과 수행할 함수가 주어졌을 때, 최종 결과를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. T는 최대 100이다.

각 테스트 케이스의 첫째 줄에는 수행할 함수 p가 주어진다. p의 길이는 1보다 크거나 같고, 100,000보다 작거나 같다.

다음 줄에는 배열에 들어있는 수의 개수 n이 주어진다. (0 ≤ n ≤ 100,000)

다음 줄에는 [x1,...,xn]과 같은 형태로 배열에 들어있는 정수가 주어진다. (1 ≤ xi ≤ 100)

전체 테스트 케이스에 주어지는 p의 길이의 합과 n의 합은 70만을 넘지 않는다.

출력

각 테스트 케이스에 대해서, 입력으로 주어진 정수 배열에 함수를 수행한 결과를 출력한다. 만약, 에러가 발생한 경우에는 error를 출력한다.

내가 푼 풀이

- 해당 기능 R, D를 구현하면 된다.

- 문제는 주어지는 함수가 최대 100,000에 테스트케이스는 최대 100개이므로 O(N^2)의 시간복잡도를 갖는 알고리즘은 아마 시간초과가 날것이다.

- 문자열과는 사이가 나쁜 Swift..

- R: 뒤집는 기능이지만 실제로 뒤집진 않는다(뒤집으면 최대 10만번 뒤집어야함)

- D: 첫째 수를 빼지만 실제로 removefirst()를 하지않는다(배열 특성상 첫번째수를 빼려면 모든 배열의 수를 읽어야함 N번)

 

다양하게 구현하는방법이 있겠지만, 이번문제는 배열의 첫번째인덱스 start,와 마지막인덱스 end를 이용해서 풀었다.

만약 뒤집혀있는배열이라면 end의 문자를 빼야하므로 end-1

뒤집혀있지않는 배열이라면 start+1

모두 빼내면 결국 start...end 범위의 배열만 남는다.

여기서 뒤집는함수 R이 짝수번 발생했다면 뒤집기의뒤집기는 결국 그대로라 그대로 출력하지만

홀수번 발생했다면 end...start 로 출력하면된다.

 

코드로 구현하면 다음과 같다.

import Foundation

// 테스트케이스 수
let T = Int(readLine()!)!

for i in 0..<T {
    // 입력받기
    let p = readLine()!
    let n = Int(readLine()!)!
    var arr = [Int]()
    let strNum = readLine()!
    var str = ""
    
    // 입력받은 배열의문자열을 숫자배열로 변환
    for j in strNum {
        if let num = Int(String(j)) {
            str += String(j)
        } else {
            if str != "" {
                arr.append(Int(str)!)
                str = ""
            }
        }
    }
    
    // start, end
    var start = 0
    var end = arr.count - 1
    // reversed: 뒤집혀있는가?
    // check는 문제에 정의된 조건으로 빈배열일때 첫번째수를 빼려고한다면 error, 이를 판단하기위해
    var reversed = false
    var check = true
    
    // 주어진 함수의문자열 실행
    for k in p {
        // 뒤집혀있는지 확인
        if k == "R" {
            reversed = !reversed
        } else if k == "D" {
            // 배열이 비어있거나, 배열수 이상으로 빼내서 start인덱스가 end를 넘어버렸다면
            if arr.isEmpty || start > end {
                check = false
            } else {
                // 뒤집힘에 따라 인덱스 조절
                if reversed {
                    end -= 1
                } else {
                    start += 1
                }
            }
        }
    }
    // 결과 출력 문자열
    var result = ""
    
    // 빈배열에서 D함수 실행했다면 error
    if check {
        if arr.isEmpty || start > end{
            print("[]")
        } else {
            // 뒤집혀있다면 범위 거꾸로 출력
            if reversed {
                for j in (start...end).reversed() {
                    if j == start {
                        result += "\(arr[j])"
                    } else {
                        result += "\(arr[j]),"
                    }
                }
            } else {
                // 그대로라면 그대로 출력
                for j in start...end {
                    if j == end {
                        result += "\(arr[j])"
                    } else {
                        result += "\(arr[j]),"
                    }
                }
            }
            print("[\(result)]")
        }
    } else {
        print("error")
    }
}