[백준] 17140번 : 이차원 배열과 연산(Python)

문제

크기가 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을 출력한다.

전체코드(Pythono)

from collections import Counter
def operation(m,dir):
    # 가로 연산인 경우 배열을 그대로 저장하지만
    if dir=='R':
        box = m
    # 세로 연산인 경우 행과 열을 전환한다.
    else:
        box = list(zip(*m))
    # 어차피 배열의 개수만큼 가로가 나올것이므로 result는 box의 길이만큼 []를 만든다.
    result = [[] for _ in range(len(box))]
    large = 0
    for loop in range(len(box)):
        temp = []
        # 0의 개수는 세면 안 되므로, 배열에서 0보다 큰 수들만 뺀다.
        box[loop] = list(filter(lambda x:x>0,box[loop]))
        # 행에 있는 숫자들의 개수를 센다
        count = Counter(box[loop])
        # 행에 있는 숫자들(중복없는)을 num에 저장한다.
        num = list(set(box[loop]))
        # temp에 숫자와 숫자의 개수를 임시로 저장한다.
        for i in range(len(num)):
            temp.append([num[i],count[num[i]]])
        
        # 숫자의 개수대로 오름차순 정렬하고 숫자의 개수가 동일하다면 숫자의 오름차순으로 정렬한다.
        temp = sorted(temp,key=lambda x:(x[1],x[0]))
        # 나중에 가장 긴 배열의 크기만큼 0을 채워야 하므로 larage에 가장 긴 배열의 크기를 저장한다.
        large = len(temp)*2 if large < len(temp)*2 else large
        # 정렬한 숫자들을 숫자,숫자개수 순서로 result에 추가한다.
        for i in range(len(temp)):
            result[loop].append(temp[i][0])
            result[loop].append(temp[i][1])
    # 다 정리된 숫자들을 전체 길이에 맞게 추가한다. 짧은 배열은 0으로 채운다.
    for i in range(len(result)):
        for loop in range(large-len(result[i])):
            result[i].append(0)
        # 행 또는 열의 크기가 100을 넘어가는 경우에는 처음 100개를 제외한 나머지는 버린다.
        result[i] = result[i][:100]
    # 세로 연산인 경우 다시 세로로 만들어 준다.
    if dir=='C':
        result = list(zip(*result))
    return result

# r과 c와 k를 입력 받는다.
r,c,k = map(int,input().split())
# 처음에는 3x3 배열이므로 3x3 배열을 만든다.
m = [ [0]*3 for _ in range(3)]

# 3x3 반복문을 돌며 matrix에 값을 입력받는다.
for y in range(3):
    temp = list(map(int,input().split()))
    for x in range(3):
        m[y][x] = temp[x]
# 연산을 한 시간
loop = 0

flag = True
# matrix의 r-1, c-2 이 k거나 시간이 100을 넘어가면 반복문을 탈출한다.
while flag: 
    # 만일 변형한 matrix가 r보다 가로가 짧거나 c보다 세로가 짧을 경우가 있으므로 이 경우에는 matrix r-1,c-1을 구하지 않고 연산만 한다.
    if len(m)>=r and len(m[0])>=c:
        if m[r-1][c-1]!=k and loop<100:
            loop+=1
            # 행 개수가 열보다 크거나 같으면 가로 연산을 한다.
            if len(m) >= len(m[0]):
                m = operation(m,'R')
            else:        
                m = operation(m,'C')
        else:
            flag = False
    else:
        if loop <100:
            loop+=1
            # 행 개수가 열보다 크거나 같으면 가로 연산을 한다.
            if len(m) >= len(m[0]):
                m = operation(m,'R')
            else:        
                m = operation(m,'C')
        else:
            flag = False

# 탈출 했을때 구하고자 하는 배열의 크기와 안 맞으면 정답을 못 찾은것이므로 -1
if len(m)>=r and len(m[0])>=c:
    # 정답을 찾은 시점이 100초 이하라면 구한 시간을 출력(100을 포함)
    if loop <= 100 and m[r-1][c-1]==k:
        print(loop)
    else:
        print(-1)
else:
    print(-1)

알아야할 함수들

• map(int,input().split())
  • map(자료형,변형할 대상) :  변형할 대상을 자료형으로 변형한다.
  • input() : 외부로부터 입력값을 받는다.
  • split() : 괄호안에 값을 기준으로 문자열을 분할한다(아무것도 없을시 띄어쓰기로 분할)
• list(zip(*m))
  • zip(*iterable) : zip은 동일한 개수로 이루어진 자료형을 묶어 주는 역할을 하는 함수이다. 위 문제에서 행과 열을 바꿔주는데 사용했다.
    list(zip([1,2,3],[4,5,6])     -> [(1,4),(2,5),(3,6)]
• list(filter(lambda x:x>0,box[loop]))
  • filter(function,iterable) : 함수에 맞는 조건으로 반복 가능한 자료형을 필터링하여 반환하는 함수이다.
    [ list로 감싸지 않을경우 iterator형으로 나오므로 list로 변환을 해 주자 ]
• Counter(box[loop)
  • Counter : collections에 있는 하나의 메서드로 순환 가능한 자료형에서 아이템들의 개수를 세서 반환한다.
    • 예시 : ex_list = ['kim','kim','park','choi','kim','kim','kim','choi','park','choi']
      print(collections.Counter(ex_lixt))      # Counter({'kim':5,'choi':3,'park':2})
    • 각 아이템의 개수를 개수만큼 만드는것도 가능하다.
      ex) ex_counter = collections.Counter(kim=3,park=2,choi=3)
           print(sorted(ex_counter.elements()))      # ['choi','choi','choi','kim','kim','kim','park','park']
• list(set(box[loop]))
  • set : 중복없이 순환가능한 자료형의 아이템들을 집합으로 만든다.
    list로 감싸면 list형으로 형변환이 된다.
• sorted(temp,key=lambda x:(x[1],x[0])
  • sorted : 원래 순환가능한 자료형의 원본을 변형시키지 않고 정렬하는 방법이며, 안에 사용자 정의 함수를 통해 정렬방식을 정할 수 있다.( 안에 선언된 사용자 정의 함수는 temp 배열의 각 아이템들의 2번째 요소로 오름차순 2번째 요소가 같을경우 1번째 요소로 오름차순한다는 의미이다) [ 역순정렬을 하고 싶다면 앞에 -를 붙히면 된다.)
• result[i][:100]
  • result[i]의 배열을 100개까지만 저장하하겠다는 의미이다.

 

혹시라도 정정할 내용이나 추가적으로 필요하신 정보가 있다면 댓글 남겨주시면 감사하겠습니다.

오늘도 Jindory 블로그에 방문해주셔서 감사합니다.

 

[ 참조 ]

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