백준 이차원 배열과 연산 [17140] 파이썬(Python) 코드 + 해설

백준 17140 이차원 배열과 연산 문제

 

문제 설명

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

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

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

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

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

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

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

입력 및 출력

• 입력:
  • 첫째 줄: r,c,k(1≤r,c,k≤100)
  • 다음 3개의 줄: 배열 A의 초기 상태 (A는 3×3 배열)
• 출력:
  • A[r][c]=k가 되기 위한 최소 시간을 출력한다. 100초가 지나도 A[r][c]=k가 되지 않으면 -1을 출력한다.

문제 접근

이 문제는 매 초마다 배열에 연산을 적용하며, A[r][c]의 값이 k가 될 때까지 시뮬레이션을 진행해야 한다.

• R 연산과 C 연산을 구현해야 한다.
• 배열의 크기가 변하기 때문에, 배열을 동적으로 관리해야 한다.
• 매 초마다 A[r][c]를 확인하여 k와 같은지 검사한다.
• 시간 제한이 0.5초로 매우 짧기 때문에, 효율적인 구현이 필요하다.

구현 방법

1. 배열 초기화 및 입력 받기

배열 A를 리스트로 초기화하고, 입력을 받는다.

import sys
input = sys.stdin.readline

r, c, k = map(int, input().split())
A = [list(map(int, input().split())) for _ in range(3)]

2. R 연산 구현

• 각 행에 대해서 숫자와 등장 횟수를 센다.
• 숫자와 등장 횟수를 튜플로 묶어서 리스트에 저장한다.
• 등장 횟수가 증가하는 순으로, 숫자가 증가하는 순으로 정렬한다.
• 정렬된 결과를 한 행으로 만들어 반환한다.

def R_operation(array):
    max_len = 0
    new_array = []
    for row in array:
        count = {}
        for num in row:
            if num == 0:
                continue
            if num in count:
                count[num] += 1
            else:
                count[num] = 1
        count_list = []
        for num, cnt in count.items():
            count_list.append((num, cnt))
        count_list.sort(key=lambda x: (x[1], x[0]))
        new_row = []
        for num, cnt in count_list:
            new_row.extend([num, cnt])
        max_len = max(max_len, len(new_row))
        new_array.append(new_row)
    # 가장 긴 행의 길이에 맞춰 0을 추가한다.
    for row in new_array:
        while len(row) < max_len:
            row.append(0)
        # 행의 길이가 100을 넘으면 100까지만 자른다.
        if len(row) > 100:
            del row[100:]
    return new_array

3. C 연산 구현

• 배열을 전치하여 열을 행으로 바꾼다.
• R 연산과 동일한 과정을 수행한다.
• 다시 전치하여 원래 배열로 복원한다.

def C_operation(array):
    transposed_array = list(map(list, zip(*array)))
    transposed_array = R_operation(transposed_array)
    # 다시 전치하여 원래 배열로 복원
    new_array = list(map(list, zip(*transposed_array)))
    return new_array

4. 시뮬레이션 진행

• 최대 100초까지 반복하며, 매 초마다 다음을 수행한다:
  • 현재 배열의 크기를 확인하여 R 연산 또는 C 연산을 선택한다.
  • 연산을 수행한 후, 배열 A를 업데이트한다.
  • A[r−1][c−1]이 k와 같은지 확인한다.

time = 0
while time <= 100:
    try:
        if A[r-1][c-1] == k:
            break
    except IndexError:
        pass  # 배열의 크기가 작아서 인덱스 에러가 발생할 수 있다.
    time += 1
    row_len = len(A)
    col_len = len(A[0])
    if row_len >= col_len:
        A = R_operation(A)
    else:
        A = C_operation(A)
    # 배열의 크기가 100을 넘으면 100까지만 자른다.
    if len(A) > 100:
        A = A[:100]
    for i in range(len(A)):
        if len(A[i]) > 100:
            A[i] = A[i][:100]

5. 결과 출력

• A[r−1][c−1]==k이면 현재 시간을 출력한다.
• 100초를 넘어도 A[r−1][c−1]이 k가 되지 않으면 -1을 출력한다.

if time > 100:
    print(-1)
else:
    print(time)

백준 17140 이차원 배열과 연산 파이썬(Python) 정답 코드

import sys
input = sys.stdin.readline

r, c, k = map(int, input().split())
A = [list(map(int, input().split())) for _ in range(3)]

def R_operation(array):
    max_len = 0
    new_array = []
    for row in array:
        count = {}
        for num in row:
            if num == 0:
                continue
            if num in count:
                count[num] += 1
            else:
                count[num] = 1
        count_list = []
        for num, cnt in count.items():
            count_list.append((num, cnt))
        count_list.sort(key=lambda x: (x[1], x[0]))
        new_row = []
        for num, cnt in count_list:
            new_row.extend([num, cnt])
        max_len = max(max_len, len(new_row))
        new_array.append(new_row)
    # 가장 긴 행의 길이에 맞춰 0을 추가한다.
    for row in new_array:
        while len(row) < max_len:
            row.append(0)
        # 행의 길이가 100을 넘으면 100까지만 자른다.
        if len(row) > 100:
            del row[100:]
    return new_array

def C_operation(array):
    transposed_array = list(map(list, zip(*array)))
    transposed_array = R_operation(transposed_array)
    # 다시 전치하여 원래 배열로 복원
    new_array = list(map(list, zip(*transposed_array)))
    return new_array

time = 0
while time <= 100:
    try:
        if A[r-1][c-1] == k:
            break
    except IndexError:
        pass  # 배열의 크기가 작아서 인덱스 에러가 발생할 수 있다.
    time += 1
    row_len = len(A)
    col_len = len(A[0])
    if row_len >= col_len:
        A = R_operation(A)
    else:
        A = C_operation(A)
    # 배열의 크기가 100을 넘으면 100까지만 자른다.
    if len(A) > 100:
        A = A[:100]
    for i in range(len(A)):
        if len(A[i]) > 100:
            A[i] = A[i][:100]

if time > 100:
    print(-1)
else:
    print(time)

17140 문제 해결 핵심 포인트

• R 연산과 C 연산의 구현: 두 연산은 매우 유사하므로, R 연산을 구현한 후 C 연산에서는 배열을 전치하여 R 연산을 적용하고 다시 전치한다.
• 숫자의 등장 횟수 세기: 딕셔너리 또는 리스트를 사용하여 각 숫자의 등장 횟수를 센다.
• 정렬 기준: 등장 횟수가 증가하는 순으로, 숫자가 증가하는 순으로 정렬한다.
• 배열 크기 조정: 연산 후 배열의 크기가 변하므로, 가장 긴 행 또는 열의 길이에 맞춰 배열을 조정한다.
• 시간 초과 방지: 최대 100초까지만 시뮬레이션을 진행하고, 효율적인 코드를 작성하여 시간 초과를 방지한다.

제출 결과

백준 17140 이차원 배열과 연산 문제 제출 결과

 

도움이 되셨다면 공감과 댓글 부탁드립니다.