[백준] # 17140. 이차원 배열과 연산 (파이썬)

문제 링크

https://www.acmicpc.net/problem/17140

17140번: 이차원 배열과 연산

 

문제 내용

크기가 3×3인 배열 A가 있다. 배열의 인덱스는 1부터 시작한다. 1초가 지날때마다 배열에 연산이 적용된다.

• R 연산: 배열 A의 모든 행에 대해서 정렬을 수행한다. 행의 개수 ≥ 열의 개수인 경우에 적용된다.
• C 연산: 배열 A의 모든 열에 대해서 정렬을 수행한다. 행의 개수 < 열의 개수인 경우에 적용된다.

한 행 또는 열에 있는 수를 정렬하려면, 각각의 수가 몇 번 나왔는지 알아야 한다. 그 다음, 수의 등장 횟수가 커지는 순으로, 그러한 것이 여러가지면 수가 커지는 순으로 정렬한다. 그 다음에는 배열 A에 정렬된 결과를 다시 넣어야 한다. 정렬된 결과를 배열에 넣을 때는, 수와 등장 횟수를 모두 넣으며, 순서는 수가 먼저이다.

예를 들어, [3, 1, 1]에는 3이 1번, 1가 2번 등장한다. 따라서, 정렬된 결과는 [3, 1, 1, 2]가 된다. 다시 이 배열에는 3이 1번, 1이 2번, 2가 1번 등장한다. 다시 정렬하면 [2, 1, 3, 1, 1, 2]가 된다.

정렬된 결과를 배열에 다시 넣으면 행 또는 열의 크기가 달라질 수 있다. R 연산이 적용된 경우에는 가장 큰 행을 기준으로 모든 행의 크기가 변하고, C 연산이 적용된 경우에는 가장 큰 열을 기준으로 모든 열의 크기가 변한다. 행 또는 열의 크기가 커진 곳에는 0이 채워진다. 수를 정렬할 때 0은 무시해야 한다. 예를 들어, [3, 2, 0, 0]을 정렬한 결과는 [3, 2]를 정렬한 결과와 같다.

행 또는 열의 크기가 100을 넘어가는 경우에는 처음 100개를 제외한 나머지는 버린다.

배열 A에 들어있는 수와 r, c, k가 주어졌을 때, A[r][c]에 들어있는 값이 k가 되기 위한 최소 시간을 구해보자.

 

입력

첫째 줄에 r, c, k가 주어진다. (1 ≤ r, c, k ≤ 100)

둘째 줄부터 3개의 줄에 배열 A에 들어있는 수가 주어진다. 배열 A에 들어있는 수는 100보다 작거나 같은 자연수이다.

 

출력

A[r][c]에 들어있는 값이 k가 되기 위한 연산의 최소 시간을 출력한다. 100초가 지나도 A[r][c] = k가 되지 않으면 -1을 출력한다.

 

IDEA

R연산과 C연산은 행과 열만 서로 바뀔뿐이지 계산은 같으므로, 배열을 회전시켜버리는 방법을 사용했다. 파이썬의 zip과 map을 사용하여 한 줄로 회전가능하다. a = list(map(list,zip(*a)))

Counter 모듈을 사용하면 내부 계산 또한 한줄로 가능하다. sorted(Counter(a[i]).most_common(), key=lambda k : k[1]) 

Counter의 most_common() 메소드는 배열의 원소 중 가장 많은 개수의 원소부터 (원소, 개수)의 튜플로 묶어서 반환해준다. 그걸 역정렬을 시켜서 문제의 요구를 충족시켜줬다.

또한 배열의 크기가 변하면서 A[r][c]에 해당하는 원소가 없어 IndexError가 발생할 수 있으므로 예외처리가 필요하다.

 

CODE

# 17140. 이차원 배열과 연산 - 골드4
# 배열 회전에 zip()사용, 함수로 만들기 => 성공! 애초에 while 조건에서 indexError가 난 거였다.

# A[r][c]가 k값이 나올 때 까지 연산을 수행하는데, 연산을 진행하다보면 
# 배열 A의 크기가 변하면서 A[r][c]에 해당하는 원소가 없어 IndexError가 발생할 수 있다.
# → 예외처리 필요
from collections import Counter
r,c,k = map(int,input().split())
a = [list(map(int,input().split())) for _ in range(3)]
t = 0
len_row = 3
len_col = 3
r -= 1
c -= 1
while 1:
    # 조건에 맞으면 중단.
    if len(a) > r and len(a[0]) > c:
        if a[r][c] == k :
            break
    t += 1
    if t > 100:
        t = -1
        break
    if len_row < len_col:
        a = list(map(list,zip(*a)))
        x, y = len_col, len_row
    else : 
        x, y = len_row, len_col
    for i in range(x):
        count_0 = a[i].count(0)
        for _ in range(count_0):
            a[i].remove(0)
        a[i].sort()
        temp = sorted(Counter(a[i]).most_common(), key=lambda k : k[1])
        a[i].clear()
        for j in range(len(temp)):
            a[i].append(temp[j][0])
            a[i].append(temp[j][1])
        if len(a[i]) > 100:     # 크기가 100이 넘어가면 슬라이싱
            a[i] = a[i][:100]
        y = max(y, len(a[i]))
    for i in range(x):
        if len(a[i]) < y:
            a[i] += [0]*(y-len(a[i]))
    if len_row < len_col :
        a = list(map(list,zip(*a)))
        len_row = y
        len_col = x
    else:
        len_row = x
        len_col = y
    # print(t)
    # for i in a:
    #     print(*i)
    # print()
print(t)

 

사용 알고리즘

구현

 

풀이 평

시간제한이 0.5초인 점이 가장 힘들게 했다. 몇 일동안 나를 힘들게 한 문제지만, 배열 한 줄 회전, Counter모듈에 대해 공부할 수 있었다.