[BOJ] 삼성 SW기출 17140 이차원 배열과 연산 Python

문제

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

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

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

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

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

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

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

입력

첫째 줄에 r, c, k가 주어진다. (1 ≤ r, c, k ≤ 100)

둘째 줄부터 3개의 줄에 배열 A에 들어있는 수가 주어진다. 배열 A에 들어있는 수는 100보다 작거나 같은 자연수이다.

출력

A[r][c]에 들어있는 값이 k가 되기 위한 연산의 최소 시간을 출력한다. 100초가 지나도 A[r][c] = k가 되지 않으면 -1을 출력한다.

 

풀이

# 17140 이차원 배열과 연산

import sys
input = sys.stdin.readline

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

# 행 연산 수행하는 함수
def sorting(graph):
    for i in range(len(graph)):
        tmp = []
        dic = {}
        for j in graph[i]:
        	# 0인 경우는 제외
            if j == 0:
                continue
            # key : 등장하는 숫자 value : 해당 숫자가 등장하는 횟수
            if (dic.get(j) == None):
                dic[j] = graph[i].count(j)
        # value값(횟수) 기준으로 오름차순 정렬, value값이 같다면 key값(등장 숫자)으로 정렬
        dic = dict(sorted(dic.items(), key= lambda item: (item[1], item[0])))
        # key, value, key, value .. 저장 (숫자, 횟수, 숫자, 횟수, ..)
        for k, v in dic.items():
            tmp.append(k)
            tmp.append(v)
        graph[i] = tmp
    # 가장 길이가 큰 행의 길이 max_len에 저장
    max_len = -1e9
    for i in range(len(graph)):
        max_len = max(max_len, len(graph[i]))
    # 부족한 길이만큼 0으로 채워주기
    for j in range(len(graph)):
        while len(graph[j]) < max_len:
            graph[j].append(0)
    return graph


count = 0
while True:
    if (r-1) < len(graph) and (c-1) < len(graph[0]) and graph[r-1][c-1] == k:
        print(count)
        break
    # R연산_모든 행에 대해서 정렬 수행
    if len(graph)>=len(graph[0]):
        # 딕셔너리 {key : 값, value : 횟수}, 인덱스 1로 정렬, 인덱스 0으로 정렬
        # 인덱스 1만큼 반복해서 인덱스0값 넣기
        # 길이 max값 찾고, 빈 공간은 0으로 채워서 그래프 완성
        graph = sorting(graph)
        count += 1
    else:
        # 2차원 리스트의 행, 열 변환
        graph = list(map(list, zip(*graph)))
        graph = sorting(graph)
        # 2차원 리스트의 행, 열 변환 (원상복귀)
        graph = list(map(list, zip(*graph)))
        count += 1
    if count > 100:
        print(-1)
        break

 

헤매었던 부분

1. r, c의 인덱스가 1부터 시작인 것을 0부터 시작으로 이해하고 풀었음. 문제를 잘 읽자

2. 딕셔너리 정렬을 할 때 value값으로 정렬, 값이 같다면 key값으로 정렬 -> 이 부분을 1. value값으로 정렬 2. key값으로 정렬 이렇게 나눠서 두 번 정렬 해줘서 생각했던 것과 다르게 정렬이 되었다....

# value값(횟수) 기준으로 오름차순 정렬, value값이 같다면 key값(등장 숫자)으로 정렬
dic = dict(sorted(dic.items(), key= lambda item: (item[1], item[0])))

잊지 말자

3. 행연산, 열연산을 결정할 때 행과 열의 길이로 판단을 해야 하는데 처음에 r, c로 착각하고 코드를 짰다...

4. 최대길이의 행을 구하는 부분에서 코드 오류 ㅠㅠ

max_len = -1e9
    for i in range(len(graph)):
        max_len = max(max_len, len(graph[i]))

평소 잘 짜던 부분이었는데 너무 오랜만에 문제를 풀어서 헷갈렸나보다.

 

결론 : 실수투성이라 시간이 너무 오래 걸린 문제. 문제를 꼼꼼히 읽고 코드를 꼼꼼히 확인하자..

 

배운 것

1. 딕셔너리 이중 정렬

# value값(횟수) 기준으로 오름차순 정렬, value값이 같다면 key값(등장 숫자)으로 정렬
        dic = dict(sorted(dic.items(), key= lambda item: (item[1], item[0])))

2. 2차원 리스트의 행, 열 변환

# 2차원 리스트의 행, 열 변환
        graph = list(map(list, zip(*graph)))

 

 

여러모로 복습할 코드가 많은 문제이니 여러 번 보기 !!