[프로그래머스] 42860 (조이스틱)

#1 오답

#1-1 오만한 풀이

• → 방향으로만 커서를 이동하며 누적된 조작 횟수
• ← 방향으로만 커서를 이동하며 누적된 조작 횟수

이 둘을 비교하여 더 작은 값을 반환하면 되겠다고 생각했다. 문제를 더 깊이 들여다보지 않고 쉽게 가려던 오만함이 부른 결과였다.

 

#1-2 탐욕법 (그리디)

이번엔 문제의 유형을 판단해 보려고 했다. 그리디 알고리즘 아닐까?

• 현재 커서의 위치로부터 가장 가까운, 'A'가 아닌 위치까지 이동한다.
• 해당 위치까지 간 후에, 문자를 변경한다.
• 반복한다.

하지만, 이 문제는 그리디 알고리즘이 아니었다. 그때그때 제일 나은 선택을 하는 것이 최적해로 이어지지 않는다는 말이다. 반례는 아래와 같다.

 

ABBBBBBBBAAAAAAAAAAAAAAAABAAA

맨 끝에 있는 B에 들렸다가 유턴하여 나머지 B들을 방문하는 게 정답이다. 하지만 그리디 알고리즘으로 풀면, 맨 끝에 있는 B를 제일 나중에 방문하게 된다. 지금 최선의 선택이 나중의 선택을 불리하게 만들고 있다. 즉, 그리디 알고리즘으로 풀리는 문제가 아니다.

 

#2 정답

#2-1 완전 탐색

class Solution {
    val alphabets = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
    lateinit var nameCharIndexToAlphabetIndex: (Int) -> Int
    lateinit var nameIndices: IntRange

    var answer = -1

    fun solution(name: String): Int {
        nameCharIndexToAlphabetIndex = {
            val nameChar = name[it]
            alphabets.indexOf(nameChar)
        }
        nameIndices = name.indices

        val changeNeededIndexes = name.withIndex().filter {
            it.value != 'A'
        }.map {
            it.index
        }

        return if (changeNeededIndexes.isEmpty()) {
            0
        } else {
            dfs(changeNeededIndexes)
            answer
        }
    }

    fun dfs(vertexes: List<Int>) {
        val visited = mutableSetOf<Int>()
        vertexes.forEach {
            dfs(it, 0, 0, visited, vertexes)
        }
    }

    fun dfs(
        vertex: Int,
        cursorIndex: Int,
        allCount: Int,
        visited: MutableSet<Int>,
        vertexes: List<Int>
    ) {
        // [1] 방문 기록
        if (visited.contains(vertex)) {
            return
        }
        visited.add(vertex)

        // [2] 이 정점에서 할 일
        var updatedCount = allCount
        // 조이스틱 조작 - 커서 이동
        updatedCount += getMinMoveCount(cursorIndex, vertex, nameIndices)
        // 조이스틱 조작 - 알파벳 변경
        updatedCount += getMinMoveCount(
            0, // 'A'의 인덱스
            nameCharIndexToAlphabetIndex(vertex),
            alphabets.indices
        )

        // [3] 다음 정점 준비 및 이동
        val updatedCursorIndex = vertex
        vertexes.forEach {
            dfs(it, updatedCursorIndex, updatedCount, visited, vertexes)
        }

        // [4] 정답 메모
        if (visited.size == vertexes.size) {
            answer = if (answer == -1) {
                updatedCount
            } else {
                minOf(answer, updatedCount)
            }
        }

        // [5] 백트래킹
        visited.remove(vertex)
    }

    fun getMinMoveCount(a: Int, b: Int, range: IntRange): Int {
        val smaller = minOf(a, b)
        val larger = maxOf(a, b)

        return minOf(
            larger - smaller,
            (smaller - range.first) + (1) + (range.last - larger)
        )
    }
}

그래서 그냥 완전 탐색으로, 무식하게 풀어보았다. 코드 자체는 정답 처리가 되었지만, 뭔가 석연치 않다. 테스트 케이스가 더럽게(?) 나왔더라면, 아마 시간 초과로 인해 오답으로 처리되지 않았을까?

 

#3 얻은 깨알 지식

Char 관련

Char - Char의 결과는 Int다.

 

Char는 참조형 객체처럼 같은 대상을 공유하는 방식이 아니라, (Int처럼) 대입 시 값 자체가 복사된다. 따라서 아래 코드에서 old의 값은 변하지 않는다.

val old = myCharArray[i]
myCharArray[i] = new

 

String[index] 형태로 특정 문자를 (Char 형태로) 읽는 것은 가능하지만, String[index] = ... 와 같은 식으로 값 변경은 할 수 없다. String은 불변(immutable) 객체기 때문이다 (우리가 "abc" + "def" 따위의 연산을 하는 것은 기존 String을 업데이트하는 게 아니라 새 String을 계속 만들어내는 것이다).

 

함수 관련

멤버 함수의 데이터형 표기는, MyClass.(Int, String) -> Boolean처럼 () 앞에 함수가 속하는 클래스를 붙여주면 된다.

 

어떤 함수에 또 다른 함수를 넘기고 싶을 땐, ClassName::MethodName과 같은 형식을 쓰면 된다. 만약 그 함수가 현재 속한 클래스의 멤버 함수라면 this::MethodName로 써도 되고, this를 생략하고 ::MethodName이라고 쓸 수도 있다.

 

함수 관련 - 연습용 코드 스니펫

// 어느 클래스에도 속하지 않는 독립 함수. 이 함수를 호출할 때는 그냥 ::add로 호출하면 된다.
fun add(a: Int, b: Int): Int {
    return a + b
}

fun calculate(
    a: Int,
    b: Int,
    operation: (Int, Int) -> Int // 함수의 데이터형 표시
): Int {
    return operation(a, b)
}

fun main() {
    val result = calculate(
        3,
        5,
        ::add
    )

    println(result) // 8
}

 

코틀린 문법 관련

IntRange에도 filter를 사용할 수 있다.

val sevenIndexes: Array<Int> = myArray.indices.filter {it == 7 }.toTypedArray()

 

minOf()는 각 원소를 변환한 결과 중 최솟값을 반환한다. minBy()는 변환 결과가 가장 작은 원소 자체를 반환한다. 전자는 변환 결과를 기준으로 그 결괏값을 그대로 반환하고, 후자는 변환 결과를 기준으로 그 변환 전 재료를 반환한다 (Of는 값, By는 그걸 만든 원소).

val words = listOf("apple", "kiwi", "banana")
val minLength = words.minOf { word -> word.length } // 4
val shortestWord = words.minBy { word -> word.length } // "kiwi"