yubin

I am an amazing person.

카테고리 (펼쳐보기)

LV.1 달리기 경주

이번에는 코테 준비겸 IDE없는 환경에서 문제를 풀어보고자 프로그래머스 문제를 풀어보았다.

이번에 푼 문제는 ‘달리기 경주’ 라는 문제로 현재 순위에서 이름의 호명이 있을때 앞 선수를 추월하여 callings배열의 호명이 끝났을 때 등수대로 선수의 이름을 출력하는 문제였다.

첫번째 시도는 아래와 같이 코드를 짰다.

fun solution(players: Array<String>, callings: Array<String>): Array<String> {
    
    var answer: Array<String> = arrayOf<String>()
    val player=players.toMutableList()
    
    callings.forEach{
        val index=player.indexOf(it)
        val temp=player[index]
        player[index]=player[index-1]
        player[index-1]=temp
        
    }
    answer=player.toTypedArray()
    return answer
}

IDE없이 코딩을 하려니 아주 헷갈리고 번거로워서 아래에 사용한 함수에 대한 설명을 적어두기로 했다.

  • indexOf(value) : 해당 컬렉션을 탐색하여 해당 value 를 가진 첫번째 index를 찾아 반환, 없을시 -1 반
  • toTypedArray() : 컬렉션을 array로 변환

이 함수에서는 callings를 하나씩 반복하며 아래 절차에 따라 등수를 변경한다.

  1. 호명된 선수의 인덱스 찾기
  2. 호명된 선수를 임시로 저장
  3. 현재 등수에 앞 등수 선수를 넣기
  4. 앞 등수에 호명된 선수 넣기

이렇게 구현하고 코드 실행을 했을 때는 코드가 잘 실행됨을 알 수 있다.

그러나 채점하기를 누른 후에는 아래와 같은 결과를 얻었다.

장렬하게 시간초과를 먹어버렸다..🥲

정말 이럴 때 마다 코틀린 말고 실행 시간이 빠른 다른 언어를 쓸까 생각이 들지만 이렇게 약간만 비효율적으로 짜도 실패 해 버리는 게 오히려 실력 향상 측면에서는 좋지 않나 싶다.

코틀린 고수가 되는 그날을 위해 열심히 버티기로 한다.😂

🚀 Advanced

이부분은 문제 질문을 뒤지다가 해답을 찾았다.

파이썬 시간초과에 대한 질문글이 있었는데 Map을 사용하면 실행시간을 줄일 수 있다는 것이었다.

반대로 생각해보면 위 코드에서 가장 비효율적인 부분은 val index=player.indexOf(it) 이 부분이었다.

indexOf() 또한 반복문을 통해 리스트를 탐색하는 함수인데 이부분에 대한 이해가 없이 접근을 하다보니 비 효율적인 부분을 찾아내는데 시간이 좀 걸렸다.😓

겸사겸사 여기에 대해서도 제대로 공부해두면 좋을것같아서 아래에 잠깐 정리해뒀다.

indexOf() 작동 원리

이 코드가 맞는지는 모르겠지만 아무튼 공식문서에서 열심히 찾아본 결과 아래와 같은 소스코드를 찾을 수 있었다.

github : kotlin_indexOf()

public fun <@kotlin.internal.OnlyInputTypes T> Iterable<T>.indexOf(element: T): Int {
    if (this is List) return this.indexOf(element)
    var index = 0
    for (item in this) {
        checkIndexOverflow(index)
        if (element == item)
            return index
        index++
    }
    return -1
}

public fun <@kotlin.internal.OnlyInputTypes T> List<T>.indexOf(element: T): Int {
    return indexOf(element)
}

완전히 이해하기는 어렵지만 이걸 보면 그냥 모든 element를 하나씩 탐색해나가는 선형탐색(Linear Search)을 사용하고 있다는 것을 알 수 있다.

따라서 시간 복잡도에 측면에서 생각해보면 indexOf()는 O(n)의 시간 복잡도를 가지므로 리스트의 사이즈가 클수록 시간이 오래걸리게 된다!

+) 🧐 따라서 정렬된 리스트라면 binarySearch()함수를 사용하여 이진탐색(binarySearch)을 수행하는게 더 효율적이다!

어쨌든 위 코드의 비효율적인 부분을 찾았으니 indexOf()로 인덱스를 찾는 과정을 Map을 통해O(1)의 시간복잡도로 감소 시켜 효율성을 높여보도록 한다!

fun solution(players: Array<String>, callings: Array<String>): Array<String> {
        
        var answer: Array<String> = arrayOf<String>()
        val player=players.toMutableList()
				//선수의 등수를 저장하는 map
        val playerMap= player.withIndex().associate{it. value to it.index}.toMutableMap()
        
        callings.forEach{

            val index=playerMap[it]!!
            val temp=player[index]

            //기존 선수 등수 내리기
            player[index]=player[index-1]
            playerMap[player[index-1]]=index
            
            //호명 선수 등수 올리기
            player[index-1]=temp
            playerMap[it]=index-1
            
            
        }
        answer=player.toTypedArray()
        return answer
    }

위 코드에서 약간 고려해 볼 만한 점이라면

val playerMap= player.withIndex().associate{it. value to it.index}.toMutableMap()

이 부분에서 추가적인 반복 작업이 생기게 된다.

그러나 생성 시 한번만 진행하면 되고 이후 indexOf()를 통한 반복이 사라졌기 때문에 입력에 큰 사이즈의 배열이 들어오는 경우에는 이전보다 효율적으로 인덱스를 찾을 수 있게 된다.

사용한 함수를 정리하자면 아래와 같다.

  • withIndex()
    • 컬렉션 각 요소 → 인덱스를 가진 IndexedValue객체 로 변환
    • IndexedValue : (인덱스,값)

    • 예시

        val list=listOf("hello","hi")
  val indexList=list.withIndex()
  indexList[0].index //0
  indexList[0].value //"hello"
        
  //->indexList : [(0,"hello"),(1,"hi")]
  • associate()
    • 컬렉션의 각 요소를 매핑하여 새로운 map을 만듦
    • Pair를 반환하는 람다식을 인자로 받음

    • 예시

        val list=listOf("hello","hi")
  val map=list.associate{it to it.length}
  //-> map : {"hello" to 5,"hi" to 2 }

댓글남기기

참고