지난 토요일 madfinger님 그리고 다른 부트캠프 동기들과 함께 구글 코드잼에 참여해 봤습니다. 총 5문제 100점 만점이며 3번 문제의 첫번째 테스트 세트를 통과해야 30점이 되어 본선 라운드 자격이 주어집니다.
토요일 점심부터 새벽까지 시간동안 해봤는데 세번째 문제에서 속도 요건 때문에 통과하지 못해 결국 30점을 맞추지 못했습니다. 문제에 맞춰 코드를 짜는 과정이 재미있었지만 아직 실력의 한계도 많이 느꼈습니다. 참가 기념으로? 1~3번 문제를 간단히 정리해 봤습니다. 코드는 정리가 된다면 추가해 보려고 합니다.
1. Vestigium
N by N 행렬이 주어졌을 때 숫자 3개를 출력해야 합니다. 주대각선의 합, 같은 숫자가 있는 행의 개수, 같은 숫자가 있는 열의 개수 이렇게 3개입니다.
input
3 # 케이스 개수
4 # 행렬 크기
1 2 3 4
2 1 4 3
3 4 1 2
4 3 2 1
4
2 2 2 2
2 3 2 3
2 2 2 3
2 2 2 2
3
2 1 3
1 3 2
1 2 3output
Case #1: 4 0 0
Case #2: 9 4 4
Case #3: 8 0 2
정리
처음에는 입력값을 읽고 출력하는 것도 쉽지 않았습니다. 입력값을 읽으면서 3개의 숫자 값을 구하고 출력하는 방식으로 풀었습니다.
2. Nesting Depth
숫자 여러 개가 나열되어 있습니다. 각 숫자는 그 숫자만큼 괄호가 씌어져야 하며, 여러 경우의 수가 있는데 그 중에서도 최소의 괄호 개수로 출력해야 합니다.
input
4 # 케이스 개수
0000
101
111000
1output
Case #1: 0000
Case #2: (1)0(1)
Case #3: (111)000
Case #4: (1)정리
여러가지 경우를 보다보면 패턴이 보입니다. 다음에 오는 숫자가 크면 숫자 차이만큼 (를 작으면 차이만큼 )를 붙여주면 됩니다. 처음 숫자는 0으로 시작해 비교하고 마지막 숫자 만큼 )를 붙여주는 걸로 마무리 했습니다. 처음과 끝에 0을 붙이고 밑줄의 작업을 하는 것과 같습니다.
3. Parenting Partnering Returns
N개의 일을 2명이 해야합니다. 각각의 일은 시작과 끝 시간이 정해져 있고 한 명이 한 번에 한 개의 일만 할 수 있습니다. N개의 일에 2명을 배정하는 여러 방법 중 하나를 출력하면 됩니다. 모든 일을 다 할 수 없다면 IMPOSSIBE을 출력합니다. 시작시간과 끝시간이 같은 다른 일 두개는 이어서 할 수 있습니다.
input
4 # 케이스 개수
3 # 일의 개수
360 480 # 시작시간, 끝시간(하루를 분단위로)
420 540
600 660
3
0 1440
1 3
2 4
5
99 150
1 100
100 301
2 5
150 250
2
0 720
720 1440output
Case #1: CJC
Case #2: IMPOSSIBLE
Case #3: JCCJJ
Case #4: CC
정리
두 사람에게 일을 배정하는데 둘다 일을 할 수 없으면 IMPOSSIBLE을 출력합니다. 저는 일의 시간 range를 list로 만들어 시작시간을 각 사람의 리스트에 추가하는 방식으로 했습니다. 시작과 끝 시간 비교하는 방법도 가능할 것 같은데 속도를 고려해야 하기 때문에 다른 방법을 고안해야 합니다.
