백준: 17140 이차원 배열과 연산

문제

17140번: 이차원 배열과 연산

 

문제 풀이

 문제에서 배열 A가 주어지면, 배열의 행, 열의 수에 따라 정렬을 수행 후 행렬에 값을 추가한다. 조건은 다음과 같다.

• 행의 개수가 열의 개수보다 크거나 같은 경우
  • 배열 A의 모든 행에 대해 정렬을 수행한다
• 행의 개수가 열의 개수보다 작은 경우
  • 배열 A의 모든 열에 대해 정렬을 수행한다.
• 정렬을 위해서는 한 행 또는 한 열의 수와 등장 횟수를 기준으로 정렬한다.
  • (count, number)와 같은 기준으로 정렬한다.
  • 정렬할 때, 0은 무시한다.
• 변환된 행열을 A에 반환할 때, 가장 길이가 긴 행 또는 열을 기준으로 0으로 채운다.

이와 같은 과정을 100번(초)만큼 진행하고, `A[R][C] == K`가 되는 답을 찾지 못한다면 -1을 반환한다. 초기에 문제를 접근할 때, 예제 6을 생각하지 않아서 문제를 풀지 못했다. 행열의 크기가 100을 넘는 경우, 처음 100개를 제외한 나머지는 잘라내야 하는 제한 사항을 반영하지 않았는데도 맞았습니다가 떠서 당황했다.🤔

 

코드

from sys import stdin
from copy import deepcopy
from collections import Counter
from itertools import chain


def check_answer() -> bool:
    '''
    4 4 1
    1 2 1
    2 1 3
    3 3 3
    이와 같은 예시를 생각하지 않으면, 처음 부터 런타임 에러 발생!
    '''
    if R < num_rows() and C < num_columns():
        return A[R][C] == K
    return 0


def num_rows() -> int:
    return len(A)


def num_columns() -> int:
    return len(A[0])


def calc(cur_dir: str):
    global A
    temp = []
    max_len = 0
    # 방향이 열인 경우, 아래 로직을 다시 사용하기 위해 행열전환
    cur_matrix = A if cur_dir == "row" else list(map(list, zip(*A)))

    for nums in cur_matrix:
        # 각 요소를 카운트 한 후, 숫자가 0 이상인 경우만 (카운트, 숫자) 순으로 정렬
        cur_nums = list(chain(*sorted(Counter(filter(lambda x: x > 0, nums)).items(), key=lambda x: (x[1], x[0]))))
        max_len = max(len(cur_nums), max_len)
        temp.append(cur_nums)

    # 부족한 부분은 0으로 채우는 과정 필요
    for idx, nums in enumerate(temp):
        cur_len = len(nums)

        if cur_len < max_len:
            temp[idx] += [0] * (max_len - cur_len)

    # 행열을 전환한 경우, 다시 원상태로 전환
    if cur_dir == "column":
        temp = list(map(list, zip(*temp)))

    A = deepcopy(temp)


if __name__ == '__main__':
    R, C, K = map(int, stdin.readline().split())
    R -= 1
    C -= 1
    A = [list(map(int, stdin.readline().split())) for _ in range(3)]

    # 처음 부터 정답인 경우
    if check_answer():
        print(0)
        exit(0)

    # 조건에 따라, 시뮬레이션이 필요한 경우
    for cur_time in range(100):
        direction = "row" if num_rows() >= num_columns() else "column"
        calc(direction)

        if check_answer():
            print(cur_time + 1)
            exit(0)
    # 100초 후에도 찾지 못하는 경우
    else:
        print(-1)