TIL: 프로그래머스 달리기 경주, 시간복잡도(Time Complexity)

class Solution {
    fun solution(players: Array<String>, callings: Array<String>): Array<String> {
        var answer: Array<String> = arrayOf<String>()
        var playerArray=players
        var change1 = 0
        var change2 = 0
        var temp= ""
        var idx = 0
        for(i in 0 until callings.size){
            change1= playerArray.indexOf(callings[i])-1
            change2= change1+1
           
            temp=playerArray[change2]
            playerArray[change2]=playerArray[change1]
            playerArray[change1]=temp
            idx++ 
            continue
        }
        
        return answer
    }
}

 

처음 썼던 코드... 버블정렬을 활용했지만 실패... 시간초과가 뜬다.

하... 어쩐지 너무 쉽게 풀린다 했다. 

시간 초과가 뜨는이유는  indexOf()가 배열의 0부터 끝까지 하나하나 대입하면서 비교하는거라서 길이가 10만개, 100만개씩 되면 계산시간이 그만큼 길어지기 때문이다.

원하는 값을 더 빨리 찾을 수 있는 무언가가 필요했다. 찾아보니 map으로 풀라고 한다. 

 

class Solution {
    fun solution(players: Array<String>, callings: Array<String>): Array<String> {
        var answer: Array<String> = arrayOf<String>()
        var playerArray=players
        var nameRankMap = mutableMapOf<String, Int>()
        var rankNameMap = mutableMapOf<Int, String>()
        
        for(i in players.indices){
            nameRankMap[players[i]]=i+1
            rankNameMap[i+1]=players[i]
        }
        for(i in 0 until callings.size){
            var passing=callings[i]
            var passingidx= nameRankMap[passing]!!
            
            var passedidx = passingidx!!-1
            var passed = rankNameMap[passedidx]!!
            
            nameRankMap[passing]=nameRankMap[passing]!!-1
            rankNameMap[passedidx]=passing
            
            nameRankMap[passed]=nameRankMap[passed]!!+1
            rankNameMap[passingidx]= passed
     
        }
   
       for(i in players.indices){
           answer+=rankNameMap[i+1]!!
       }
        return answer
    }
}

 

확실히 값을 찾는 속도가 엄청나게 빨라졌다....

 

시간복잡도

 

• Big-O(빅-오) ⇒ 최악
• Big-Ω(빅-오메가) ⇒ 최선
• Big-θ(빅-세타) ⇒ 그 둘의 평균

 

Big-O 표기법

1. O(1) : 입력값에 상관없이 계산 1번으로 결과가 나옴.
2. O(n) : 입력값이 증가할 때마다 계산도 n 번씩 똑같은 비율로 증가한다.
3. O(log n) : 로그복잡도라고 부르는데 O(1) 다음으로 빠른 시간복잡도를 가진다. up&down 게임의 알고리즘을 예시로 들 수 있다. (최대 수를 계속 2씩 나누면서 범위를 좁히는 방법)
4. O(n2) : 2차 복잡도(quadratic complexity)라고 부르는데 입력값에 따라서 계산시간이 곱절로 늘어나는 걸 말한다. 이중 for문이나 삼중for문이 대표적인 예이다.
5. O(2n) :기하급수적 복잡도(exponential complexity)라 부른다. 입력값에 따라 엄청난 계산이 필요한 경우를 말한다.

//피보나치 수열 (기하급수적 복잡도)
function fibonacci(n) {
  if (n <= 1) {
    return 1;
  }
  return fibonacci(n - 1) + fibonacci(n - 2);
}