글 읽기 - 해싱을 사용했습니다. 예제와 게시판의 반례는 다 맞지만 25%에서 틀립니다.

jslkap227 2년 전 0

어디가 틀린 걸까요..?

로직은 번호마다 hashArray[자리수][번호]의 해싱값(count)을 확인해서 하나라도 1이면, 해당 자리수의 숫자를 가진 전화번호가 자신밖에 없으니 일관성 있는 번호라고 판단했습니다. 그리고 모두 2 이상이면 일관성 없는 번호라고 판단했습니다.

제가 생각하기에 로직이 맞는 거 같은데, 어디가 틀린 걸까요?

코틀린이지만 열심히 주석 작성해서 보시기에 큰 무리 없을 거예요.

도와주십쇼ㅠㅠ

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

fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    val t = readLine().toInt()
    val answer = StringBuilder()

    repeat(t) {
        val size = readLine().toInt()

        val phoneNumbers = Array<List<Int>>(size) {
            val phone = readLine()
            val list = mutableListOf<Int>()

            phone.forEach {ch ->
                if (ch != ' ') {
                    list.add(ch - '0')
                }
            }

            list
        }

        // 카운트 해시: hashArray[자리수][번호] - 각 자리수에 몇개의 숫자가 들어있는지 센다
        val hashArray = getHashArray(phoneNumbers)

        if (isConsistent(phoneNumbers, hashArray)) answer.append("YES\n")
        else answer.append("NO\n")
    }

    print(answer)
}

fun isConsistent(phoneNumbers: Array<List<Int>>, hashArray: Array<IntArray>): Boolean {
    // 해싱 확인
    for (phone in phoneNumbers) {
        var isConsistent = false

        for (i in phone.indices) {
            val number = phone[i]

            // 전화번호에서 i자리에 phone[i]를 갖고 있는 전화번호가 자신밖에 없다
            // -> 지금 번호는 일관성이 있다
            if (hashArray[i][number] == 1) {
                isConsistent = true
                break
            }
        }

        // 모든 자리수의 숫자가 2개 이상이면 일관성이 없는 번호이다
        if (!isConsistent) {
            return false
        }
    }

    // 검사가 중간에 끝나지 않았으면 모두 일관성 있는 번호이다
    return true
}

// 카운트 해시 반환) hashArray[자리수][번호]
fun getHashArray(phoneNumbers: Array<List<Int>>): Array<IntArray> {
    val hashArray = Array<IntArray>(10) {
        IntArray(10)
    }

    // 해싱
    phoneNumbers.forEach { phone ->
        for (i in phone.indices) {
            val number = phone[i]
            hashArray[i][number]++
        }
    }

    return hashArray
}

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

문제

문제

출처

ICPC

해싱을 사용했습니다. 예제와 게시판의 반례는 다 맞지만 25%에서 틀립니다.

jslkap227 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말