[Python] BOJ 17140 - 이차원 배열과 연산

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

17140번: 이차원 배열과 연산

# 스터디에서 구현문제 위주로 매일 문제를 올려주신다길래 풀어보고 있다!

# 구현,시뮬레이션 문제는 아이디어가 어렵고 복잡하지 않지만, 말그대로 구현이 복잡하고 어렵다

   (약간 무지성으로 풀기 딱 좋은?? 문제들인듯)

   (물론 어렵게 bfs랑 같이 섞어 나온다면 아이디어 떠올리는 것도 힘들다 ex: 삼성기출문제)

# 이 문제는 문제에서 요구하는대로 그냥 그대로 구현해주면 풀린다.

 

 

1. 우선 처음에 입력된 r, c가 0초일때 배열 범위(3 x 3)를 넘을 수 있기 때문에

    7번째 줄에서 r, c가 배열 범위를 벗어나는지 check를 해준다.

 

2. 처음부터 m[r-1][c-1]이 k가 아니라면 while문을 실행한다.

    row에는 행의 개수를, col에는 열의 개수를 저장해주고 row >= col이면 R연산을 수행하고

    row < col이면 C연산을 수행한다.

 

3. R연산

   3-1. m(현재 배열)의 각 행을 돌면서 행마다 나온 숫자와 개수를 count 딕셔너리에 저장해준다.

           26번째 줄에서 count에는 숫자와 그 숫자가 나온 개수 순서로 저장되어 있기 때문에 문제에서

           요구하는대로 개수가 작은 순서대로 정렬해주고, 그 다음 숫자가 커지는 순서로 정렬해준다.

           그리고 각 행의 길이 중 최댓값을 max_length에 저장해준다.

 

   3-2. 3-1에서 정렬된 arr를 sort_arr라 하고 tmp배열에 sort_arr의 원소들을 하나하나 차례대로

           append해준다. 여기서 각 행의 길이가 100이 넘으면 100까지 자르라고 했으므로

           tmp[ :100]을 new_arr에 extend해준다.

 

   3-3. 최종적으로 new_arr에는 연산을 마친 뒤의 배열이 저장되어 있다. 여기서 가장 길이가

           긴 행을 기준으로 길이를 맞춰줘야 한다. 따라서 new_arr를 돌면서 현재 행의 길이가 

           max_length*2보다 작으면 작은만큼 0을 뒤에 extend해준다.

 

   3-4. 모든 작업을 마친뒤 m에 new_arr를 copy해서 다시 넣어준다.

 

4. C연산

    Idea. C연산은 R연산이랑 원리는 같은데, 행이 아니라 열을 돌면서 작업을 해줘야 한다.

           처음에 여러가지 방법을 생각해보았다. 열마다 확인 하는 것은 상관이 없는데, 작업을 마치고

           다시 열을 기준으로 수를 넣어줘야 해서 복잡해질 것 같았다.

           그래서 일단 R연산처럼 new_arr를 만든 뒤 배열을 돌리는 방법을 생각했는데, new_arr를

           C연산 결과처럼 만드려면 배열을 단순히 돌리는 것이 아니라 좌우로 뒤집은 다음

           반시계방향으로 90도 돌려줘야해서 시간이 오래걸릴 것 같았다.

           따라서, tmp2배열을 하나 더 만든 뒤 new_arr배열을 돌며 나오는 값들을 하나하나 

           tmp2 배열에 해당하는 좌표값에 넣어주는 방식으로 했다.

 

    4-1. R연산과 마찬가지로 new_arr까지 만들어준다. 대신 count 딕셔너리를 채울 때 m[j][i]를 통해

          열끼리 count딕셔너리를 만들어주었다.

 

    4-2. new_arr가 3x6배열이라면 우리가 원하는 C연산을 마친 뒤의 배열은 6x3배열일 것이다.

          따라서 new_arr의 행과 열을 뒤집은 크기로 tmp2배열을 만들어준다.

          그리고 new_arr의 (0, 1), (0, 2)은 tmp2의 (1, 0), (2, 0)에 넣어줘야 한다.

          따라서 new_arr[i][j] => tmp2[j][i]에 넣어준다.

 

    4-3. m에 tmp2를 copy해서 다시 넣어준다.

 

5. R연산 또는 C연산을 마친 뒤, m[r-1][c-1]이 k인지 확인한다.

   여기서도 r과 c가 배열범위를 벗어나는지 확인해줘야 한다. 

   m[r-1][c-1]이 k이면 time을 출력하고 break해주고, 아니라면 time을 1증가시킨다.

   100초가 지나도 m[r-1][c-1]이 k가 되지않으면 -1을 출력해주고 break해준다.

 

import sys, copy
from collections import defaultdict
input = sys.stdin.readline
r, c, k = map(int,input().split())
m = [list(map(int,input().split())) for _ in range(3)]
time = 1
if (r-1 < len(m) and c-1 < len(m[0])) and m[r-1][c-1] == k:
    print(0)
else:
    while True:
        # row = 행, col = 열
        row, col = len(m), len(m[0])
        new_arr = [] 
        if row >= col:
            # R 연산
            max_length = 0
            for i in m:
                tmp = []
                count = defaultdict(int)
                
                for j in i:
                    if j == 0:
                        continue
                    count[j] += 1

                sort_arr = sorted(count.items(), key=lambda x: (x[1], x[0]))
                if len(count.items()) > max_length:
                    max_length = len(count.items())

                for j in sort_arr:
                    tmp.extend((j[0], j[1]))
                new_arr.append(tmp[:100])

            for i in new_arr:
                if len(i) < max_length * 2:
                    zero = [0] *(max_length * 2 - len(i))
                    i.extend(zero)
            
            m = copy.deepcopy(new_arr)
        
        else:
            # C 연산
            max_length = 0
            for i in range(len(m[0])):
                tmp = []
                count = defaultdict(int)
                
                for j in range(len(m)):
                    if m[j][i] == 0:
                        continue
                    count[m[j][i]] += 1

                sort_arr = sorted(count.items(), key=lambda x: (x[1], x[0]))
                if len(count.items()) > max_length:
                    max_length = len(count.items())

                for j in sort_arr:
                    tmp.extend((j[0], j[1]))
                new_arr.append(tmp[:100])

            for i in new_arr:
                if len(i) < max_length * 2:
                    zero = [0] *(max_length * 2 - len(i))
                    i.extend(zero)

            tmp2 = [[0] * len(new_arr) for _ in range(len(new_arr[0]))]
            for i in range(len(new_arr)):
                for j in range(len(new_arr[0])):
                    tmp2[j][i] = new_arr[i][j]
            
            m = copy.deepcopy(tmp2)

        if (r-1 < len(m) and c-1 < len(m[0])) and m[r-1][c-1] == k:
            print(time)
            break

        time += 1
        if time > 100:
            print(-1)
            break

(solved.ac 티어: 골드 4)

 

 

# C연산을 할때 zip을 사용하면 이차원배열을 뒤집어서 R연산처럼 그냥 똑같이 할 수 있는 것 같다.

   그러면 나처럼 케이스를 나누지 않고 코드길이를 절반으로 줄일 수 있다.

# sort_arr를 나처럼 직접 만들어도 좋지만 웬만하면 Counter함수를 사용하자..