백준 - 사탕 박사 고창영(Kotlin)

본 알고리즘 풀이는 Routine Study에서 진행하고 있습니다.

https://github.com/ROUTINE-STUDY/Algorithm

 

저를 포함한 구성원이 대부분 초보이므로, 원하시는분은 언제라도 들어오셔도 좋습니다.

GitHub - ROUTINE-STUDY/Algorithm: 초보 알고리즘 스터디 / 누구나 참여 가능

문의는 댓글 바람.

 

문제 출처 : https://www.acmicpc.net/problem/2508

[문제 설명]

사탕을 찾아라.

 

[접근 방법]

내가 접근한 방법은 'o' 좌표만 체크했다가, 나중에 사탕의 4방향을 체크하는 방법이다.

빠를 거라고 생각하고 작성했는데, 사실 오히려 느린 방법이다.

최악의 경우 모든 맵의 문자가 'o'가 되는데. 이렇게 되면 'o'의 개수는 r*w(맵의 크기)가 되고, 4방향을 체크해야하므로 r*w*4가 총 연산 횟수가 된다.

물론 시간복잡도는 O(r*w)지만, 다른 방법보다 좀 느리다.

 

다른 사람들의 답안을 보니까 '>'나 'v'가 나오면 체크하는 방법을 선택했는데, 이 방법은 r*w*2이므로 내가 생각한 방법보다 미세하지만 조금 빨랐다.

 

import java.io.BufferedReader
import java.io.InputStreamReader

val directions = arrayOf (intArrayOf(-1,0), intArrayOf(0,1), intArrayOf(1,0), intArrayOf(0,-1))
fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    var time = readLine().toInt()
    while (time-- > 0) {
        var cntOfCandy = 0
        readLine()
        val (r,c) = readLine().split(" ").map { it.toInt() }
        val map = Array(r) {CharArray(c)}
        val circleIdxList = ArrayList<IntArray>()
        repeat(r) { rIdx ->
            map[rIdx] = readLine().toCharArray()
            map[rIdx].forEachIndexed { cIdx, c ->
                if (c == 'o') {
                    circleIdxList.add(intArrayOf(rIdx, cIdx))
                }
            }
        }

        if (r <= 2 && c <= 2) {
            println(0)
            continue
        }

        circleIdxList.forEach { circlePosition ->
            if (isCandy(map, circlePosition)) {
                cntOfCandy++
            }
        }

        println(cntOfCandy)
    }
}

fun isCandy(map: Array<CharArray>, circlePosition: IntArray): Boolean {
    if ((circlePosition[0] + directions[0][0] in map.indices && circlePosition[1] + directions[0][1] in map[0].indices) &&
        (circlePosition[0] + directions[2][0] in map.indices && circlePosition[1] + directions[2][1] in map[0].indices)) {
        if (map[circlePosition[0] + directions[0][0]][circlePosition[1] + directions[0][1]] == 'v' && map[circlePosition[0] + directions[2][0]][circlePosition[1] + directions[2][1]] == '^') {
            return true
        }
    }

    if ((circlePosition[0] + directions[3][0] in map.indices && circlePosition[1] + directions[3][1] in map[0].indices) &&
        (circlePosition[0] + directions[1][0] in map.indices && circlePosition[1] + directions[1][1] in map[0].indices)) {
        if (map[circlePosition[0] + directions[3][0]][circlePosition[1] + directions[3][1]] == '>' && map[circlePosition[0] + directions[1][0]][circlePosition[1] + directions[1][1]] == '<') {
            return true
        }
    }

    return false
}