Notice
Recent Posts
Recent Comments
Link
«   2024/05   »
일 월 화 수 목 금 토
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
Tags more
Archives
Today
Total
관리 메뉴

최's 먹공로그

BOJ17140_이차원배열과 연산 본문

APS

BOJ17140_이차원배열과 연산

ChoiSH313 2019. 9. 1. 15:12

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


문제정리

1. 크기가 3 * 3인 배열 A가 있다. 1초가 지날때마다 배열에 연산이 적용된다.

2. 연산

(1) R연산 : 배열 A의 모든 행에 대해서 정렬을 수행한다. 행의 개수 >= 열의 개수인 경우에

적용된다.

(2) C연산 : 배열 A의 모든 열에 대해서 정렬을 수행한다. 행의 개수 < 열의 개수인 경우에

적용된다.

3. 정렬은 수의 등장 횟수가 커지는 순으로 , 그러한 것이 여러가지면 수가 커지는 순으로 정렬한다.

배열 A에 정렬된 결과를 다시 넣어야 한다. 수 , 등장 횟수 순서로 넣는다.

4. R연산이 적용된 경우에는 행의 크기가 가장 큰행을 기준으로 모든 행의 크기가 커지고,

C연산이 적용된 경우에는 열의 크기가 가장 큰 열을 기준으로 모든 열의 크기가 커진다.

5. 행 또는 열의 크기가 커진 곳에는 0이 채워진다. 수를 정렬할 때 0은 무시해야 한다.

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

1~50까지 모든수가 있다면 50 이 몇개 까지 가능하다는 소리??

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

구해보자. 시간이 100을 넘어가는 경우에는 -1을 출력한다. 100초과??


문제issue

1. list에 있는 값을 map에 갱신한 후 map에 남은 값들을 생각해줘야 한다.

2. 연산을 실행하고 나서 행 또는 열의 크기를 갱신해주는 시점을 잘 생각해야 한다.

3. list에 있는 값을 map에 갱신할 때


해결흐름

1. map[101][101]로 만든다. 1~100까지 사용한다.

2. pair list를 정렬을 위해 사용한다.

3. 숫자의 개수를 파악하기 위해 count[101]을 사용한다.

4. R연산을 할 경우

(1) for 행 for 열로 탐색하면서 map의 숫자가 0이 아니면 count++한다.

(2) count를 돌면서 0이 아니면 그때의 인덱스와 값을 list에 넣는다. 이때, list의 최댓값을

도출한다.

(3) list를 cnt로 먼저 정렬하고 cnt가 같은게 있으면 number로 정렬한다. map을 갱신해준다.

(2) list의 최댓값과 이전의 행크기와 비교해서 다음에는 어떤 연산을 할지 정한다.

5. C연산을 할 경우는 R연산과 비슷하다.


소스코드

1. list 사용

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
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;
import java.util.StringTokenizer;
 
public class Main {
 
    static class pair {
        int number;
        int cnt;
 
        public pair(int number, int cnt) {
            super();
            this.number = number;
            this.cnt = cnt;
        }
    }
 
