[알고리즘] 프린트(❌) - 알고리즘 공부

✔️사이트 : 프로그래머스

✔️언   어 : Kotlin

✔️난이도 : Level 2

✔️문   제 : 프린트

 

 

총평 : 

테스트가 통과되지 않았다. 문제를 풀어내는 아이디어는 비슷했으나 잘못 생각한 부분이 있었다.

 

문제 :

 

아래의 테스트코드를 작성한것처럼 작동해야한다고 생각했다.

  assertEquals(1, solution(intArrayOf(1), 0))
  assertEquals(1, solution(intArrayOf(2, 1, 3, 2), 2))
  assertEquals(5, solution(intArrayOf(1, 1, 9, 1, 1, 1), 0))
  assertEquals(1, solution(intArrayOf(1, 2, 2, 3, 4, 6, 6, 6, 7, 9), 9))
  assertEquals(9, solution(intArrayOf(1, 9, 9, 9, 9, 9, 9, 9, 9, 9), 9))

 

문제를 해결하지 못하고 답안을 참고했다.

발상한 아이디어는 비슷했다고 생각한다. 그러나 프린트 대기 목록에서 계속해서 비교를 하고 프린트를 해야하는 부분에 대해서 다르게 생각하고 문제를 풀었다. 이상한것 같은데? 라고 생각하면서 계속 코드를 잘못 작성했다.

 

대기 목록의 맨 앞에 있는 아이템을 계속해서 비교하면서 우선순위가 낮으면 뒤로 보내고 우선순위가 높으면 프린트를 계속 했어야했다.

 

실패 요인

1. 한번에 대기 목록을 만들어야한다는 이상한(?) 생각

2. 첫 예문에서 (A,B,C,D)의 목록의 중요도는 (2,1,3,2) 이고 인쇄를 하게 될 경우 (C, D, A, B) 순서로 출력이 된다고했길래,

   A,B,C,D -> B,C,D,A -> C,D,A,B 형태로 되고 출력이 된다고 생각을 한점.

3. 2번처럼하면 맨 처음에만 우선순위를 정하는건데... 나머지 대기목록의 중요도는 의미없는거 아닌가? 라는 생각을 하면서도 밀어붙인 점.

 

 

 

 

나의 테스트 코드

@Test
fun test() {
  assertEquals(1, solution(intArrayOf(1), 0))
  assertEquals(1, solution(intArrayOf(2, 1, 3, 2), 2))
  assertEquals(5, solution(intArrayOf(1, 1, 9, 1, 1, 1), 0))
  assertEquals(1, solution(intArrayOf(1, 2, 2, 3, 4, 6, 6, 6, 7, 9), 9))
  assertEquals(9, solution(intArrayOf(1, 9, 9, 9, 9, 9, 9, 9, 9, 9), 9))
}

fun solution(priorities: IntArray, location: Int): Int {
    if (priorities.size == 1) return 1

    var maxValue = 0
    var listSize = 0
    val prioritiesPairList = priorities.mapIndexed { index, value ->
        if (value > maxValue) {
            maxValue = value
        }
        listSize++
        Pair(value, index)
    }

    val initValue = prioritiesPairList[location]
    val printList: Queue<Pair<Int, Int>> = LinkedList(prioritiesPairList.toList())

    var whileCount = 0
    while (printList.first().first < maxValue && whileCount < listSize) {
        printList.add(printList.poll())
        whileCount++
    }

    return printList.indexOf(initValue) + 1
}

 

테스트 결과

 

정답 중 하나

fun solution(priorities: IntArray, location: Int): Int {
    val printerQueue = ArrayDeque<Pair<Int, Int>>()
    priorities.forEachIndexed { index, i ->
        printerQueue.offer(Pair(index, i))
    }

    var count = 0
    while (!printerQueue.isEmpty()) {
        val first = printerQueue.poll()

        if (printerQueue.any { first.second < it.second }) {
            printerQueue.offer(first)
        } else {
            count++
            if (first.first == location) return count
        }
    }
    return 0
}

 

 

Additional

추가적으로 위의 테스트가 통과된 코드에서 살짝 정리를 해봤다.

fun solution(priorities: IntArray, location: Int): Int {
    val printerQueue = ArrayDeque<Pair<Int, Int>>()
    priorities.forEachIndexed { index, i ->
        printerQueue.offer(Pair(index, i))
    }

    var count = 0
    while (printerQueue.isNotEmpty()) {
        val first = printerQueue.poll()
        if (printerQueue.any { first.second < it.second }) {
            printerQueue.offer(first)
        } else {
            count++
            if (first.first == location) return count
        }
    }

    return count
}

 

그리고 난 Queue 를 써야하는 문제에는 보통 LinkedList 를 써왔었는데, ArrayDeque 를 쓰길래 무슨 차이인지 찾아봤다.

 

ArrayDeque 가 LinkedList 차이

1. LinkedList 의 메모리 소모가 더 많다.

2. 리스트 양 끝단에 삽입/삭제 는 ArrayDeque 가 효율적이고, 현재 요소를 반복적으로 지우는데는 LinkedList 가 효율적이다.

3. ArrayDeque 는 null을 지원하지 않지만, LinkedList 는 지원한다.

4. ArrayDeque 에 데이터가 꽉 찬 상태에서 데이터 삽입이 일어날때 원래 형태의 2배를 만들고 복사를 하고 추가해야한다.

 

참고 :

stackoverflow.com/a/6163204/3897810

Why is ArrayDeque better than LinkedList