[Swift] 프로그래머스 월간 코드 챌린지 3 공 이동 시뮬레이션

 

 

Problem

 

코딩테스트 연습 - 공 이동 시뮬레이션

---

Solution

 

해당 문제는 효율성이 핵심인 문제였습니다.

 

최대 행과 열이 각 10^9, 최대 쿼리 갯수가 20만으로 어마어마한 크기를 가지고 있어 만약 모든 위치에서 시뮬레이션을 돌릴 경우

 

최대 10^9 * 10^9 * 200000 이 됩니다. 

 

시간초과를 피하기 위해선 목적지에서부터 쿼리의 역순으로 되돌아가면서 가능한 범위가 어디까지인지를

 

체크하는 것이 중요했습니다.

 

이론 설명

 

아래와 같이 목적지와 쿼리가 있다고 가정하겠습니다.( 문제 예시 2번입니다.)

 

가장 먼저 시작할 땐 목적지 그 자체의 범위입니다. (1,0)

 

 

 

여기서 역순으로 실행시켜보면 가장 마지막 쿼리가 위로 이동하는 것이였고 현재 별의 위치의 y가 0이므로

 

쿼리가 실행되기 전 위치는 현재위치 또는 바로 아래 위치였을 것입니다.

 

그러면 목적지에 도달하기 위한 범위가 아래로 확장됩니다.

 

그 다음 쿼리를 실행해보면 왼쪽으로 이동한 것입니다.

 

왼쪽으로 이동했을 때 목적지의 위치가 되기 위해선 (2,0)에서 이동한 것이므로 별의 위치를

 

2,0으로 이동해줍니다.

 

 

그 다음 쿼리는 위쪽으로 세 번 이동한 것입니다.

 

별의 y위치가 0이므로 행을 3줄 더 확장할 수 있지만 예시에서 최대 행의 길이가 2이므로 

 

확장시킬 수가 없습니다.

 

...

 

이런 식으로 주어진 격자 범위 바깥으로 실행되는 쿼리가 있다면 가능한 범위를 확장시켜주고

 

안으로 실행되는 쿼리가 있다면 목적지를 이동시켜줍니다.

 

그렇게 목적지까지 도착할 수 있는 범위를 구해서 반환해줍니다.

 

코드 설명

 

1. 쿼리를 역순으로 실행시킨다.

 

for query in queries.reversed() {
        if !isEdge(query: query) {
            if !checkRightQuery(query: query) { return 0 }
            moveStart(query: query)
        }
        extendEnd(query: query)
    }

 

2. 가장자리인지 아닌지 확인한다.

 

func isEdge(query:[Int]) -> Bool {
    return (query[0] == 0 && range.startX == 0) || (query[0] == 1 && range.endX == range.M) || (query[0] == 2 && range.startY == 0) || (query[0] == 3 && range.endY == range.N)
}

 

3. 가장자리라면 범위를 확장시켜준다.

 

func extendEnd(query:[Int]) {
    switch query[0] {
    case 0:
        range.endX = min(range.M,range.endX+query[1])
    case 1:
        range.startX = max(0,range.startX-query[1])
    case 2:
        range.endY = min(range.N,range.endY+query[1])
    default:
        range.startY = max(0,range.startY-query[1])
    }
}

 

4. 가장자리가 아니라면 이동시켜준다.

 

이동시켜주는 방법은 시작과 끝을 동시에 늘려주면 됩니다.

 

func moveStart(query:[Int]){
    switch query[0] {
    case 0:
        range.startX = min(range.M,range.startX+query[1])
    case 1:
        range.endX =  max(0,range.endX-query[1])
    case 2:
        range.startY = min(range.N,range.startY+query[1])
    default:
        range.endY = max(0,range.endY-query[1])
    }
}

 

5. 올바른 쿼리인지 확인해준다.

 

목적지를 이동해줘야 하는 쿼리가 나왔을 때 주어진 격자보다 더 크다면 잘못된 쿼리이므로 0을 반환해줍니다.

 

(테스트 케이스 33번 34번을 위한 코드)

 

func checkRightQuery(query:[Int]) -> Bool {
    switch query[0] {
    case 0:
        if range.startX+query[1] > range.M { return false }
    case 1:
        if range.endX-query[1] < 0 { return false }
    case 2:
        if range.startY+query[1] > range.N { return false }
    default:
        if range.endY-query[1] < 0 { return false }
    }
    return true
}

 

6. 올바른 쿼리라면 범위를 반환한다.

 

return Int64(range.getArea)

---

Source Code

 

---

P.S

 

문제의 이해를 돕기 위한 시뮬레이션을 보고 시작하는 것이 함정이었다.

 

시뮬레이션을 보면 당연히 순차적으로 실행해서 코드를 짜야할 것 같은 느낌인데 오히려 반대로 생각해야 했다.

 

또한 33번,34번 테스트 케이스는 목적지에 도달하지 않는 잘못된 쿼리를 가지고 있는 것이었다.

 

이건 좀 억지로 엣지 케이스를 만들어낸 것이 아닌가라는 생각이 든다.

 

아무튼 이 문제를 끝으로 이번 년도 목표였던 프로그래머스 3단계 문제를 모두 풀었다!

 

일주일에 한 문제씩만 꾸준히 풀자는 생각으로 조금 오래 걸렸지만 뿌듯하다..

 

프로그래머스 순위도 257등을 달성했고 다음 년도엔 4단계,5단계를 모두 푸는 목표로 달려가야겠다.