    public static void main(String[] args) throws Exception {
        // input
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine().trim());
        int r = Integer.parseInt(st.nextToken());
        int c = Integer.parseInt(st.nextToken());
        int k = Integer.parseInt(st.nextToken());
        int[][] map = new int[101][101];
        for (int i = 1; i < 4; i++) {
            st = new StringTokenizer(br.readLine().trim());
            for (int j = 1; j < 4; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        int time = 0;
        int row_size = 3;
        int col_size = 3;
        List<pair> list = new ArrayList<pair>();
        int[] count = new int[101];
        while (true) {
            if (map[r][c] == k) {
                break;
            }
            time++;
            if(time > 100) {
                time = -1;
                break;
            }
            // R연산
//            System.out.println("row_size : " + row_size + " col_size : " + col_size);
            if (row_size >= col_size) {
                int maxCol_value = Integer.MIN_VALUE;
                for (int i = 1; i < 101; i++) {
                    for (int j = 1; j < 101; j++) {
                        if (map[i][j] != 0) {
                            count[map[i][j]]++;
                        }
                    }
                    list = new ArrayList<pair>();
                    // 한 행에 대한 검사가 끝나면~
                    for (int j = 1; j < 101; j++) {
                        if (count[j] != 0) {
                            list.add(new pair(j, count[j]));
                        }
                    }
                    count = new int[101];
                    int col_value = list.size() * 2;
//                    System.out.println("col_value : " + col_value);
                    if (maxCol_value < col_value) {
                        maxCol_value = col_value;
                    }
//                    System.out.println("maxCol_value : " + maxCol_value);
                    Collections.sort(list, new Comparator<pair>() {
                        @Override
                        public int compare(pair o1, pair o2) {
                            if (o1.cnt == o2.cnt)
                                return o1.number - o2.number;
                            return o1.cnt - o2.cnt;
                        }
                    });
//                    System.out.println("===========R연산 list=============");
//                    for (int j = 0; j < list.size(); j++) {
//                        System.out.println("number : " + list.get(j).number + " cnt : " + list.get(j).cnt);
//                    }
                    int idx = 1;
                    for (int j = 0; j < list.size(); j++) {
                        map[i][idx++] = list.get(j).number;
                        map[i][idx++] = list.get(j).cnt;
                    }
                    for (int j = idx; j < 101; j++) {
                        map[i][j] = 0;
                    }
//                    System.out.println("=========R연산 map===========");
//                    for (int j = 1; j < 5; j++) {
//                        for (int j2 = 1; j2 < 5; j2++) {
//                            System.out.print(map[j][j2] + " ");
//                        }
//                        System.out.println();
//                    }
                }
                col_size = maxCol_value;
            }
            // C연산
            else if (row_size < col_size) {
                int maxRow_value = Integer.MIN_VALUE;
                for (int i = 1; i < 101; i++) {
                    for (int j = 1; j < 101; j++) {
                        if (map[j][i] != 0) {
                            count[map[j][i]]++;
                        }
                    }
                    // 한 열에 대한 검사가 끝나면~
                    list = new ArrayList<pair>();
                    for (int j = 1; j < 101; j++) {
                        if (count[j] != 0) {
                            list.add(new pair(j, count[j]));
                        }
                    }
                    count = new int[101];
                    int row_value = list.size() * 2;
                    if (maxRow_value < row_value) {
                        maxRow_value = row_value;
                    }
                    Collections.sort(list, new Comparator<pair>() {
                        @Override
                        public int compare(pair o1, pair o2) {
                            if (o1.cnt == o2.cnt)
                                return o1.number - o2.number;
                            return o1.cnt - o2.cnt;
                        }
                    });
//                    System.out.println("===========C연산 list=============");
//                    for (int j = 0; j < list.size(); j++) {
//                        System.out.println("number : " + list.get(j).number + " cnt : " + list.get(j).cnt);
//                    }
                    int idx = 1;
                    for (int j = 0; j < list.size(); j++) {
                        map[idx++][i] = list.get(j).number;
                        map[idx++][i] = list.get(j).cnt;
                    }
                    for (int j = idx; j < 101; j++) {
                        map[j][i] = 0;
                    }
//                    System.out.println("=========C연산 map===========");
//                    for (int j = 1; j < 5; j++) {
//                        for (int j2 = 1; j2 < 5; j2++) {
//                            System.out.print(map[j][j2] + " ");
//                        }
//                        System.out.println();
//                    }
                }
                row_size = maxRow_value;
            }
        }
        System.out.println(time);
    } // end of main
} // end of class
cs


2. count 배열만 사용

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
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Comparator;
import java.util.StringTokenizer;
 
public class Main {
 
    static class pair {
        int number;
        int cnt;
 
        public pair(int number, int cnt) {
            super();
            this.number = number;
            this.cnt = cnt;
        }
    }
 
