[BOJ] 1021번 회전하는 큐
문제 : 원형 큐에서 현재 위치에서 목적 위치까지 가는데 가장 가까운 방법으로 가는데 드는 비용의 합.
설명 : 큐에 1~N까지 원소를 넣고, 현재 위치는 큐의 첫번째 원소로 생각.
( 큐의 첫번째 위치에서 +1 , 큐의 끝점에서 -1 ) => 반복해서 도착하고자 하는 번호에 먼저 도달하는 것이 비용이 작게 든다. 따라서 먼저 도달한 방법으로 큐의 현재위치(q[0]) 를 이동시킨다.
만약 현재위치에서 좌측으로 가는 것이 빠르다 => q[0]에 큐의 마지막 원소를 넣고, 마지막 원소를 삭제 : 즉, 좌측으로 이동.
만약 현재위치에서 우측으로 가는 것이 빠르다 => 큐에 q[0]를 뒤에 추가하고, q[0]를 삭제 : 즉 q[0]를 우측으로 이동
그리고 한칸이동 시 비용을 +1 해주어서 결과값을 얻었다.
(문제 바로가기 : https://boj.kr/1021 )
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 | import java.io.BufferedReader import java.io.InputStreamReader import java.util.* fun main(args: Array<String>) { val br = BufferedReader(InputStreamReader(System.`in`)) val (n, m) = br.readLine()!!.split(" ").map { it.toInt() } val choice = br.readLine()!!.split(" ").map { it.toInt() }.toIntArray() val q = LinkedList<Int>() for (i in 1..n) q.add(i) var res = 0 var count = 0 while (count != m) { if (q.first == choice[count]) { q.poll() } else { for (i in 1 until q.size) { if (q[q.size - i] == choice[count]) { while (q[0] != choice[count]) { q.add(0, q.last) q.removeLast() res++ } q.poll() break } else if (q[i] == choice[count]) { while (q[0] != choice[count]) { q.add(q.first) q.removeFirst() res++ } q.poll() break } } } count++ } println(res) } | cs |
'BOJ(백준)' 카테고리의 다른 글
| [BOJ] 2170번 선 긋기 by Kotlin (0) | 2018.11.13 |
|---|---|
| [BOJ] 1017번 소수 쌍 by Kotlin (0) | 2018.10.07 |
| [BOJ] 1671번 상어의 저녁식사 by Kotlin (0) | 2018.10.06 |
| [BOJ] 1068번 트리 byKotlin (0) | 2018.10.02 |
| BOJ 2789번 유학금지 by Kotlin (0) | 2018.07.18 |