프로그래머스 Level 2 조이스틱

조이스틱

출처: 프로그래머스

https://school.programmers.co.kr/learn/courses/30/lessons/42860

프로그래머스

이 포스트는 광고 게시가 없는 비상업적, 비영리적 포스트임을 알려드립니다.

 

이 문제는 매우 애를 먹은 문제였습니다.

그리디로 하려니 제 머리로는 최소한의 규칙이 보이지 않더군요..

처음에는 이렇게 풀었습니다.

현재 index 기준에서 A가 아닌 문자가 가장 가까이에 있는 곳으로 당장 출발하게 했습니다. 그리디니까요.

그런데 이상하게 안되더군요.. 좌우로 차이가 같은 경우가 발생하면 두 개로 나누어 출발하게 해야 하나 싶었습니다.

규칙 한 개가 아닌 두 개의 규칙으로 그리디를 적용해야 하나 싶었습니다. 하지만 떠오르지 않더군요.

 

잠시 멈추고 새로 다시 생각해 보았습니다.

만약 오른쪽으로만 먼저 가보고 오른쪽으로 계속 가다가 하나씩 왼쪽으로 가면?

방향 전환을 해야 하는 부분이 3곳이라면

 

오른쪽 오른쪽 오른쪽 

오른쪽 오른쪽 왼쪽 

오른쪽 왼쪽 오른쪽

오른쪽 왼쪽 왼쪽

 

왼쪽 오른쪽 오른쪽

왼쪽 오른쪽 왼쪽

왼쪽 왼쪽 오른쪽

왼쪽 왼쪽 왼쪽

 

이런 생각이 들어 제한사항을 확인했습니다.

 

name의 길이는 20 이하. 가능하겠구나.

그래서 dfs로 모든 갈 수 있는 경로를 확인해 보고 이렇게 답을 구해야겠다 싶었습니다.

 

아래에 코드가 있습니다.

 

class Solution {
    var move = Int.MAX_VALUE
    fun solution(name: String): Int {
        var answer = 0
        val b = BooleanArray(name.length) { true }
        var limit = 0
        var cnt = 0
        var depth = 0
        name.forEachIndexed { index, c ->
            if (c != 'A') {
                b[index] = false
                limit++
            }
        }
        println(b.toList())
        if (!b[0]) {
            b[0] = true
            cnt = findUpDown(name[0])
            depth = 1
        }
        answer = dfs(name, depth, limit, 0, cnt, 100000000, b)
        return answer
    }

    //
    fun dfs(
        name: String,
        depth: Int,
        limit: Int,
        index: Int,
        cnt: Int,
        min: Int,
        visited: BooleanArray
    ): Int {
        var m = min
        return if (depth == limit) min(m, cnt)
        else {
            for (i in 0..1) {
                val p = findRightLeft(name, visited, index, i)
                visited[p.first] = true
                m = dfs(name, depth + 1, limit, p.first, cnt + p.second, m, visited)
                visited[p.first] = false
            }
            m
        }
    }

    fun findRightLeft(name: String, visited: BooleanArray, start: Int, direction: Int): Pair<Int, Int> {
        var index = if(direction == 0) start + 1 else start - 1
        var cnt = 1
        var p = Pair(0,0)
        for(i in 1 until name.length) {
            if (direction==0 && index >= name.length) index = 0
            if (direction==1 && index < 0) index = name.length - 1
            if (name[index] != 'A' && !visited[index]) {
                p =Pair(index, cnt + findUpDown(name[index]))
                println(p)
                break
            }
            cnt++
            if(direction==0) index++ else index--
            println("3 index: $index")
            println()
        }
        return p
    }

    private fun findUpDown(c: Char): Int {
        val up = c.code - 'A'.code
        val down = 'Z'.code - c.code + 1
        return min(up, down)
    }
}

 

코트가 약간 길고 아주 살짝 복잡합니다. 아주 살짝

천천히 하나씩 보겠습니다.

 

큰 줄기를 설명하고 각 함수들을 설명드리겠습니다.

1. 먼저 solution 함수에서 A가 아닌 문자가 몇 개인지 확인하고 BooleanArray를 만들었습니다.

2. 만약 문자열 0번의 char 가 A가 아니라면 먼저 선처리해 줍니다.

3. 이제 dfs를 돌려 가장 작은 min 값을 찾습니다.

 

크게 3개의 과정이 solution에서 실행됩니다.

 

