천소희

기록하는 개발자

업데이트:

카테고리:

/

태그: , ,

지나다니는 길을 ‘O’, 장애물을 ‘X’로 나타낸 직사각형 격자 모양의 공원에서 로봇 강아지가 산책을 하려합니다. 산책은 로봇 강아지에 미리 입력된 명령에 따라 진행하며, 명령은 다음과 같은 형식으로 주어집니다.

  • [“방향 거리”, “방향 거리” … ]

예를 들어 “E 5”는 로봇 강아지가 현재 위치에서 동쪽으로 5칸 이동했다는 의미입니다. 로봇 강아지는 명령을 수행하기 전에 다음 두 가지를 먼저 확인합니다.

  • 주어진 방향으로 이동할 때 공원을 벗어나는지 확인합니다.
  • 주어진 방향으로 이동 중 장애물을 만나는지 확인합니다.

위 두 가지중 어느 하나라도 해당된다면, 로봇 강아지는 해당 명령을 무시하고 다음 명령을 수행합니다.

공원의 가로 길이가 W, 세로 길이가 H라고 할 때, 공원의 좌측 상단의 좌표는 (0, 0), 우측 하단의 좌표는 (H - 1, W - 1) 입니다.

[공원 산책의 이미지]https://user-images.githubusercontent.com/62426665/217702316-1bd5d3ba-c1d7-4133-bfb5-36bdc85a08ba.png

공원을 나타내는 문자열 배열 park, 로봇 강아지가 수행할 명령이 담긴 문자열 배열 routes가 매개변수로 주어질 때, 로봇 강아지가 모든 명령을 수행 후 놓인 위치를 [세로 방향 좌표, 가로 방향 좌표] 순으로 배열에 담아 return 하도록 solution 함수를 완성해주세요.

접근

  1. 공원 맵을 2차원 배열로 설정
  2. 시작점에서부터 명령을 차례로 실행
  3. 공원 범위 밖으로 벗어나거나, 장애물을 만나면 다음 명령으로 건너뜀
  4. 마지막 위치를 출력

해결

class Solution {
    fun solution(park: Array<String>, routes: Array<String>): IntArray {
        val dog = intArrayOf(0, 0)

        val map = mutableMapOf(
            "E" to intArrayOf(0, 1),
            "W" to intArrayOf(0, -1),
            "S" to intArrayOf(1, 0),
            "N" to intArrayOf(-1, 0)
        )

        var y = 0
        for (row in park) {
            var x = 0
            for (ele in row) {
                if (ele == 'S') {
                    dog[0] = y
                    dog[1] = x
                }
                x += 1
            }
            y += 1
        }

        for (route in routes) {
            val command = route.split(" ")
            val go = command[1].toInt()

            var curx = dog[1]
            var cury = dog[0]
            var ok = true

            for (i in 1 .. go) {
                curx += map[command[0]]?.get(1) ?: 0
                cury += map[command[0]]?.get(0) ?: 0

                if (cury >= park.size || curx >= park[0].length || curx < 0 || cury < 0) {
                    ok = false
                    break
                } else if (park[cury][curx] == 'X') {
                    ok = false
                    break
                }
            }

            if (ok) {
                dog[0] = cury
                dog[1] = curx
            }
        }
        return dog
    }
}

처음에는 N,E,W,S 에 따라 if문으로 분기처리하여 탐색을 시도하였으나 테스트 케이스에서 시간초과가 발생하였다.

그래서 몇가지 질문글을 찾아보니 if문으로 분기 처리하지 말고 어떤 상황이던 똑같은 로직이 돌아갈 수 있도록 해야한다는 답변 글을 보았다.

그리하여 map으로 방향을 key, 이동값을 value로 지정하여 동일로직으로 변경하니 시간초과 없이 통과 되었다

아무래도 이동 방향이 많아지면 무조건 4번의 분기를 거쳐야하니 거기에서 오는 시간복잡도가 상당했던거 같다.

참고