[구글 코딩 잼] Magic Trick - Qualification Round Problem 1
2014년 Google Code Jam Qualification Round 에 참가했습니다. 구글 코드잼은 구글에서 진행하는 프로그램으로서 2003년부터 지금까지 계속 진행되고 있는 일종의 코딩 대회입니다. 하지만 대회라고 해서 정해진 장소 한곳에 모여서 하는게 아니라 Qualification Round 에서 Round 1, Round 2, Round 3 까지는 집에서나 컴퓨터만 있으면 어디에서나 참가할수 있는 코딩 경기 대회입니다. 일정한 시간에 프로그래밍 문제가 주어지고 주어진 시간안에 그 문제를 풀고 답을 제출하면 컴퓨터가 결과를 측정해서 랭킹을 주는거죠. Qualification Round 에서는 총 27시간이 주어졌는데요. 다행히도 전 4 문제중에 2 문제를 풀어서 25점을 받고 Round 1 에 겨우 참가할수 있게 되었습니다 ^^
제 실력이 어느정도인지 알고 싶었어요. 그렇다고 이길수 있다는 기대는 없었고 그냥 재미반 연습반 식으로 참여했어요. 그래도 이번에는 세계랭킹 1000위 안에라도 들어서 T-Shirt 라도 받고 싶은 욕심은 내심 있었던것 같아요 ^^ 코드 잼에 대한 자세한 내용은 아래 링크에서 알수 있습니다.
https://code.google.com/codejam
현재 Qualification Round 랭킹 1위는 Belarus 의 Gennady.Korotkevich 이란 참가자네요. 알고보니까 이분이 Topcoder Open 이나 러시아 코딩 대회에서도 일등을 다 차지했을 정도록 기록이 엄청나네요... 그리고 나이는 15살 ㄷㄷㄷ 코딩 문제 4개를 58분 3초만에 풀다니 정말 넘사벽이네요 ㅠ
첫번째 문제에 대해서 설명하겠습니다. 문제는 다음과 같습니다.
문제 (Problem)
[Source: https://code.google.com/codejam/contest/2974486/dashboard]
This contest is open for practice. You can try every problem as many times as you like, though we won't keep track of which problems you solve. Read the Quick-Start Guide to get started.
Note: To advance to the next rounds, you will need to score 25 points. Solving just this problem will not give you enough points.
Problem
Recently you went to a magic show. You were very impressed by one of the tricks, so you decided to try to figure out the secret behind it!
The magician starts by arranging 16 cards in a square grid: 4 rows of cards, with 4 cards in each row. Each card has a different number from 1 to 16 written on the side that is showing. Next, the magician asks a volunteer to choose a card, and to tell him which row that card is in.
Finally, the magician arranges the 16 cards in a square grid again, possibly in a different order. Once again, he asks the volunteer which row her card is in. With only the answers to these two questions, the magician then correctly determines which card the volunteer chose. Amazing, right?
You decide to write a program to help you understand the magician's technique. The program will be given the two arrangements of the cards, and the volunteer's answers to the two questions: the row number of the selected card in the first arrangement, and the row number of the selected card in the second arrangement. The rows are numbered 1 to 4 from top to bottom.
Your program should determine which card the volunteer chose; or if there is more than one card the volunteer might have chosen (the magician did a bad job); or if there's no card consistent with the volunteer's answers (the volunteer cheated).
Solving this problem
Usually, Google Code Jam problems have 1 Small input and 1 Large input. This problem has only 1 Small input. Once you have solved the Small input, you have finished solving this problem.
Input
The first line of the input gives the number of test cases, T. T test cases follow. Each test case starts with a line containing an integer: the answer to the first question. The next 4 lines represent the first arrangement of the cards: each contains 4 integers, separated by a single space. The next line contains the answer to the second question, and the following four lines contain the second arrangement in the same format.
Output
For each test case, output one line containing "Case #x: y", where x is the test case number (starting from 1).
If there is a single card the volunteer could have chosen, y should be the number on the card. If there are multiple cards the volunteer could have chosen, y should be "Bad magician!", without the quotes. If there are no cards consistent with the volunteer's answers, y should be "Volunteer cheated!", without the quotes. The text needs to be exactly right, so consider copying/pasting it from here.
Limits
1 ≤ T ≤ 100.
1 ≤ both answers ≤ 4.
Each number from 1 to 16 will appear exactly once in each arrangement.
Sample
Input
3
2
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16
3
1 2 5 4
3 11 6 15
9 10 7 12
13 14 8 16
2
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16
2
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16
2
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16
3
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16
Output
Case #1: 7
Case #2: Bad magician!
Case #3: Volunteer cheated!
문제 푸는 과정 (Approach to the Problem Solving)
대충 문제는 이렇습니다. 마술사가 1 에서 16 까지 적어져 있는 카드를 한줄마다 카드 4개씩 그렇게 4줄로 깔고 저보고 카드 하나를 뽑아보라고 합니다. 그리고 그 카드의 숫자는 마술사가 모르고 있지만 저보고 카드가 몇번째 줄에 있었는지만 말하라고 합니다. 그리고 한번 더 16개의 카드를 셔플해서 다시 한번 똑같은 게임을 반복합니다. 그러면 마술사는 그 2번의 게임을 통해서 저의 카드가 무슨 카드였는지 맞추는 게임입니다. 그리고 마술사가 정확하게 맞추는게 가능하면 카드에 적혀진 숫자를 출력하고 만약에 하나도 맞추는게 불가능한 배열이면 Volunteer cheated! 라는 String 을 출력하고 여러가지 카드의 결과가 가능하면 Bad magician! 이란 String 을 출력합니다.
인풋으로는 각 케이스마다 다음의 정보들이 주어집니다.
- 카드의 행 번호 (row number)
- 4 x 4 의 랜돔의 카드 배열 2번
우선 두개의 함수를 만들었습니다. 결과에 따라서 String 메시지만 프린트해주는 getMagicTrickMessage(int resultMagic) 라는 함수와 실제 문제를 푸는 getMagicTrickAnswer(String[] firstSetCards, String[] secondSetCards) 이란 함수를 만들었습니다. 우선 firstSetCards 의 리스트와 secondSetCards 의 리스트를 메인에서 받으면 가격을 비교해서 몇번이 메치되는지 계산하고 그 가격을 다시 매인에서 getMagicTrickMessage 함수를 불러 메시지를 출력하는 방식을 사용했습니다.
처음에는 array 대신에 Stack 을 쓸려고 있는데 아무래도 그냥 인풋 사이즈도 크지도 않아서 O(N^2) 퍼포먼스로 돌아가더라도 모든 값을 다 계산하는 for 루프 2개를 써서 해결했습니다. 아마 이 문제는 어렵다기 보다는 문제를 이해하는 시간과 인풋을 처리하는게 좀 까다로웠던것 같습니다.
코드 (Code)
프로그래밍 언어는 자바입니다.
package com.codingjam;
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.FileReader;
import java.io.FileWriter;
public class MagicTrick {
private static final String INPUT1 = "./input/A-small-attempt5.in";
private static final String OUTPUT1 = "./output/A-small-attempt5.out";
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new FileReader(INPUT1));
BufferedWriter bw = new BufferedWriter(new FileWriter(OUTPUT1));
String line = br.readLine();
int N = Integer.parseInt(line);
for(int i=0; i < N; ++i) {
int answerFirst = Integer.parseInt(br.readLine().trim());
String[][] firstSetCards = new String[4][4];
firstSetCards[0] = br.readLine().split(" ");
firstSetCards[1] = br.readLine().split(" ");
firstSetCards[2] = br.readLine().split(" ");
firstSetCards[3] = br.readLine().split(" ");
int answerSecond = Integer.parseInt(br.readLine().trim());
String[][] secondSetCards = new String[4][4];
secondSetCards[0] = br.readLine().split(" ");
secondSetCards[1] = br.readLine().split(" ");
secondSetCards[2] = br.readLine().split(" ");
secondSetCards[3] = br.readLine().split(" ");
int resultMagic = getMagicTrickAnswer(firstSetCards[answerFirst-1], secondSetCards[answerSecond-1]);
String message = getMagicTrickMessage(resultMagic);
bw.write("Case #" + (i+1) + ": " + message);
if(i < (N-1)) {
bw.write("\n");
}
}
br.close();
bw.close();
}
public static int getMagicTrickAnswer(String[] firstSetCards, String[] secondSetCards) {
int counter = 0;
String answer = "";
int size = firstSetCards.length;
for(int i=0; i < size; ++ i) {
String cardFirst = firstSetCards[i];
for(int j=0; j < size; ++ j) {
String cardSecond = secondSetCards[j];
if(cardFirst.equals(cardSecond)) {
answer = cardFirst;
++ counter;
}
}
}
if(counter == 1) {
return Integer.parseInt(answer);
}
else if(counter == 0) {
return -1;
}
else {
return 0;
}
}
public static String getMagicTrickMessage(int resultMagic) {
if(resultMagic == 0) {
return "Bad magician!";
}
else if(resultMagic < 0) {
return "Volunteer cheated!";
}
else {
StringBuffer sb = new StringBuffer();
sb.append(resultMagic);
return sb.toString();
}
}
}