2890번: 카약

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

 

언어 : Kotlin

 

문제 설명 :

상근이는 카약 대회를 개최했다. 대회는 전세계에 생중계되고, 위성이 경기장 전체를 촬영하고 있다. 상근이는 위성 사진을 바탕으로 실시간 순위를 계산하는 프로그램을 만들려고 한다.

위성 사진은 R행 C열이다. 모든 줄의 첫 번째 글자는 'S'이고 출발선을 의미한다. 또, 마지막 글자는 'F'이고 이것은 결승선을 의미한다. 대회에 참가한 팀은 총 9팀이고, 각 팀은 1부터 9까지 번호가 매겨져 있다. 카약은 항상 열에 대해 연속하는 세 칸을 차지하며, 카약 번호로 표시한다. 마지막으로 물은 '.'로 나타나 있다.

팀의 순위는 결승선으로부터 떨어진 거리로 측정한다. 가까울수록 순위가 높다. 만약, 두 팀이 결승선과 떨어진 거리가 같다면, 같은 등수이다.

 

입력 :

첫째 줄에 R과 C가 주어진다. 다음 R개 줄에는 '.', 'S', 'F', '1'~'9'로 이루어진 위성 지도가 주어진다. 한 줄에는 최대 한 개의 카약만 있고, 위성 사진에 있는 카약은 항상 9개이다. (10 ≤ R, C ≤ 50)

 

출력 :

출력은 총 9줄을 해야 한다. i번째 줄에는 i번 팀의 등수를 출력한다. (i=1~9)

 

제한 사항 :

• 시간 제한 : 1초
• 메모리 제한 : 128MB

 

입출력 예 :

입력	출력
10 10 S.....111F S....222.F S...333..F S..444...F S.555....F S666.....F S.777....F S..888...F S...999..F S........F	1 2 3 4 5 6 5 4 3
10 15 S..........222F S.....111.....F S...333.......F S...555.......F S.......444...F S.............F S......777....F S..888........F S........999..F S...666.......F	5 1 6 3 6 6 4 7 2

 

풀이 : 

S ~ F의 뒷부분 F에서부터 접근하여 '.'이 아닌 것이 나오면 해당 문자와 인덱스를 저장한다.

저장한 배열을 인덱스로 묶고 인덱스를 기준으로 내림차순으로 정렬한다.

반복문을 통해 순회하며 해당 항목이 size가 1이라면 미리 준비한 크기 9짜리 정수형 배열에 저장한 문자를 정수로 형변환하여 result[형변환한 문자] = index + 1을 해준다.

 

예를 들어 예제 2의 경우 groupBy를 사용하고 내림차순으로 정렬하면 다음과 같이 나올 것이다.

 

Index	A	B
0	13	(2, 13)
1	11	(9, 11)
2	10	(4, 10)
3	9	(7, 9)
4	8	(1, 8)
5	6	(3, 6), (5, 6) (6, 6)
6	5	(8, 5)

 

여기서 A는 처음에 저장할때 '.'이 아닌 문자가 검열된 첫 인덱스를 뜻한다.

검열된 첫 인덱스란 Start. 시작지점에서부터 이동한 거리이다.

B는 Pair로 묶인 것으로 (팀 번호, 이동한 거리)가 된다.

 

이동한 거리를 기준으로 그룹이 묶였으므로 0 ~ 6까지 인덱스가 나왔고, 문제에선 거리가 같으면 등수 또한 중복된다고 하였다. 그러므로 Index + 1은 등수가 된다.

 

이제 이것을 순회하며 result[팀번호 - 1] = Index + 1을 해주면 result 0 ~ 8에 등수가 들어가게 되고 이를 출력하면 된다.

Index	Team Number	Result
0	1	5
1	2	1
2	3	6
3	4	3
4	5	6
5	6	6
6	7	4
7	8	7
8	9	2

 

import java.io.BufferedReader
import java.io.BufferedWriter
import java.io.InputStreamReader
import java.io.OutputStreamWriter

fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    val bw = BufferedWriter(OutputStreamWriter(System.out))

    val (r, c) = readLine().split(" ").map { it.toInt() }
    val record = mutableListOf<Pair<Char, Int>>()
    repeat(r) {
        val cur = readLine()
        for (i in cur.lastIndex - 1 downTo 1) {
            if (cur[i] != '.') {
                record += Pair(cur[i], i)
                break
            }
        }
    }

    val result = IntArray(9)
    record.groupBy { it.second }.entries.sortedByDescending { it.value[0].second }.forEachIndexed { index, entry ->
        with(entry.value) {
            if (size == 1) {
                result[entry.value[0].first.digitToInt() - 1] = index + 1
            } else {
                repeat(size) {
                    result[this[it].first.digitToInt() - 1] = index + 1
                }
            }
        }
    }

    result.map { bw.appendLine("$it") }
    bw.flush()
    bw.close()
}