dfs에서는 어떤 과정이 있냐면

fun dfs(
    name: String,
    depth: Int,
    limit: Int,
    index: Int,
    cnt: Int,
    min: Int,
    visited: BooleanArray
): Int {
    var m = min
    return if (depth == limit) min(m, cnt)
    else {
        for (i in 0..1) {
            val p = findRightLeft(name, visited, index, i)
            visited[p.first] = true
            m = dfs(name, depth + 1, limit, p.first, cnt + p.second, m, visited)
            visited[p.first] = false
        }
        m
    }
}

depth는 A가 아닌 문자를 찾는 경우 늘어나는 매개변수입니다.

depth를 limit와 비교하는데 limit는 solution 함수에서 계산해 문자열에서 A가 아닌 경우의 총개수를 넘겨줍니다. 

그래서 depth가 limit이면 return 하게 합니다.

그리고 for문은 0부터 1까지인데

0일 때는 오른쪽으로 가고 1일 때는 왼쪽으로만 간다 생각하고 넘겨줍니다.

일종의 스위치 값입니다.

findRightLeft는 오른쪽 왼쪽으로 방향에 따른 문자의 이동 횟수와 위아래 이동 횟수를  합친 값과 그때의 index를 반환해 줍니다. 

반환된 index를 방문처리하고 다시 index 순간을 기준으로 dfs를 돌려 탐색합니다.

 

---

1. findUpDown

A를 기준으로 위아래로 몇 번을 움직여야 하는지 최솟값을 구해주는 함수입니다.

down은 Z에서 어떤 문자 ex N이라고 하면 Z부터 N까지 구하고 +1 해서 A에서 밑으로 내려가면 몇인지 구합니다.

A에서 위로 가는 Up과 밑으로 가는 Down을 구해 둘 중에 작은 값을 반환합니다.

fun findUpDown(c: Char): Int {
    val up = c.code - 'A'.code
    val down = 'Z'.code - c.code + 1
    return min(up, down)
}

 

2. findRightLeft

findRightLeft 함수는 

매개변수로 name , visited , start , direction 이 있습니다.

name = 탐색할 문자열

visited = 방문 여부 배열

start = 직전에 A가 아니어서 바꾼 문자열의 index입니다.

direction = 오른쪽, 왼쪽을 나타냅니다. 

fun findRightLeft(name: String, visited: BooleanArray, start: Int, direction: Int): Pair<Int, Int> {
    var index = if(direction == 0) start + 1 else start - 1
    var cnt = 1
    var p = Pair(0,0)
    for(i in 1 until name.length) {
        if (direction==0 && index >= name.length) index = 0
        if (direction==1 && index < 0) index = name.length - 1
        if (name[index] != 'A' && !visited[index]) {
            p =Pair(index, cnt + findUpDown(name[index]))
            println(p)
            break
        }
        cnt++
        if(direction==0) index++ else index--
        println("3 index: $index")
        println()
    }
    return p
}

 

 

direction은 0일 때 오른쪽을 나타내고 1일 때 왼쪽을 나타냅니다. 

그래서 0일 때는 오른쪽으로 가니까 index를 index++하고 1일 때는 왼쪽으로 가서 index--합니다.

 

direction이 0이면 index를 하나 올립니다. 

만약에 하나 올렸는데 index가 name.length를 넘으면 0으로 바꾸고 

direction이 1일 때는 왼쪽으로 가서 하나 내리는데 그게 0보다 작으면 index를 name의 마지막 원소 length-1 값으로 바꿉니다. 

 

if (name[index] != 'A' && !visited[index]) {
    p =Pair(index, cnt + findUpDown(name[index]))
    break
}

바뀐 index 값이 방문한 적이 없고 A가 아니라면 Pair 값으로 이때의 index값과 index가 되기 위해 몇 번 움직였는지 횟수를 가진 cnt + index에서 A가 아닌 문자열이 위아래 값에서 최소 얼마나 움직이는지 값을 더해 반환합니다.

 

간단하게 정리하면 findLeftRight는 좌 우 둘 중에 하나로 가다가 A가 아닌 경우를 발견하면 아닌 경우까지 몇 번 움직였는지 cnt로 기억하고 그 문자가 A에서 위아래로 몇 번 움직였는지 최솟값을 반환합니다.

 

설명이 좀 부실한 것 같습니다. 다시 다듬어서 올리겠습니다. 읽어주셔서 감사합니다.