    public static void main(String[] args) throws Exception {
        // input
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine().trim());
        int r = Integer.parseInt(st.nextToken());
        int c = Integer.parseInt(st.nextToken());
        int k = Integer.parseInt(st.nextToken());
        int[][] map = new int[101][101];
        for (int i = 1; i < 4; i++) {
            st = new StringTokenizer(br.readLine().trim());
            for (int j = 1; j < 4; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        int time = 0;
        int row_size = 3;
        int col_size = 3;
        pair[] count = new pair[101];
        while (true) {
            // 종료조건 두가지
            if (map[r][c] == k) {
                break;
            }
            time++;
            if(time > 100) {
                time = -1;
                break;
            }
            // R연산
//            System.out.println("row_size : " + row_size + " col_size : " + col_size);
            if (row_size >= col_size) {
                int maxCol_value = Integer.MIN_VALUE;
                for (int i = 1; i < 101; i++) {
                    for (int k1 = 0; k1 < count.length; k1++) {
                        count[k1] = new pair(0,0);
                    }
                    int new_size = 0;
                    for (int j = 1; j < 101; j++) {
                        if (map[i][j] != 0) {
                            count[map[i][j]].cnt++;
                            count[map[i][j]].number = map[i][j];
//                            new_size++;
                        }
                    }
                    // 한 행에 대한 검사가 끝나면~
//                    System.out.println("maxCol_value : " + maxCol_value);
                    Arrays.sort(count, new Comparator<pair>() {
                        @Override
                        public int compare(pair o1, pair o2) {
                            if (o1.cnt == o2.cnt)
                                return o1.number - o2.number;
                            return o1.cnt - o2.cnt;
                        }
                    });
//                    System.out.println("===========R연산 count=============");
//                    for (int j = 0; j < 101; j++) {
//                        if(count[j].cnt != 0)
//                            System.out.println("number : " + count[j].number + " cnt : " + count[j].cnt);
//                    }
                    int idx = 1;
                    for (int j = 1; j < 101; j++) {
                        if(count[j].cnt != 0) {
                            map[i][idx++] = count[j].number;
                            map[i][idx++] = count[j].cnt;
                            new_size += 2;
                        }
                    }
                    int col_value = new_size;
//                    System.out.println("col_value : " + col_value);
                    if (maxCol_value < col_value) {
                        maxCol_value = col_value;
                    }
                    // 그전에 map에 남아있던 뒤에 값들은 0으로
                    for (int j = idx; j < 101; j++) {
                        map[i][j] = 0;
                    }
//                    System.out.println("=========R연산 map===========");
//                    for (int j = 1; j < 5; j++) {
//                        for (int j2 = 1; j2 < 5; j2++) {
//                            System.out.print(map[j][j2] + " ");
//                        }
//                        System.out.println();
//                    }
                }
                col_size = maxCol_value;
            }
            // C연산
            else if (row_size < col_size) {
                int maxRow_value = Integer.MIN_VALUE;
                for (int i = 1; i < 101; i++) {
                    for (int k1 = 0; k1 < count.length; k1++) {
                        count[k1] = new pair(0,0);
                    }
                    int new_size = 0;
                    for (int j = 1; j < 101; j++) {
                        if (map[j][i] != 0) {
                            count[map[j][i]].cnt++;
                            count[map[j][i]].number = map[j][i];
                        }
                    }
                    // 한 열에 대한 검사가 끝나면~
                    Arrays.sort(count, new Comparator<pair>() {
                        @Override
                        public int compare(pair o1, pair o2) {
                            if (o1.cnt == o2.cnt)
                                return o1.number - o2.number;
                            return o1.cnt - o2.cnt;
                        }
                    });
//                    System.out.println("===========C연산 count=============");
//                    for (int j = 0; j < 101; j++) {
//                        if(count[j].cnt != 0)
//                            System.out.println("number : " + count[j].number + " cnt : " + count[j].cnt);
//                    }
                    int idx = 1;
                    for (int j = 1; j < 101; j++) {
                        if(count[j].cnt != 0) {
                            map[idx++][i] = count[j].number;
                            map[idx++][i] = count[j].cnt;
                            new_size += 2;
                        }
                    }
                    int row_value = new_size;
                    if (maxRow_value < row_value) {
                        maxRow_value = row_value;
                    }
                    for (int j = idx; j < 101; j++) {
                        map[j][i] = 0;
                    }
//                    System.out.println("=========C연산 map===========");
//                    for (int j = 1; j < 5; j++) {
//                        for (int j2 = 1; j2 < 5; j2++) {
//                            System.out.print(map[j][j2] + " ");
//                        }
//                        System.out.println();
//                    }
                }
                row_size = maxRow_value;
            }
        }
        System.out.println(time);
    } // end of main
} // end of class
cs

count만 사용하면 시간절약을 할 수 있겠다고 생각했지만 오히려 0.2초 정도 늘었다. 소스코드를 보면서 왜 그럴까 생각해보니 list를 초기화하는 부분 , count를 초기화하는 부분과 list정렬 , count정렬 이렇게 두 가지 부분에서 count만 사용했을 경우 더 많은 시간을 사용할 수 있을 것이라 생각했다.

저작자표시

'APS' 카테고리의 다른 글

BOJ17136_색종이 붙이기  (0) 2019.09.03
SWEA1767_[SW Test 샘플문제] 프로세서 연결하기  (2) 2019.09.03
BOJ16235_나무 재테크(시간제한 변경으로 다시)  (0) 2019.08.31
SWEA1953_[모의 SW 역량테스트] 탈주범 검거  (0) 2019.08.29
SWEA2112_[모의 SW 역량테스트] 보호 필름  (2) 2019.08.26
'APS' Related Articles more