Google Code Jam 2020 QR 1 Vestigium 풀이

구글 코드잼 2020 Qualification Round 1번 문제입니다. 첫 번째 문제답게 난이도는 그리 높지 않습니다. 문제를 읽어 봅시다.

---

---

문제를 해석해 봅시다.

---

Vestigium은 라틴어로 "추적하다(trace)"를 의미합니다. 이 문제에서 우리는 Latin squares와 매트릭스 traces를 다룹니다.

정방 행렬(square matrix)에서의 trace는 주 대각선(왼쪽 위에서 오른쪽 아래로 긋는)의 합입니다.

N-by-N 매트릭스 이면서 행(row)과 열(column)의 숫자가 N개의 서로 다른 숫자이면서 반복되지 않는다면 Latin square입니다.

주어지는 매트릭스는 1과 N사이의 숫자로 이루어져 있습니다. 우리는 trace를 구하고 싶고 이 매트릭스가 natural Latin square인지 확인하려고 합니다. 좀 더 설명을 하자면 단순히 이것이 natural Latin square인지 아닌지를 알려달라는 것이 아니고 반복되는 숫자를 가진 행(row)의 개수와 열(column)의 개수를 계산해 주세요.

---

애초에 matrix, trace, latin square가 뭔지 알고 있다면 문제가 금방 이해가 될 거 같습니다. 하지만 저는 잘 몰라서 꼼꼼히 읽어 봤네요. 아무튼 왼쪽 위부터 오른쪽 아래로 이어지는 대각선 값들의 합을 구합니다.

그리고 가로로 같은 수가 있는 게 몇 개 인지, 세로로 같은 수가 있는 게 몇 개 인지 구하면 됩니다.

입력값

첫 줄에는 테스트 케이스 개수 T 가 나옵니다. 다음에는 N 이 나옵니다. N-by-N 매트릭스의 N입니다. 4가 나오면 4-by-4 매트릭스라는 말입니다. 다음에는 N 줄 만큼의 매트릭스 값이 나옵니다.

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 3

 

문제들의 포맷은 비슷한 형식으로 많이 나오니 이런 형식의 입력값에 대한 처리는 익숙해지는 것이 좋습니다.

출력

Case #x: k r c

x는 테스트 케이스의 번호입니다. 1부터 시작합니다.

k는 trace. 좌상-우하로 이어지는 대각선 합입니다.

r는 반복되는 값이 있는 행(row) 개수입니다.

c는 반복되는 값이 있는 열(column) 개수입니다. 앞서 나온 입력값에 대한 출력 값은 다음과 같습니다.

Case #1: 4 0 0
Case #2: 9 4 4
Case #3: 8 0 2

처음 예제를 다시 볼까요?

1 2 3 4
2 1 4 3
3 4 1 2
4 3 2 1

trace는 1+1+1+1=4입니다. 가로로 겹치는 숫자가 있는 행이 없네요. 0입니다. 세로로도 겹치는 숫자가 있는 열이 없습니다. 0입니다. 그래서 4 0 0 이 나왔습니다.

두 번째 예제를 봅니다.

2 2 2 2
2 3 2 3
2 2 2 3
2 2 2 2

trace는 2+3+2+2=9. 가로로 다 겹치니 4. 세로로도 다 겹치니 4입니다. 9 4 4네요.

마지막 예제도 봅니다.

2 1 3
1 3 2
1 2 3

trace는 2+3+3=8. 가로로는 겹치는 게 없네요. 0입니다. 세로로는 첫 번째 세 번째가 겹쳐서 2입니다. 8 0 2입니다.

코드 구현

코드로 구현해 봅시다. 첫 번째 문제이니 조금 천천히 나가봅시다.

tc = int(input())

첫 번째 입력값을 숫자로 바꿔서 tc에 저장합니다. T의 개수라고 tc라고 했습니다. tc만큼 반복문을 돌립니다. 그리고 output포맷으로 출력합니다. trace, rbad, cbad값은 임의로 0으로 넣었습니다.

tc = int(input())

for t in range(tc):
  trace = 0
  rbad = 0
  cbad = 0
  print("Case #" + str(t+1) + ": ", trace, rbad, cbad)

