글 읽기 - 시간초과가 발생합니다.(mutableMap사용)

hsjeon01 1년 전 0

처음에 mutableList로 제출했을 땐 시간초과가 나서 mutableMap을 사용하여 문제를 해결을 시도하였는데 마찬가지로 시간초과가 발생합니다..! 혹시 여기서 시간초과에 관한 계선을 더 할 수 있을까요? 질문들 보니까 이분탐색으로도 많이들 푸시더라구요! 이분탐색이 정답일까요?

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

fun main() {

    val br = BufferedReader(InputStreamReader(System.`in`))
    val bw = BufferedWriter(OutputStreamWriter(System.out))

    val (cntData, cntQuiz) = br.readLine().split(" ").map { it.toInt() }

    val pocketmonBook = mutableMapOf<String, Int>()

    repeat(cntData) { index ->
        // 포켓몬의 이름이 키, 값은 포켓몬의 번호(순서이자 인덱스)
        pocketmonBook.put(br.readLine(), index + 1)
    }

    repeat(cntQuiz) {
        val input = br.readLine()

        // 입력으로 숫자가 들어왔다면
        if (isNum(input)) {
            bw.write("${pocketmonBook.filterValues { it == input.toInt() }.keys.joinToString()}\n")
            // 입력으로 문자(포켓몬의 이름이 들어왔다면
        } else {
            bw.write("${pocketmonBook.get(input)}\n")
        }

    }

    bw.flush()
    bw.close()
}

// 입력받은 문자열이 정수인지 확인하는 함수
fun isNum(string: String): Boolean {

    // 입력받은 문자열이 정수라면 isNum은 true
    var isNum = true

    // 입력받은 문자열을 문자 하나씩 탐색
    string.forEach { char ->

        // 아스키코드로 변환된 "문자" - 대문자일수도 있으니 소문자로 바꿔줌.
        val charConvertedToCode = char.code

        // 정수 0의 아스키 코드는 48, 정수 9의 아스키 코드는 57 - 해당 범위를 벗어나면 정수가 아님.
        if (charConvertedToCode > 57 || charConvertedToCode < 48) {
            isNum = false
            return isNum
        }
    }

    return isNum
}

chldn323 1년 전 1

Map 1개로 해결하려고 하지 말고 2개를 쓰거나 list, map 1개씩 써도 됩니다. 이분탐색 없어도 돼요.

25번 줄에 filter 부분 때문에 시간 초과가 발생하는 것 같네요.

추가로 Kotlin에는 Char에 isDigit 함수가 있어서 47~50 번 줄의 내용은 if(char.isDigit())으로 편하게 할 수 있습니다.

또 입력은 전부 숫자거나 전부 영어이기 때문에 모든 문자를 다 비교할 필요 없어요.

hsjeon01 1년 전 0

오... 그렇군요 많이 배워갑니다! 정말 감사드려요!!

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

시간초과가 발생합니다.(mutableMap사용)

hsjeon01 1년 전 0

chldn323 1년 전 1

hsjeon01 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말