🤔 문제 분석
오직 4줄의 입력만 주어진다.
각 입력은 A~F의 승/무/패 기록으로 구성되어 있다.
제시된 승/무/패 기록이 가능한지 확인하는 로직을 구현해야 한다.
✅ 문제 풀이
입력 데이터는 각 국가의 승/무/패 데이터이다.
축구 경기이므로 X, Y가 대결했을 때
X가 승리하면 동시에 Y에 패가 누적되고
무승부하면 X, Y에게 무승부가 누적되고
X가 패배하면 동시에 Y에게 승리가 누적된다.
입력된 데이터를 통해 승/무/패를 따져가며 기가막힌 방식으로 검증을 해봐야 할까?
대충 구상해봐도 쉽지 않을 듯하다. 머리 아플 때는 우선 완전 탐색을 고려해본다.
A, B, C, D, E, F 가 각각 한번 씩 대결하면, 가능한 매치업은 아래와 같을 것이다.
A vs. B
A vs. C
A vs. D
A vs. E
A vs. F
B vs. C
B vs. D
B vs. E
B vs. F
...
D vs. E
D vs. F
E vs. F
5+4+3+2+1=15개의 매치업만이 존재한다. (조합 6C2와 같다)
해당 매치업에서 가능한 경우의 수는 3가지씩이다. (X의 승리 or 무승부 or Y의 승리)
즉, 3^15의 경우의 수가 가능하며, 이는 대략 1400만 정도의 수이고,
현재 제한된 시간인 1초에 충분히 처리가 가능한 대상이라고 할 수 있다.
지금부터 완전 탐색으로 접근할 것이다. 우선 입력부터 받자.
테스트 케이스마다 재사용할 변수를 선언하고, 입력을 받는다.
private lateinit var R: List<IntArray> // 입력된 승,무,패 데이터
private lateinit var counter: List<IntArray> // 승,무,패 기록할 변수
private val answer = IntArray(4) // 답을 기록할 변수
private var order = 0 // 테스트 케이스 순서 변수
...
fun main() = with(System.`in`.bufferedReader()) {
repeat(4) {
order = it
R = readLine().split(" ").chunked(3)
.map { match -> match.map(String::toInt).toIntArray() }
counter = List(6) { IntArray(3) } // IntArray의 각 인덱스에 승/무/패가 기록된다.
...
}
}
그리고 매치업을 미리 만들어두자. 이중 for문으로 금방 작성할 수 있다.
private data class Match(
val x: Int,
val y: Int
)
val match: List<Match> = buildList {
for (x in 0 until 6) {
for (y in x + 1 until 6) {
add(Match(x, y))
}
}
}
...이제 매치업을 하나씩 탐색해나가며 승/무/패를 모두 따져보자.
match 변수에 접근할 것이며, 인덱스는 0부터 시작한다.
fun main() = with(System.`in`.bufferedReader()) {
repeat(4) {
...
bruteforce(0)
}
}
fun bruteforce(matchNum: Int) {
...
}match 변수에는 매치업의 X와 Y가 기록되어 있다. matchNum을 인덱스로 데이터에 접근하자.
matchNum을 1씩 증가시킬 것이기 때문에
matchNum이 match 변수의 크기에 도달하면 해당 경우가 입력값과 일치하는지 검증하면 된다.
fun bruteforce(matchNum: Int) {
if (matchNum == match.size) {
...
return
}
val (x, y) = match[matchNum]
...
}X가 이기는 경우, 무승부, Y가 이기는 경우를 모두 탐색한다.
fun bruteforce(matchNum: Int) {
if (matchNum == match.size) {
...
return
}
val (x, y) = match[matchNum]
// x 이기는 경우
counter[x][0]++
counter[y][2]++
bruteforce(matchNum + 1)
counter[x][0]--
counter[y][2]--
// 무승부
counter[x][1]++
counter[y][1]++
bruteforce(matchNum + 1)
counter[x][1]--
counter[y][1]--
// x 지는 경우 (y 이기는 경우)
counter[x][2]++
counter[y][0]++
bruteforce(matchNum + 1)
counter[x][2]--
counter[y][0]--
}matchNum이 match의 크기에 도달했을 때, 검증에 들어간다.
R과 counter가 갖는 값들이 완전히 동일한지 확인하고,
동일하면 기록한다.
fun isAnswer(): Int {
for (i in 0 until 6) {
for (j in 0 until 3) {
if (R[i][j] != counter[i][j])
return 0
}
}
return 1
}
fun bruteforce(matchNum: Int) {
if (matchNum == match.size) {
answer[order] = maxOf(answer[order], isAnswer())
return
}
...
}기록한 Int 값을 출력해내면 정답.
...
fun main() = with(System.`in`.bufferedReader()) {
repeat(4) {
...
}
print(answer.joinToString(" "))
}위 풀이처럼 단순히 승/무/패를 누적해나가면
상식적으로 불가능한 경우를 필터링 하지 않고 진행하기 때문에,
최적화가 더해진다면 더 짧은 시간에 답을 도출해낼 수 있을 것 같다.
