문제:

크기가 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을 출력한다.

풀이방법:

 연산에 따라 행과 열에 각각 행동을 취해야 하는 문제다. 일반적으로 열에다가 특정 연산을 취하는 것은 어렵기 때문에 열에 있는 내용들을 50번줄과 같이 행으로 전환해서 수행하도록 한다.

 각 행을 dict을 사용해서 갯수를 count하고 (횟수, 숫자)를 기준으로 정렬하도록 한다. 각 행을 임시 배열에 저장한 뒤에 가장 긴 행을 기준으로 나머지 부분에 0을 채워넣도록 한다. 만약 열에 대해서 수행했다면 50번줄의 코드를 다시 실행하여 열로 바꿔주도록 한다. 이를 k를 찾거나 100초가 넘을때까지 계속 반복해서 수행한다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
from collections import defaultdict
import copy
 
def make_new_A(A,max_idx):
    next_A = []
    for a in A:
        r = []
        for j in a:
            r.append(j[0])
            r.append(j[1])
        count = 0
        while 2*(max_idx-len(a))>count:
            r.append(0)
            count+=1
        next_A.append(r)
    return next_A
  
 
r,c,k = map(int,input().split())
 
= []
for _ in range(3):
    A.append(list(map(int,input().split())))
 
time = 0
while True:
    A_tmp = copy.deepcopy(A)
    if time>100:
        break
    try:
        if A_tmp[r-1][c-1]==k:
            break
    except:
        pass
    #R
    if len(A_tmp) >= len(A_tmp[0]):
        new_A = []
        max_row = 0
        for _, v in enumerate(A_tmp):
            tmp_dict = defaultdict(int)
            for i in v:
                if i:
                    tmp_dict[i]+=1
            row = sorted(tmp_dict.items(),key = lambda x : (x[1],x[0]))
            if len(row) > max_row:
                max_row = len(row)
            new_A.append(row)
        A = make_new_A(new_A,max_row)
    else:
        A_tmp = list(map(list,zip(*A_tmp)))
        new_A = []
        max_row = 0
        for _, v in enumerate(A_tmp):
            tmp_dict = defaultdict(int)
            for i in v:
                if i:
                    tmp_dict[i]+=1
            row = sorted(tmp_dict.items(),key = lambda x : (x[1],x[0]))
            if len(row) > max_row:
                max_row = len(row)
            new_A.append(row)
        A = make_new_A(new_A,max_row)
        A = list(map(list,zip(*A)))
    time+=1
if time>100:
    print(-1)
else:
    print(time)
cs

문제링크:

https://www.acmicpc.net/problem/17140

 

17140번: 이차원 배열과 연산

첫째 줄에 r, c, k가 주어진다. (1 ≤ r, c, k ≤ 100) 둘째 줄부터 3개의 줄에 배열 A에 들어있는 수가 주어진다. 배열 A에 들어있는 수는 100보다 작거나 같은 자연수이다.

www.acmicpc.net

 

'Algorithm > Python' 카테고리의 다른 글

[BOJ]1339. 단어 수학  (0) 2021.10.21
[BOJ] 15658. 연산자 끼워넣기 (2)  (0) 2021.10.20
[BOJ]2659. 십자카드 문제  (0) 2021.10.18
[BOJ] 2668. 숫자고르기  (0) 2021.10.15
[BOJ] 16918. 봄버맨  (0) 2021.10.14

+ Recent posts