백준 25758: 유전자 조합 [Kotlin 코틀린 / 비둘기집 원리]

백준 25758: 유전자 조합

🥸 문제 분석

알파벳 두개로 이루어진 유전자 문자열이 주어진다.
각 유전자는 다른 유전자와 조합할 수 있으며,
조합되는 알파벳의 양 끝 알파벳 중에 사전 순으로 같거나 큰 알파벳이 표현형으로 선택된다.

✅ 문제 풀이

N이 100000까지로, 상당히 크다.
즉, O(N)이나 O(NlogN)으로 해결할 수 있는 방법을 고민해봐야 한다.
우선 문제에서 제시하는 조건을 다시 확인해보자.

1. 알파벳이 조합될 때는 양 끝 알파벳 중 하나만 선택된다. (AB - CD 라면 A와 D 중에 선택)
2. 사전 순으로 같거나 큰 알파벳이 선택된다. (A와 D 중에 D가 선택됨)

위 조건에 따르면 아래와 같은 유전자 조합들은 같은 표현형을 도출해낸다.

AB - CD => D
AZ - XD => D
AC - FD => D

즉, 우리가 초점을 맞춰야 될 곳은 4개의 알파벳 중 양 끝 알파벳 뿐이다.
예시로, 현재 AB라는 알파벳과 조합할 알파벳을 찾고자 한다면,
AB의 첫번째 알파벳인 A가 표현형이 되고자 하면,
다른 유전자의 두번째 알파벳이 A와 같거나 사전 순으로 앞서면 되고,
AB의 두번째 알파벳인 B가 표현형이 되고자 하면,
다른 유전자의 첫번째 알파벳이 B와 같거나 사전 순으로 앞서면 된다.

그러므로 존재하는 유전자의 조합을 다 구할 필요가 없다.
내가 표현형으로 나타내고 싶은 알파벳 이하인 알파벳이 하나라도 있는지만 확인하면 되는 것이다.

이 접근 방식을 기반으로 데이터를 초기화하자.
우선 모든 유전자의 알파벳 개수를 기록할 Map을 생성한다.

// 첫번째 알파벳의 개수를 기록할 Map
val firstMap = buildMap {
	('A'..'Z').forEach { put(it, 0) }
}.toMutableMap()

// 두번째 알파벳의 개수를 기록할 Map
val secMap = buildMap {
	('A'..'Z').forEach { put(it, 0) }
}.toMutableMap()

이제 모든 유전자의 알파벳 개수를 기록한다.

val G = readLine().split(" ")

for (g in G) {
	val f = g[0]; val s = g[1]
    firstMap[f] = firstMap[f]!! + 1
    secMap[s] = secMap[s]!! + 1
}

기록된 알파벳 개수를 이용하여 문제를 해결하자.
모든 유전자를 쭉 한번 훑으면서, 첫번째 알파벳 이하인 두번째 알파벳이 존재하는지 확인하고,
두번째 알파벳 이하인 첫번째 알파벳이 존재하는지 확인한다.

val answer = mutableSetOf<Char>()
for (g in G) {
	val f = g[0]; val s = g[1]
    
    // 두번째 알파벳 이하인 알파벳이 존재하는지 확인
    for ((k, v) in firstMap) {
    	if (k <= s) {
        	when {
            	// g의 첫번째 알파벳이 k와 같을 수도 있다. 
                // 이때는 다른 유전자의 알파벳이여야 답이 될 수 있기 때문에, 
                // count된 개수가 1 초과인지를 확인한다.
            	k == f && v > 1 -> answer.add(s) 
                k != f -> answer.add(s)
            }
        }
    }
    
    // 첫번째 알파벳 이하인 알파벳이 존재하는지 확인
    for ((k, v) in secMap) {
    	if (k <= f) {
        	when {
            	// g의 두번째 알파벳이 k와 같을 수도 있기 때문에,
                // 그럴 가능성을 확인하고 답으로 추가한다.
            	k == s && v > 1 -> answer.add(f) 
                k != s -> answer.add(f)
            }
        }
    }
}
println(answer.size)
print(answer.sorted().joinToString(" "))

결론적으로 모든 유전자 쌍을 확인해볼 필요 없이,
문제 조건을 제대로 활용하고, 알파벳이 총 26개인 것을 기반으로
비교적 빠른 시간 복잡도로 해결할 수 있는 문제였다.
비둘기집원리 문제는 항상 교육적으로 퀄리티가 좋은 것 같다.

정답 코드

val N = readLine().toInt()
val G = readLine().split(" ")

val firstMap = buildMap {
    ('A'..'Z').forEach { put(it, 0) }
}.toMutableMap()
val secMap = buildMap {
    ('A'..'Z').forEach { put(it, 0) }
}.toMutableMap()

for (g in G) {
    firstMap[g[0]] = firstMap[g[0]]!! + 1
    secMap[g[1]] = secMap[g[1]]!! + 1
}

val answer = mutableSetOf<Char>()
for (g in G) {
    val f = g[0]; val s = g[1]
    for ((k, v) in firstMap) {
        if (k <= s && v > 0) {
            when {
                f != k -> answer.add(s)
                f == k && v > 1 -> answer.add(s)
            }
        }
    }
    for ((k, v) in secMap) {
        if (k <= f && v > 0) {
            when {
                s != k -> answer.add(f)
                s == k && v > 1 -> answer.add(f)
            }
        }
    }
}

println(answer.size)
print(answer.sorted().joinToString(" "))