[Google Kick Start] 2021 구글 킥스타트 Round D Arithmetic Square 풀이

 

 

문제

---

https://codingcompetitions.withgoogle.com/kickstart/round/00000000004361e3/000000000082b813

Kick Start - Google’s Coding Competitions

 

 

나의 풀이

---

Arithmetic sequence인지 아닌지 검사하는 방법은 쉬우니 중요한 가운데 원소의 선택에 대해서만 고민하면 된다. 가운데 원소(1행1열 원소)를 기준으로 가로, 세로, 대각선 2개 방향에 대해서 이들이 최대한 많이 arithmetic sequence가 되도록 하는 원소가 무엇일지 생각해봐야 한다. 

만약 arithmetic sequence에서 a1, a3이 주어졌다면 a2는 a1과 a3의 평균이다. 따라서 1행 1열 원소를 기준으로 가로, 세로, 대각선 2개 방향에 대해 이 같은 양 끝 원소의 평균을 구하고 가장 빈번하게 등장하는 숫자를 가운데 원소로 하면 된다. 여기서 주의할 점은 만약 a1=10, a3=9라면 2로 나누었을 때 정수가 아닌 9.5가 된다. 이러한 경우는 배제하면 된다. 왜냐하면 애초에 문제 조건에서 interger로 이루어진 행렬이라 했으므로.

 

코드

---

T = int(input())
for t in range(T):
    A = []
    for i in range(3):
        temp = list(map(int, input().split()))
        if i==1:
            temp = [temp[0]] + ['N'] + [temp[1]]
        A.append(temp)
    avg = []
    if (A[0][0]+A[2][2])%2 == 0:
        avg.append((A[0][0]+A[2][2])//2)
    if (A[0][1]+A[2][1])%2==0:
        avg.append((A[0][1]+A[2][1])//2)
    if (A[0][2]+A[2][0])%2==0:
        avg.append((A[0][2]+A[2][0])//2)
    if (A[1][0]+A[1][2])%2==0:
        avg.append((A[1][0]+A[1][2])//2)
    avg_cnt = {}
    for k in avg:
        if k not in avg_cnt:
            avg_cnt[k] = 1
        else:
            avg_cnt[k] += 1
    # find max count
    max_cnt = 0
    for k in avg_cnt:
        max_cnt = max(max_cnt, avg_cnt[k])
    for k in avg_cnt:
        if avg_cnt[k]==max_cnt:
            max_cnt_num = k
    A[1][1] = max_cnt_num
    # 4 edge check
    edge_cnt = 0
    if A[0][1]-A[0][0] == A[0][2]-A[0][1]:
        edge_cnt += 1
    if A[1][2]-A[0][2] == A[2][2]-A[1][2]:
        edge_cnt += 1
    if A[2][1]-A[2][0] == A[2][2]-A[2][1]:
        edge_cnt += 1
    if A[1][0]-A[0][0] == A[2][0]-A[1][0]:
        edge_cnt += 1
    ans = max_cnt + edge_cnt
    print(f"Case #{t+1}: " + str(ans))