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

문제

---

17140번: 이차원 배열과 연산

 

크기가 3×3인 배열 A가 있으며, 배열의 인덱스는 1부터 시작한다.

 

1초가 지날 때마다 배열에 다음 두 개의 연산 중 하나가 적용된다.

1. R 연산 : 행의 개수 ≥ 열의 개수인 경우, 배열 A의 모든 행에 대하여 정렬을 수행

2. C 연산 : 행의 개수 < 열의 개수인 경우, 배열 A의 모든 열에 대하여 정렬을 수행

 

수의 등장 횟수가 커지는 순으로, 등장 횟수가 동일하다면 수가 커지는 순으로 정렬하며

정렬된 결과를 배열에 넣을 때는 수와 등장 횟수를 모두 넣는다.

ex. [3, 1, 1] → [3, 1, 1, 2] → [2, 1, 3, 1, 1, 2]

 

정렬된 결과를 배열에 다시 넣으면 행 또는 열의 크기가 달라질 수 있다.

행 또는 열의 크기가 커진 곳에는 0을 채워 넣으나,

수를 정렬할 때 0은 무시한다.

 

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

 

A[r][c]에 들어있는 값이 k가 되기 위한 연산의 최소 시간을 구하는 것이 문제이며,

100초가 지나도 A[r][c] = k가 되지 않으면 -1을 출력한다.

 

 

풀이

---

조건이 상당이 많은 문제다.

행에 대한 접근과 열에 대한 접근이 다르기 때문에 공통적인 부분 생각

 

우선, 프로그램의 큰 틀은 다음과 같다.

1. A[r][c] == k인지 확인

2. 시간이 100초가 되었다면 -1 반환

3. 행의 개수 ≥ 열의 개수인 경우 R 연산 / 아닐 경우 C 연산

r, c, k = map(int, sys.stdin.readline().split())
N, M = 3, 3  # N : 행 개수 / M : 열 개수

A = []
for _ in range(N):
    A.append(list(map(int, sys.stdin.readline().split())))

r -= 1
c -= 1
time = 0

while True:
    if len(A) > r and len(A[0]) > c:  # 범위 확인 (런타임 에러 - Index error 발생)
        if A[r][c] == k:
            break

    if time == 100:
        time = -1
        break

    if N >= M:  # R 연산
        R()
    else:  # C 연산
        C()

    time += 1

print(time)

 

그다음, R 연산과 C 연산에 대하여 생각해보자.

두 연산은 배열에 접근하는 방법만 다르고 수행해야 하는 큰 흐름은 동일하다.

주요 구현 포인트들과 각각에 대한 구현 방법은 다음과 같다.

 

1. 수 등장 횟수 세기 - dictionary 사용

for y in range(N):
    dic = {}  # key : 수 / value: 수 등장 횟수

    for x in range(M):
        if A[y][x] in dic:
            dic[A[y][x]] += 1
        else:
            dic[A[y][x]] = 1

 

2. 수 등장 횟수가 커지는 순으로 정렬 - sorted() 함수 사용

sorted_dic = sorted(dic.items(), key=lambda item: item[1])

 

3. 2번 정렬 내에서 수가 커지는 순으로 정렬 - 우선순위 큐(heapq) 사용

# 수 커지는 순으로 정렬 / 0 제외
def get_sorted_line(dic):
    line = []
    q = []  # 우선 순위 큐
    count = 0  # key 개수 (0 제외)

    for key, value in dic:
        if key != 0:
            count += 1

            # 다른 value일 경우 전부 pop
            if len(q) != 0 and q[0][0] != value:
                while q:
                    t = heapq.heappop(q)
                    line.append(t[1])  # value
                    line.append(t[0])  # key
                heapq.heappush(q, (value, key))

            # 같은 value일 경우 push
            else:
                heapq.heappush(q, (value, key))
                heapq.heapify(q)

    while q:
        t = heapq.heappop(q)
        line.append(t[1])  # value
        line.append(t[0])  # key

    return count, line

 

코드

---

import sys
import heapq

r, c, k = map(int, sys.stdin.readline().split())
N, M = 3, 3  # N : 행 개수 / M : 열 개수

A = []
for _ in range(N):
    A.append(list(map(int, sys.stdin.readline().split())))


# 수 커지는 순으로 정렬 / 0 제외
def get_sorted_line(dic):
    line = []
    q = []  # 우선 순위 큐
    count = 0  # key 개수 (0 제외)

    for key, value in dic:
        if key != 0:
            count += 1

            # 다른 value일 경우 전부 pop
            if len(q) != 0 and q[0][0] != value:
                while q:
                    t = heapq.heappop(q)
                    line.append(t[1])  # value
                    line.append(t[0])  # key
                heapq.heappush(q, (value, key))

            # 같은 value일 경우 push
            else:
                heapq.heappush(q, (value, key))
                heapq.heapify(q)

    while q:
        t = heapq.heappop(q)
        line.append(t[1])  # value
        line.append(t[0])  # key

    return count, line


# 행에 대한 정렬
def R():
    global M
    m = 0

    for y in range(N):
        dic = {}  # key : 수 / value: 수 등장 횟수

        for x in range(M):
            if A[y][x] in dic:
                dic[A[y][x]] += 1
            else:
                dic[A[y][x]] = 1

        # 수 등장 횟수가 커지는 순으로 정렬
        sorted_dic = sorted(dic.items(), key=lambda item: item[1])

        # 수 커지는 순으로 정렬 / 0 제외
        count, line = get_sorted_line(sorted_dic)

        A[y] = line  # 행 변경
        m = max(m, 2 * count)

    # 열의 크기가 100을 넘어가는 경우
    if m > 100:
        m = 100

    if M < m:
        M = m

    # 0 채우기
    for y in range(N):
        for i in range(M - len(A[y])):
            A[y].append(0)


# 열에 대한 정렬
def C():
    global N
    n = 0
    col = []

    for x in range(M):
        dic = {}

        for y in range(N):
            if A[y][x] in dic:
                dic[A[y][x]] += 1
            else:
                dic[A[y][x]] = 1

        # 수 등장 횟수가 커지는 순으로 정렬
        sorted_dic = sorted(dic.items(), key=lambda item: item[1])

        # 수 커지는 순으로 정렬 / 0 제외
        count, line = get_sorted_line(sorted_dic)
        col.append(line)
        n = max(n, 2 * count)

    # 행의 크기가 100을 넘어가는 경우
    if n > 100:
        n = 100

    if N < n:
        for _ in range(n - N):
            A.append([0 for _ in range(M)])
        N = n

    for x in range(M):
        for y in range(N):
            if y < len(col[x]):
                A[y][x] = col[x][y]  # 값 변경
            else:  # 0 채우기
                A[y][x] = 0


r -= 1
c -= 1
time = 0

while True:
    if len(A) > r and len(A[0]) > c:  # 범위 확인 (런타임 에러 - Index error 발생)
        if A[r][c] == k:
            break

    if time == 100:
        time = -1
        break

    if N >= M:  # R 연산
        R()
    else:  # C 연산
        C()

    time += 1

print(time)

런타임 에러(Index Error)가 계속 떴었는데,

A[r][c] == k인지 확인하기 전에 현재 A 배열의 행과 열의 개수가 r, c보다 작지 않은지 즉, 인덱스가 유효한 값인지 아닌지를 체크해주지 않아서 발생한 것이었다.

 

예외처리를 정교하게 하는 습관이 필요할 것 같다..