[백준, 삼성 기출] 17140_이차원 배열과 연산 (Python)

17140_이차원 배열과 연산 (Python)

0. 출처

• 유형 : 시뮬레이션, 삼성 (gold 4)
• 링크 : 17140번: 이차원 배열과 연산

1. 기록

• 22/04/21 (목)

2. 풀이

(1) 아이디어, 시간복잡도, 자료구조

1. 아이디어
>>

2. 시간복잡도
>>

3. 자료구조
>>

(2) 예제 입력, 예제 출력

- 예제 입력 1 -
1 2 2
1 2 1
2 1 3
3 3 3

- 예제 출력 1 -
0

- 예제 입력 2 -
1 2 1
1 2 1
2 1 3
3 3 3

- 예제 출력 2 -
1

- 예제 입력 3 -
1 2 3
1 2 1
2 1 3
3 3 3

- 예제 출력 3 -
2

- 예제 입력 4 -
1 2 4
1 2 1
2 1 3
3 3 3

- 예제 출력 4 -
52

- 예제 입력 5 -
1 2 5
1 2 1
2 1 3
3 3 3

- 예제 출력 5 -
-1

- 예제 입력 6 -
3 3 3
1 1 1
1 1 1
1 1 1

- 예제 출력 6 -
2

(3) 코드

from collections import Counter
from functools import reduce


## R 연산
def R(array):
    mx = 0  # 가장 긴 리스트의 길이
    pprint(array)
    for i in range(len(array)):

        X = Counter(array[i])


        del X[0]  # 수를 정렬할 때, 0은 제외
        X = list(X.items())
        X.sort(key=lambda x: (x[1], x[0]))
        if len(X) > 50: X = X[:50]  # 크기가 100을 넘기면 안됨.
        array[i] = reduce(lambda x, y: list(x) + list(y), X[1:], list(X[0]))
        mx = max(mx, len(array[i]))

    ## 가장 긴 리스트에 맞춰, 0을 추가한다.
    for i in range(len(array)):
        if len(array[i]) < mx:
            array[i].extend([0] * (mx - len(array[i])))


def main():
    r, c, k = map(int, input().split())
    r, c = r - 1, c - 1

    graph = [list(map(int, input().split())) for _ in range(3)]
    time = 0  # 시간
    if r < len(graph) and c < len(graph[0]):
        if graph[r][c] == k:
            return time

    while True:
        if len(graph) >= len(graph[0]):  # 행의 개수 >= 열의 개수, R연산
            R(graph)  # R 연산

        else:  # 행의 개수 < 열의 개수, C연산
            graph = list(map(list, zip(*graph)))  # 트랜스포즈
            R(graph)  # R 연산
            graph = list(map(list, zip(*graph)))  # 트랜스포즈
        time += 1

        if time > 100:
            return -1

        if r < len(graph) and c < len(graph[0]):
            if graph[r][c] == k:
                return time


print(main())

(4) 정리

문제 설명에서 R연산, C연산에 대해서 '행에 대해서 or 열에대해서 정렬을 수행한다.' 라고 되어있어서
정렬을 수행한다는게 무슨말인지 몰랐다.
정렬을 수행한다. -> 문제 설명에 있는 로직을 행에 대해서 or 열에 대해서 수행한다는 말이다.
로직은 특정 숫자를 카운트하고 그에 대한 결과를 정렬하는건데 단순히 정렬이라고만해서 문제 이해하는데 한참 걸렸다.

문제를 푸는데 있어서 파이썬의 각 함수들의 사용법 이해도가 중요하다고 느꼈습니다.

위의 풀이에서 사용된 함수는 zip, Conter, items, reduce, extend 등이 있습니다.

특히 트랜스포즈하는 코드는 미리 알고있지 않으면 생각해내서 구현하기 힘든 코드라고 생각해서 암기해야할 것 같습니다.

graph = list(map(list, zip(*graph)))  # 트랜스포즈

reduce 와 extend 도 위 문제 풀이를 찾으면서 처음 본 함수였습니다.
reduce 함수는 '감소시킨다'는 의미의 쓰임은 전혀없고 '누적'의 의미로 쓰이는 함수입니다.★

(5) 참고

파이썬 asterisk(*) 사용 용도
파이썬의 zip() 내장 함수로 데이터 엮기
coolections모듈의 Counter함수
Key, Value 쌍 얻기(items)
파이썬 reduce 함수 사용법
파이썬 extend 함수