https://www.acmicpc.net/problem/17140
17140번: 이차원 배열과 연산
첫째 줄에 r, c, k가 주어진다. (1 ≤ r, c, k ≤ 100) 둘째 줄부터 3개의 줄에 배열 A에 들어있는 수가 주어진다. 배열 A에 들어있는 수는 100보다 작거나 같은 자연수이다.
www.acmicpc.net
#문제
크기가 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가 되기 위한 최소 시간을 구해보자.
#알고리즘
구현
정렬
시뮬레이션
#풀이방법
처음 봤을때 문제 자체가 이해가 가질 않아 문제를 이해하는데 많은 시간이 걸렸다.
문제를 푸는 해결하는 순서는 이와 같다.
초기 배열의 크기는 3x3 이고, rowSize와 colSize를 3으로 놓고,
주어진 조건에 만족 할 때까지 rowSize와 colSize를 매번 비교해 R연산과 L연산을 수행한다.
또한 R연산과 L연산을 할때마다 rowSize와 colSize를 최신화 해주어야 한다.
1. R 연산
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 | //모든 행에 대하여 정렬 public static void calR() { //해쉬맵을 사용하여 각 숫자가 몇번 나왔는지 확인한다. HashMap<Integer,Integer> map; int col = 0; for(int i=0; i<rowSize; i++) { map = new HashMap<>(); for(int j=0; j<colSize; j++) { if(arr[i][j] == 0) continue; //0인 경우는 무시 if(map.containsKey(arr[i][j])) { map.put(arr[i][j],map.get(arr[i][j])+1); }//숫자가 나올때마다 count 해 줌. else { map.put(arr[i][j],1); } } List<Entry<Integer, Integer>> list_entries = new ArrayList<Entry<Integer, Integer>>(map.entrySet()); // 비교함수 Comparator를 사용하여 오름차순으로 정렬 Collections.sort(list_entries, new Comparator<Entry<Integer, Integer>>() { // compare로 값을 비교 public int compare(Entry<Integer, Integer> obj1, Entry<Integer, Integer> obj2) { // 오름 차순 정렬 if(obj1.getValue() != obj2.getValue()) return obj1.getValue().compareTo(obj2.getValue());//value 오름차순으로 정렬 else return obj1.getKey().compareTo(obj2.getKey());//value가 같을 경우 key로 오름차순 정렬 } });//나온 숫자대로 int idx = 0; //0으로 초기화되는 연산 수행 for(int j=0; j<colSize; j++) { arr[i][j] = 0; } for(Entry<Integer, Integer> entry : list_entries) { arr[i][idx++] = entry.getKey(); arr[i][idx++] = entry.getValue(); if(idx > 99) break;//100이 넘을 경우 무시 }//정렬된 값을 다시 arr 배열에 넣어줌. col = Math.max(col, idx); //가장 큰 idx를 col로 최신화 해준다. } colSize = col; //colSize 최신화 } | cs |
각 숫자가 몇번 나왔는지를 확인하기 위해 HashMap을 이용하여 카운트 해주었다.
주어진 hashmap을 정렬하여 0으로 초기화 된 행에 idx 선언하여 값을 넣고, col = Math.max(col,idx)로 col을 최대크기로 맞춘 후, 모든 행을 돌고, rowSize를 최신화 해주었다.
2 . L 연산
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 | //모든 열에대한 연산 수행 public static void calL() { //해쉬맵 사용 HashMap<Integer,Integer> map; int row = 0; for(int i=0; i<colSize; i++) { map = new HashMap<>(); for(int j=0; j<rowSize; j++) { if(arr[j][i] == 0) continue; if(map.containsKey(arr[j][i])) { map.put(arr[j][i],map.get(arr[j][i])+1); } else { map.put(arr[j][i],1); } } List<Entry<Integer, Integer>> list_entries = new ArrayList<Entry<Integer, Integer>>(map.entrySet()); // 비교함수 Comparator를 사용하여 오름차순으로 정렬 Collections.sort(list_entries, new Comparator<Entry<Integer, Integer>>() { // compare로 값을 비교 public int compare(Entry<Integer, Integer> obj1, Entry<Integer, Integer> obj2) { // 오름 차순 정렬 if(obj1.getValue() != obj2.getValue()) return obj1.getValue().compareTo(obj2.getValue()); else return obj1.getKey().compareTo(obj2.getKey()); } }); int idx = 0; //0으로 초기화되는 연산 수행 for(int j=0; j<rowSize; j++) { arr[j][i] = 0; } for(Entry<Integer, Integer> entry : list_entries) { arr[idx++][i] = entry.getKey(); arr[idx++][i] = entry.getValue(); if(idx > 99) break; } row = Math.max(row, idx); } rowSize = row; } | cs |
R연산과 마찬가지로 모든 열을 돌고 난 후, colSize를 최신화하여 연산을 수행한다.
#전체 코드
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 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 | import java.util.*; import java.util.Map.Entry; //2t public class Main { static int count = 0; static int rowSize = 3;//행 static int colSize = 3;//열 static int[][] arr = new int[100][100]; public static void main(String[] args) { Scanner sc = new Scanner(System.in); int r = sc.nextInt()-1; int c = sc.nextInt()-1; int k = sc.nextInt(); for(int i=0; i<3; i++) { for(int j=0; j<3; j++) arr[i][j] = sc.nextInt(); } while(true) { if(count > 100) { System.out.println(-1); return; }//횟수가 100이 넘을 경우 -1을 출력하고, return if(arr[r][c] == k) break;//해당 좌표가 k인경우 break if(rowSize >= colSize) { calR(); }//R연산, 모든 행에 대해 수행 else { calL(); }//L연산, 모든 열에 대해 수행 count++; } System.out.println(count); } //모든 행에 대하여 정렬 public static void calR() { //해쉬맵을 사용하여 각 숫자가 몇번 나왔는지 확인한다. HashMap<Integer,Integer> map; int col = 0; for(int i=0; i<rowSize; i++) { map = new HashMap<>(); for(int j=0; j<colSize; j++) { if(arr[i][j] == 0) continue; //0인 경우는 무시 if(map.containsKey(arr[i][j])) { map.put(arr[i][j],map.get(arr[i][j])+1); }//숫자가 나올때마다 count 해 줌. else { map.put(arr[i][j],1); } } List<Entry<Integer, Integer>> list_entries = new ArrayList<Entry<Integer, Integer>>(map.entrySet()); // 비교함수 Comparator를 사용하여 오름차순으로 정렬 Collections.sort(list_entries, new Comparator<Entry<Integer, Integer>>() { // compare로 값을 비교 public int compare(Entry<Integer, Integer> obj1, Entry<Integer, Integer> obj2) { // 오름 차순 정렬 if(obj1.getValue() != obj2.getValue()) return obj1.getValue().compareTo(obj2.getValue());//value 오름차순으로 정렬 else return obj1.getKey().compareTo(obj2.getKey());//value가 같을 경우 key로 오름차순 정렬 } });//나온 숫자대로 int idx = 0; //0으로 초기화되는 연산 수행 for(int j=0; j<colSize; j++) { arr[i][j] = 0; } for(Entry<Integer, Integer> entry : list_entries) { arr[i][idx++] = entry.getKey(); arr[i][idx++] = entry.getValue(); if(idx > 99) break;//100이 넘을 경우 무시 }//정렬된 값을 다시 arr 배열에 넣어줌. col = Math.max(col, idx); //가장 큰 idx를 col로 최신화 해준다. } colSize = col; //colSize 최신화 } //모든 열에대한 연산 수행 public static void calL() { //해쉬맵 사용 HashMap<Integer,Integer> map; int row = 0; for(int i=0; i<colSize; i++) { map = new HashMap<>(); for(int j=0; j<rowSize; j++) { if(arr[j][i] == 0) continue; if(map.containsKey(arr[j][i])) { map.put(arr[j][i],map.get(arr[j][i])+1); } else { map.put(arr[j][i],1); } } List<Entry<Integer, Integer>> list_entries = new ArrayList<Entry<Integer, Integer>>(map.entrySet()); // 비교함수 Comparator를 사용하여 오름차순으로 정렬 Collections.sort(list_entries, new Comparator<Entry<Integer, Integer>>() { // compare로 값을 비교 public int compare(Entry<Integer, Integer> obj1, Entry<Integer, Integer> obj2) { // 오름 차순 정렬 if(obj1.getValue() != obj2.getValue()) return obj1.getValue().compareTo(obj2.getValue()); else return obj1.getKey().compareTo(obj2.getKey()); } }); int idx = 0; //0으로 초기화되는 연산 수행 for(int j=0; j<rowSize; j++) { arr[j][i] = 0; } for(Entry<Integer, Integer> entry : list_entries) { arr[idx++][i] = entry.getKey(); arr[idx++][i] = entry.getValue(); if(idx > 99) break; } row = Math.max(row, idx); } rowSize = row; } } | cs |
'알고리즘 문제' 카테고리의 다른 글
| 백준 9009번) 피보나치 (JAVA) (0) | 2022.10.03 |
|---|---|
| 백준 1946번) 신입 사원 (JAVA) (4) | 2022.09.26 |
| 프로그래머스) 방금 그곡 (JAVA) (0) | 2022.09.05 |
| 프로그래머스) 단체사진 찍기 (0) | 2022.08.12 |
| 백준 17406번) 배열 돌리기 4 (JAVA) (0) | 2022.08.11 |