matrix를 N-by-N 매트릭스에 저장합니다. 배열 안에 배열을 넣는 2차원 배열로 만듭니다. 배열은 python에서는 list입니다.

tc = int(input())

for t in range(tc):
  m = []
  nc = int(input())
  for n in range(nc):
    m.append([int(x) for x in input().split()])
    
  trace = 0
  rbad = 0
  cbad = 0
  print("Case #" + str(t+1) + ": ", trace, rbad, cbad)

m이라는 list에 n 줄 만큼 읽으면서 각 숫자를 쪼개서 정수형으로 만든 배열을 m에 한 줄씩 추가합니다. 코드를 많이 축약해서 초보자에게는 이해가 좀 어려울 수 있습니다.

  for n in range(nc):
    m.append([int(x) for x in input().split()])

을 풀어서 적으면 다음과 같습니다.

  for n in range(nc):
    line = input() # "1 2 3 4" 형식의 줄을 읽습니다.
    row_list = line.split() # split함수를 호출하면 공백을 기준으로 쪼갭니다. [1,2,3,4]가 됩니다.
    row_int_list = [] # 정수로 바꿔서 저장할 list를 만듭니다
    for r in row_list:
      r_int = int(r) # r이 문자열이기 때문에 숫자로 바꿉니다.
      row_int_list.append(r_int) # 숫자로 바꾼 값을 row_int_list에 하나씩 넣습니다.
    
    m.append(row_int_list)

처음에는 축약 방식이 어려울 수 있지만 적응하면 짧게 적는 게 더 편합니다.

이제 본격적으로 trace, rbad, cbad를 구합니다.

tc = int(input())

for t in range(tc):
  m = []
  nc = int(input())
  for n in range(nc):
    m.append([int(x) for x in input().split()])
    
  trace = 0
  rbad = 0
  cbad = 0
  
  for n in range(nc):
    trace += m[n][n]
    
    if len(set(m[n])) != nc:
      rbad += 1

    if len(set([m[x][n] for x in range(nc)])) != nc:
      cbad += 1
        
  print("Case #" + str(t+1) + ": ", trace, rbad, cbad)

nc만큼 반복문을 돌립니다. 4-by-4 매트릭스 이면 4번 돌게 됩니다.

trace += m[n][n]로 대각선 합을 구합니다. m[0][0] + m[1][1] + m[2][2] + m[3][3]이 되겠죠?

    if len(set(m[n])) != nc:
      rbad += 1

m[n]을 하면 list가 한 줄씩 나옵니다. m[0]은 첫 번째 행, m[1]은 두 번째 행, 이런 식이죠.

set함수로 list를 감싸면 중복된 값을 제거 한 set이 나옵니다. set([1,1,2,2])을 실행하면 1,2가 나옵니다. 기존 list의 개수와 set의 개수가 같으면 중복된 값이 없다는 말이고, 개수가 다르면 중복된 값이 있어서 제거되었다는 의미가 됩니다. 중복된 값이 있으면 rbad를 1 증가시킵니다.

다음은 좀 복잡하네요.

    if len(set([m[x][n] for x in range(nc)])) != nc:
      cbad += 1

[m[x][n] for x in range(nc)]와 같은 축약 방식이 익숙하지 않은 분들을 위해 풀어서 적으면 다음과 같습니다.

column = []
for x in range(nc):
  column.append(m[x][n])

세로로 한 줄을 읽어와서 새로운 list에 넣는다는 의미입니다. 그다음은 앞서 나온 것처럼 set으로 중복된 것을 제거하고 길이를 비교합니다.

이미 완성된 코드가 나왔지만 마무리로 한 번 더 보겠습니다.

tc = int(input())

for t in range(tc):
  m = []
  nc = int(input())
  for n in range(nc):
    m.append([int(x) for x in input().split()])
    
  trace = 0
  rbad = 0
  cbad = 0
  
  for n in range(nc):
    trace += m[n][n]
    
    if len(set(m[n])) != nc:
      rbad += 1

    if len(set([m[x][n] for x in range(nc)])) != nc:
      cbad += 1
        
  print("Case #" + str(t+1) + ": ", trace, rbad, cbad)