관리 메뉴

준호씨의 블로그

Google Code Jam 2020 QR 1 Vestigium 풀이 본문

개발이야기/PS - Problem Solving, 알고리즘

Google Code Jam 2020 QR 1 Vestigium 풀이

준호씨 2020. 4. 8. 23:56
반응형

구글 코드잼 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)

 

반응형
0 Comments
댓글쓰기 폼