백준 2164번 : 카드2 (Queue)

제목

7/7 오늘의 문제 class2 - 백준 2164번 : 카드2

 

 

문제 유형

Queue 문제

 

풀이 방법 도출

1. 처음에는 리스트와 removeAt을 사용해서 풀었는데 시간초과가 났다.
2. 그래서 removeAt으로 시간복잡도를 늘리지 않고 새로운 리스트를 할당하는 방법으로 풀었는데 많은 리스트 생성으로 메모리 초과가 났다.. ㄱ-;;
3. 그래서 어쩔 수 없이 Queue를 공부해서 사용하였다.

 

 

시간 복잡도

• removeAt() -> 리스트 한번도는거 n 근데 while 씀 n -> n^2 최악의 경우 n^3
• 새로운 리스트 할당 -> 리스트 한번 도는거 n while 을 쓰긴하는데 반으로 리스트가 줄음 logn-> nlogn
• 큐 사용 -> 한번 돌때 앞에꺼 제거, 뒤에 추가 n -> n

 

핵심 코드 삽입 및 설명

 

fun main() {
    val n = readLine()!!.toInt()     //6
    val q = ArrayDeque<Int>()

    //[1,2,3,4,5,6]
    //[2,4,6]
    for(i in 1..n) {
        q.addLast(i)
    }
    
    while(q.size > 1) {
        q.removeFirst()
        q.addLast(q.removeFirst())
    }
   
    println(q.first())   
}

 

코틀린에서 Queue는 ArrayDeque<Int>() 로 선언한다.

addLast(), addFirst(), removeLast(), removeFirst() 가 있다.