백준 10811 바구니 뒤집기 - [알고리즘] [코틀린]

문제 내용

 

문제 분석

1. 1~N의 번호가 매겨진 n개의 바구니가 있다.

2. "x y" 형태의 명령이 m번 들어온다.

3. x~y바구니를 역순으로 배치한다.

 

아이디어

1. 크기 n+1인 배열을 만들어 1~n까지 바구니가 있다고 생각한다. (index: 위치, value: 바구니 번호)

2. "x y"가 들어오면 순서대로 stack에 넣은 후 빼서 순서를 역전시킨다.

 

풀이

2가지 방법이 더 생각나서 추가로 적용해 봤다.

import java.util.LinkedList


fun main() {
    val br = System.`in`.bufferedReader()
    // 한줄을 입력받아 공백을 기준으로 List<Int>로 반환
    fun getInput() = br.readLine().split(' ').map { it.toInt() }

    val input = getInput()
    val n = input[0]
    val m = input[1]

    // n+1크기 intArray에 각 값을 본인의 index로 세팅
    // index는 위치, value는 바구니의 번호를 의미
    val arr = IntArray(n+1){ it }

    // start~end를 역순으로 바꾸는 함수들
    fun reverse1(start: Int, end: Int) {
        // 172ms
        // IntArray 기본 확장함수 이용
        arr.reverse(start, end+1)
    }
    fun reverse2(start: Int, end: Int) {
        // 144ms
        // stack 이용
        val stack = LinkedList<Int>()
        for(i in start..end) {
            stack.addLast(arr[i])
        }
        for(i in start downTo end) {
            arr[i] = stack.removeLast()
        }
    }
    fun reverse3(start: Int, end: Int) {
        // 144ms
        // 배열을 전부 deepCopy한 후 값을 적용하는 방식 이용
        val tmpArr = arr.copyOf()
        for(i in 0..end-start) {
            arr[start+i] = tmpArr[end-i]
        }
    }

    repeat(m) {
        val tmp = getInput()
//        reverse1(tmp[0], tmp[1])
//        reverse2(tmp[0], tmp[1])
        reverse3(tmp[0], tmp[1])
    }

    // 정답 출력
    val sb = StringBuilder()
    for(i in 1 until arr.size) {
        sb.append(arr[i]).append(' ')
    }
    sb.dropLast(1)
    print(sb.toString())
}

 

추가설명 - IntArray.reverse가 가장 느린 이유

배열을 복사 후 값을 적용하는 방식

- IntArray.copyOf는 내부적으로 새로운 int[]를 만들고 값을 복사함.

- worstCase의 경우 배열 초기화(N) + 역순으로 값 할당(N) = O(N)의 시간 복잡도를 가짐

 

 

stack을 이용하는 방식

- worstCase의 경우 stack에 push(N) + 빼면서 값 할당(N) = O(N)의 시간 복잡도를 가짐

 

 

IntArray.reverse를 이용하는 방식

- worstCase의 경우 N/2 * (for문 안에서 값 할당)3번 = O(N)의 시간 복잡도를 가짐

 

 

 

 

 

 

 

 

결론

- 빅오 표기법으로는 모두 linear한 시간 복잡도를 가지지만, worstCase에서 IntArray.reverse 함수가 (3N)/2의  시간 복잡도를 가지기 때문이라고 생각.

- 하지만, 새로운 배열/Stack을 만들지 않고 1개의 변수만 추가로 사용하므로 메모리 측면에서는 이득이 있다.