BOJ10158 개미

Overview

• Problem: https://www.acmicpc.net/problem/10158
• TimeComplexity: O(n) 혹은 O(1)
• Type: 시간복잡도
• Git: https://github.com/kylelab/algorithms/blob/main/src/boj/BOJ10158.kt

Solution

Solution1 (시간 초과)

• x축과 y축을 나눠서 생각해봤을때, x축은 w까지 이동하면 그 뒤에는 -1씩 이동하고 그 외에는 +1씩 이동한다.
• 동일하게 y축은 h까지 이동하면 그 다음부터는 -1씩 이동하고 그 외에는 +1씩 이동한다.
• 이 풀이는 시간 초과로 실패한다.
  • 그 이유는 시간 복잡도가 for문이 하나이기때문에 O(t)이 되는데 이 시간t의 범위가 1 ≤ t ≤ 200,000,000 으로 2초가 넘는 시간이 걸리기 때문이다. 

private fun solution1(
    p: Int,
    q: Int,
    t: Int,
    w: Int,
    h: Int
): Pair<Int, Int> {
    var currX = p
    var currY = q

    var deltaX = 1
    var deltaY = 1
    for (i in 1..t) {
        if (currX == w) {
            deltaX = -1
        } else if (currX == 0) {
            deltaX = 1
        }

        if (currY == h) {
            deltaY = -1
        } else if (currY == 0) {
            deltaY = 1
        }

        currX += deltaX
        currY += deltaY
    }
    return Pair(currX, currY)
}

 

Solution2

• x축과 y축의 움직임을 아예 분리해서 생각해보자.
• x축만 놓고 보면 2 * w 주기로 계속 반복되는 것을 알 수 있다. 
  • p에서 오른쪽으로 w까지 이동하고 거기서부터 다시 왼쪽으로 0까지 이동, 다시 오른쪽으로 p만큼 이동하면 자기자신(원점 p)으로 돌아온다. 
• y축도 동일하게 2 * h 주기로 계속 반복된다. 
• 그렇기때문에 최종적으로 x축이 가야하는 시간 timeW는 시간 t를 2 * w로 나눈 나머지가 되게 된다.  
  • timeW = t % (2 * w)
  • timeH = t % (2 * h)
  • 시간 t의 큰 범위와 상관없이 이 timeW, timeH만큼만 이동시키면 정답을 풀이할 수 있다. 
    
    • Solution1번과 달리 이동시켜야하는 시간이 timeW, timeH로 다르기때문에 분리해서 계산한다.
• 이 경우 시간복잡도는  0 <= timeW <= 2*w, 0 <= timeH <= 2*h의 범위를 가지기 때문에 O(max(w,h))로 Solution1번보다 훨씬 빠르게 처리할 수 있다. 

private fun solution2(
    p: Int,
    q: Int,
    t: Int,
    w: Int,
    h: Int
): Pair<Int, Int> {
    var currX = p
    var currY = q

    var deltaX = 1
    var deltaY = 1

    val timeX = t % (2 * w)
    for (i in 1..timeX) {
        if (currX == w) {
            deltaX = -1
        } else if (currX == 0) {
            deltaX = 1
        }
        currX += deltaX
    }

    val timeY = t % (2 * h)
    for (i in 1..timeY) {
        if (currY == h) {
            deltaY = -1
        } else if (currY == 0) {
            deltaY = 1
        }
        currY += deltaY
    }
    return Pair(currX, currY)
}

 

Solution3

• 2*w 주기로 동작하는 것을 알았기때문에 식을 도출해서 해결할 수 있다. 
• P부터 시작이 아니라, 0부터 시작하도록 옮겨보면,
• P에서 출발해 T시간 후 위치 => 0에서 출발해 (P + T)시간 후 위치가 되게 된다. 
• x(t): t시간 뒤에 x좌표
  • x(t) = t % (2 * w)
• x(p+t): p+t시간 뒤에 x좌표
  • x(p + t) = (p + t) % (2 * w)
• 결론적으로 
  • currentX = (P + T) % (2 * w)
  • (0 <= currentX < 2w)
• 문제는 x(t)가 w보다 클 수 없기 때문에 반대로 가야한다.
  • x(p + t)가 w보다 크다면 그 만큼 -를 해줘야한다. 
• if(currentX <= w) currentX
• if(currentX >= w) w - (currX - w)

private fun solution3(
    p: Int,
    q: Int,
    t: Int,
    w: Int,
    h: Int
): Pair<Int, Int> {
    var currentX = (p + t) % (2 * w)
    var currentY = (q + t) % (2 * h)

    if (currentX > w) {
        currentX = w - (currentX - w)
    }

    if (currentY > h) {
        currentY = h - (currentY - h)
    }

    return Pair(currentX, currentY)
}