코드잼의 첫 난관은 문제를 이해하는 것입니다. 영어이기도 하고 문제를 예시와 함께 간결히 적혀있기 때문에 잘 이해하기가 어렵습니다. QR하는 날 낮에 스터디가 있었던 관계로 네피림님을 꼬셔서 같이 문제 해독(?)에 들어갔습니다. 덕분에 문제를 이해했습니다. 문제를 정리하면 이렇습니다.
구글러들이 댄스컨테스트를 합니다. 심사위원은 3명이 있는데 3명의 점수(triplet of scores)는 0~10의 범위를 가지고 3명의 점수는 최대 2의 차이내에 있습니다. 즉 최대점수와 최소점수의 차이가 2점 이내입니다. total points는 세 점수의 합이고 best reuslt는 세점수 중 최대값입니다. 그리고 세점수의 차이가 2이면 surprising이라고 부릅니다. total points와 surprising의 수가 주어졌을 때 최소한의 best result를 p라고 합니다. 참여한 구글러의 수 N과 surprising의 수 S와 p가 주어지고 total points가 주어졌을 때 p와 같거나 큰 구글러의 최대수는 몇인가를 구하는 문제입니다.
이 문제는 Scala로 풀었습니다. 알고리즘은 자신이 익숙한 문제로 푸는게 좋기 때문에 예전에는 다른 언어로 시도했었지만 사실 뭐 개인적으로 스터디하는 언어라 이런 때 아니면 연습해 볼 기회가 없기 때문에 얼마전부터는 이런 곳에서라도 Scala를 사용하려고 하고 있습니다. 프로젝트는 네피림님이 Scala 스터디를 위해서 만들어 놓은 Scala-Project-Template을 생성해서 만들었습니다. 이 프로젝트는 SBT를 기반으로 만들어져 있으며 ScalaTest도 설정되어 있어서 간단한 SBT 명령어로 이클립스 프로젝트를 생성하고 테스트를 수행할 수 있습니다.(스칼라 공부하시는 분들은 이 프로젝트설정 함 파보셔도 도움이 많이 되실겁니다.) 이번에 처음으로 Scala IDE를 사용했는데 쓸만해 졌더군요.
package kr.ne.outsider
import scala.math._
class DancingWithTheGoogler (val numberOfGooglers:Long, val suprigingCount:Long, val bestResult:Long) {
def findCandidateTripletOfScores(totalPoints:Long):List[(Long, Long, Long)] = {
var resultList:List[(Long, Long, Long)] = Nil
if (totalPoints == 0l) {
if (bestResult == 0l) {
List((0l, 0l, 0l))
} else {
Nil
}
} else if (totalPoints == 1l) {
if (bestResult <= 1l) {
List((1l, 0l, 0l))
} else {
Nil
}
} else {
var basePoints = floor(totalPoints / 3l).toLong
if ((totalPoints - basePoints) % 2 == 1l) {
basePoints = basePoints -1
}
while((abs((totalPoints - basePoints) / 2 - basePoints)) <= 2) {
if ((totalPoints - basePoints) / 2 == basePoints) {
if (getMaximumPoint((basePoints, basePoints - 1, basePoints + 1)) >= bestResult) {
resultList = resultList ::: List((basePoints - 1, basePoints, basePoints + 1))
}
}
if (getMaximumPoint((basePoints, (totalPoints - basePoints) / 2, (totalPoints - basePoints) / 2)) >= bestResult) {
resultList = resultList ::: List((basePoints, (totalPoints - basePoints) / 2, (totalPoints - basePoints) / 2))
}
basePoints = basePoints + 2
}
resultList
}
}
def isSurprising(tripletOfScores:(Long, Long, Long)) = {
val maximumPoint = getMaximumPoint(tripletOfScores)
val minimumPoint = min(min(tripletOfScores._1, tripletOfScores._2), tripletOfScores._3)
(maximumPoint - minimumPoint) == 2
}
private def getMaximumPoint(tripletOfScores: (Long, Long, Long)): Long = {
max(max(tripletOfScores._1, tripletOfScores._2), tripletOfScores._3)
}
def solveProblem(totalPoints:List[Long]) = {
var candidateTripletOfScores = getGroupOfCandidateTripletOfScores(totalPoints)
var googlerCounter = 0d
var surprisingCounter = 0d
candidateTripletOfScores foreach(scores => {
if (scores.length == 1 && isSurprising(scores(0))) {
if (surprisingCounter < suprigingCount) {
googlerCounter = googlerCounter + 1
surprisingCounter = surprisingCounter + 1
}
} else if (scores.length > 0) {
googlerCounter = googlerCounter + 1
}
})
googlerCounter.toLong
}
private def getGroupOfCandidateTripletOfScores(totalPoints:List[Long]) = {
var resultList:List[List[(Long, Long, Long)]] = Nil
totalPoints foreach(totalPoint => {
resultList = findCandidateTripletOfScores(totalPoint) :: resultList
})
resultList
}
}
object DancingWithTheGoogler extends App {
def pasreProblem(problem: String, index: Int) = {
val splited = List.fromArray(problem.split(" "))
val dance = new DancingWithTheGoogler(splited(0).toLong, splited(1).toLong, splited(2).toLong)
var scores:List[Long] = Nil
for (i <- 3 until splited.length) {
scores = splited(i).toLong :: scores
}
print("Case #" + (index+1) + ": ")
println(dance.solveProblem(scores))
}
io.Source.fromFile("/Users/outsider/projects/indigo/GoogleCodeJam2012/src/main/scala/kr/ne/outsider/input.txt").getLines.drop(1).zipWithIndex foreach { e => pasreProblem(e._1, e._2) }
}
DancingWithTheGoogler 클래스가 실제 계산을 하는 알고리즘 클래스이고 DancingWithTheGoogler 오브젝트는 싱글톤 오브젝트로 스칼라에서는 Companion class라고 부릅니다. 여기서는 자바의 main처럼 코드를 실행하는 엔트리포인트로 사용했습니다. 코드잼에서는 인풋파일을 읽어서 아웃풋으로 출력해서 제출해야 하기 때문에 인풋파일을 읽어서 문제를 파싱해서 DancingWithTheGoogler클래스를 이용해서 답을 출력하는 역할을 합니다.
DancingWithTheGoogler 오브젝트를 먼저 보면 91번 라인에서 인풋파일을 읽어서 첫줄은 생략하고(첫줄은 문제가 몇개인가 적혀있습니다.) 아웃풋출력에 문제의 번호가 필요하기 때문에 라인번호를 알 수 있도록 zipWithIndex를 사용해서 각 라인별로 pasreProblem 메서드를 실행했습니다. 각 라인은 공백을 구분자로 배열로 만들어서 N, S, P값으로 DancingWithTheGoogler 클래스를 생성하고 뒤에 나오는 각 구글로의 totals포인트를 리스트로 만들어서 solveProblem(scores)를 호출했습니다.
DancingWithTheGoogler는 알고리즘 푸는데 집중하느라고 클래스가 잘 구현되어 있지는 않습니다. 각 문제별로 하나의 DancingWithTheGoogler객체가 되고 멤버변수로 numberOfGooglers, suprigingCount, bestResult를 가지고 있습니다. 사실 numberOfGooglers는 어차피 리스트로 관리하기 때문에 없어도 되지만 굳이 지우지 않았습니다.
findCandidateTripletOfScores(totalPoints:Long)는 total Point를 받아서 세 심사위원의 점수가 될 수 있는 triplet of scores의 후보군을 찾는 함수이고 isSurprising(tripletOfScores:(Long, Long, Long))은 전달한 triplet of scores가 surprising한지를 판단하고 getMaximumPoint(tripletOfScores: (Long, Long, Long))는 triplet of scores에서 최대값을 리턴해 줍니다. getGroupOfCandidateTripletOfScores(totalPoints:List[Long])는 total points의 리스트를 전달하면 findCandidateTripletOfScores를 사용해서 전체 triplet of scores 후보군의 리스트를 합쳐서 리턴합니다.
이 메서드들을 사용해서 solveProblem(totalPoints:List[Long])에서 문제를 풀어서 결과값을 리턴합니다. 문제는 surprising의 숫자가 주어지고 그중에서 best result를 찾도록 되어 있지만 어차피 둘다 조건이므로 저는 triplet of scores의 후보군을 찾을 때 best result조건을 먼저 적용했습니다. surprisng을 적용한 다음에 best result를 찾는것 보다는 best result를 먼저 적용하는 것이 후보군을 줄여서 판단하기 쉽다고 생각했기 때문입니다. 그래서 findCandidateTripletOfScores에서 후보군을 찾을 때 최대값이 best result보다 큰지까지 한꺼번에 판단해서 리턴하도록 했습니다. totalPoints가 0이나 1경우에는 나올 수 있는 후보군이 1개 뿐이기 때문에 따로 처리를 했고 이 후보군이 best result보다 작을 경우에는 Nil을 리턴했습니다. 손으로 문제를 풀다보니까 패턴이 어느정도 보여서 total point를 3으로 나누고 그 값(basePoints)을 totalPoints에서 빼서 홀수가 나오면 basePoints에서 1을 빼준 값에서 시작합니다.
여기서 totalPoints에서 basePoinst를 뺀 값을 2로 나눈 값과 basePoints의 차이가 2 이내인 범위에서만 루프를 돌면서 totalPoints에서 basePoinst를 뺀 값을 2로 나눈 값이 basePoint와 같으면 순차적인 값이 됩니다. 즉 totalPoinst가 15이면 basePoints가 5가 되고 15-5가 짝수이므로 basePoints는 5가 됩니다. (15-5)/2가 5와 같으므로 결과는 (4,5,6)이 됩니다. 그리고 basePoints는 순회를 돌 때마다 2씩 올려주고 위와 같은 경우가 아닐 경우에는 totalPoints에서 basePoinst를 뺀 값을 2로 나눈 값으로 triplet of Scores를 만듭니다. 즉, totalPoints가 20이면 basePoints가 6이 되므로 (6,7,7)이 됩니다. 이렇게 만들어진 후보군에 surprising의 갯수의 조건을 체크해서 몇몇의 구글러가 조건에 맞는지를 판단해서 결과값을 생성합니다.(말로 설명하려니 어렵군요. ㅎ)
package kr.ne.outsider
import org.scalatest.Spec
import org.scalatest.BeforeAndAfter
class DancingWithTheGooglerSpec extends Spec with BeforeAndAfter {
var dance:DancingWithTheGoogler = null
before {
dance = new DancingWithTheGoogler(3, 0, 0)
}
describe("Dancing WIth the Googler") {
describe("#Basic") {
it("initialize object with basic data") {
val dwg = new DancingWithTheGoogler(3, 1, 8)
assert(dwg.numberOfGooglers === 3)
assert(dwg.suprigingCount === 1)
assert(dwg.bestResult === 8)
}
}
describe("#triplet of scores") {
it("total points 0 should be [(0, 0, 0)] triplet of scores") {
val result = dance findCandidateTripletOfScores(0l)
assert(result.length === 1)
assert(result(0) === (0l, 0l, 0l))
}
it("total points 8 should be [(2, 3, 3), (4, 2, 2)] triplet of scores") {
val result = dance findCandidateTripletOfScores(8l)
assert(result.length === 2)
assert(result(0) === (2l, 3l, 3l))
assert(result(1) === (4l, 2l, 2l))
}
it("total points 23 should be [(7, 8, 8), (9, 7, 7)] triplet of scores") {
val result = dance findCandidateTripletOfScores(23l)
assert(result.length === 2)
assert(result(0) === (7l, 8l, 8l))
assert(result(1) === (9l, 7l, 7l))
}
it("total points 22 should be [(6, 8, 8), (8, 7, 7)] triplet of scores") {
val result = dance findCandidateTripletOfScores(22l)
assert(result.length === 2)
assert(result(0) === (6l, 8l, 8l))
assert(result(1) === (8l, 7l, 7l))
}
it("total points 21 should be [(6, 7, 8), (7, 7, 7)] triplet of scores") {
val result = dance findCandidateTripletOfScores(21l)
assert(result.length === 2)
assert(result(0) === (6l, 7l, 8l))
assert(result(1) === (7l, 7l, 7l))
}
it("total points 1 should be [(1, 0, 0)] triplet of scores") {
val result = dance findCandidateTripletOfScores(1l)
assert(result.length === 1)
assert(result(0) === (1l, 0l, 0l))
}
it("total points 2 should be [(0, 1, 1), (2, 0, 0)] triplet of scores") {
val result = dance findCandidateTripletOfScores(2l)
assert(result.length === 2)
assert(result(0) === (0l, 1l, 1l))
assert(result(1) === (2l, 0l, 0l))
}
it("total points 11 with 5 best results should be [(5, 3, 3)] triplet of scores") {
val dwg = new DancingWithTheGoogler(3, 1, 5)
val result = dwg findCandidateTripletOfScores(11l)
assert(result.length === 1)
assert(result(0) === (5l, 3l, 3l))
}
it("total points 0 with 5 best results should be [] triplet of scores") {
val dwg = new DancingWithTheGoogler(3, 1, 5)
val result = dwg findCandidateTripletOfScores(0l)
assert(result.length === 0)
}
it("total points 26 with 3 best results should be [(8,9,9), (10,8,8)] triplet of scores") {
val dwg = new DancingWithTheGoogler(2, 2, 3)
val result = dwg findCandidateTripletOfScores(26l)
assert(result.length === 2)
assert(result(0) === (8l, 9l, 9l))
assert(result(1) === (10l, 8l, 8l))
}
it("total points 3 with 3 best results should be [] triplet of scores") {
val dwg = new DancingWithTheGoogler(2, 2, 3)
val result = dwg findCandidateTripletOfScores(3l)
assert(result.length === 0)
}
}
describe("#Surprising") {
it("(7, 7, 7)] should be not surprising") {
assert((dance isSurprising((7, 7, 7))) === false)
}
it("(9, 7, 7)] should be surprising") {
assert((dance isSurprising((9, 7, 7))) === true)
}
it("(6, 8, 8)] should be surprising") {
assert((dance isSurprising((6, 8, 8))) === true)
}
it("(4, 5, 6)] should be surprising") {
assert((dance isSurprising((4, 5, 6))) === true)
}
it("(3, 4, 4)] should be not surprising") {
assert((dance isSurprising((3, 4, 4))) === false)
}
it("(0, 1, 2)] should be surprising") {
assert((dance isSurprising((0, 1, 2))) === true)
}
}
describe("#Solving") {
it("3 1 5 15 13 11 should be 3") {
val dwg = new DancingWithTheGoogler(3, 1, 5)
val result = dwg solveProblem(List(15l, 13l, 11l))
assert(result === 3)
}
it("3 0 8 23 22 21 should be 2") {
val dwg = new DancingWithTheGoogler(3, 0, 8)
val result = dwg solveProblem(List(23l, 22l, 21l))
assert(result === 2)
}
it("2 1 1 8 0 should be 1") {
val dwg = new DancingWithTheGoogler(2, 1, 1)
val result = dwg solveProblem(List(8l, 0l))
assert(result === 1)
}
it("6 2 8 29 20 8 18 18 21 should be 3") {
val dwg = new DancingWithTheGoogler(6, 2, 8)
val result = dwg solveProblem(List(29l, 20l, 8l, 18l, 18l, 21l))
assert(result === 3)
}
it("2 2 3 26 3 should be 1") {
val dwg = new DancingWithTheGoogler(2, 2, 3)
val result = dwg solveProblem(List(26l, 3l))
assert(result === 1)
}
}
}
}
알고리즘 문제는 TDD를 적용하기에 좀 좋기 때문에 나름 TDD로 작성했습니다.(사실은 BDD스타일이지만요) ScalaTest는 여러가지 방법을 제공하는데 익숙치가 않아서 assert만 사용했습니다. small input을 제출하면서 2번을 실패했었는데 생각하지 못했던 경우에 대한 추가케이스를 테스트로 만들어서 작성하고 나니 small input을 통과한 후에 별 어려운 없이 large input도 통과할 수 있었습니다.(테스트는 역시 이럴때 보람이...)
SBT에서 테스트를 수행하면 위처럼 다 성공합니다. ㅎㅎㅎ 통과하는 테스트를 보니까 기분이 좋군요. 처음 써보는 Scala Test라서 테스트명을 영어로 적긴 했는데 역시 테스트는 한글로 적는데 더 명확하고 좋은듯 합니다.
제출 리스트입니다. Small input에서 2번 틀리고 3번째에 통과한 뒤에 Large까지 통과했습니다. 2번째 Incorrect 틀랬을 때는 짜증나서 거의 포기할 뻔했는데 새벽까지 네피림님도 같이 풀고 있어서(문제 이해할려고 꼬신덕에...) 참고 풀었더니 결국 통과했습니다. ㅎ
20번 획득해서(QR통과하려면 20이상이어야 합니다.) 15653위로 통과했네요. 첫 QT통과라 기분이 좋습니다. 저장소에 관리할 소스는 아니라서 블로그에 정리해서 올려봅니다.
Comments