티스토리 뷰
https://www.acmicpc.net/problem/17140
17140번: 이차원 배열과 연산
첫째 줄에 r, c, k가 주어진다. (1 ≤ r, c, k ≤ 100) 둘째 줄부터 3개의 줄에 배열 A에 들어있는 수가 주어진다. 배열 A에 들어있는 수는 100보다 작거나 같은 자연수이다.
www.acmicpc.net
유형 : 구현
문제 :
- R 연산: 배열 A의 모든 행에 대해서 정렬을 수행한다. 행의 개수 ≥ 열의 개수인 경우에 적용된다.
- C 연산: 배열 A의 모든 열에 대해서 정렬을 수행한다. 행의 개수 < 열의 개수인 경우에 적용된다.
접근
- R 연산을 하면 열(col)의 크기가 변하고 C 연산을 하면 행(row)의 크기가 변한다.
- 문제에서 자연수만 다루기 때문에 0에 대한 처리가 필요하다.
- 정렬은 우선순위 큐를 사용하였으며 수의 개수에 대한 처리는 HashMap을 사용하였다.
R 연산
static int calR(int row,int col){
int maxCol = 0;
int[][] copy = new int[101][101];
for(int i=1;i<=row;i++)
{
HashMap<Integer, Integer> map = new HashMap<>();
for(int j=1;j<=col;j++) {
if(board[i][j] == 0)
continue;
if (map.containsKey(board[i][j])) {
map.put(board[i][j],map.get(board[i][j])+1);
}
else{
map.put(board[i][j],1);
}
}
PriorityQueue<Node> pq = new PriorityQueue<>(
(x,y) -> {
if(x.c == y.c)
return x.v - y.v;
return x.c - y.c;
}
);
map.forEach(
(x,y)-> pq.add(new Node(x,y))
);
int nCol = pq.size() * 2;
if(nCol >= 100)
nCol = 100;
maxCol = Math.max(maxCol,nCol);
int idx = 1;
while(!pq.isEmpty())
{
Node cur = pq.poll();
copy[i][idx] = cur.v;
idx = idx + 1;
copy[i][idx] = cur.c;
idx = idx + 1;
if(idx >= 100)
break;
}
}
board = copy;
return maxCol;
}
C 연산
static int calC(int row,int col){
int maxRow = 0;
int copy[][] = new int[101][101];
for(int j=1;j<=col;j++)
{
HashMap<Integer, Integer> map = new HashMap<>();
for(int i=1;i<=row;i++)
{
if(board[i][j] == 0)
continue;
if (map.containsKey(board[i][j])) {
map.put(board[i][j],map.get(board[i][j])+1);
}
else{
map.put(board[i][j],1);
}
}
PriorityQueue<Node> pq = new PriorityQueue<>(
(x,y) -> {
if(x.c == y.c)
return x.v - y.v;
return x.c - y.c;
}
);
map.forEach(
(x,y)-> pq.add(new Node(x,y))
);
int nRow = pq.size() * 2;
if(nRow >= 100)
nRow = 100;
maxRow = Math.max(maxRow,nRow);
int idx = 1;
while(!pq.isEmpty())
{
Node cur = pq.poll();
copy[idx][j] = cur.v;
idx = idx + 1;
copy[idx][j] = cur.c;
idx = idx + 1;
if(idx >= 100)
break;
}
}
board = copy;
return maxRow;
}
전체 코드
import java.util.*;
import java.io.*;
public class Main {
static int r = 0;
static int c = 0;
static int k = 0;
static int[][] board = new int[101][101];
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine()," ");
r = Integer.parseInt(st.nextToken());
c = Integer.parseInt(st.nextToken());
k = Integer.parseInt(st.nextToken());
for(int i=1;i<=3;i++)
{
st = new StringTokenizer(br.readLine()," ");
for(int j=1;j<=3;j++)
{
board[i][j] = Integer.parseInt(st.nextToken());
}
}
int row = 3;
int col = 3;
if(board[r][c] == k) {
System.out.println(0);
return;
}
boolean ans = false;
int sec = 1;
for(int i=1;i<=100;i++)
{
if(row >= col)
{
col = calR(row,col);
}
else{
row = calC(row,col);
}
if(board[r][c] == k)
{
ans = true;
sec = i;
break;
}
}
if(ans)
{
System.out.println(sec);
}
else{
System.out.println(-1);
}
br.close();
}
static int calR(int row,int col){
int maxCol = 0;
int[][] copy = new int[101][101];
for(int i=1;i<=row;i++)
{
HashMap<Integer, Integer> map = new HashMap<>();
for(int j=1;j<=col;j++) {
if(board[i][j] == 0)
continue;
if (map.containsKey(board[i][j])) {
map.put(board[i][j],map.get(board[i][j])+1);
}
else{
map.put(board[i][j],1);
}
}
PriorityQueue<Node> pq = new PriorityQueue<>(
(x,y) -> {
if(x.c == y.c)
return x.v - y.v;
return x.c - y.c;
}
);
map.forEach(
(x,y)-> pq.add(new Node(x,y))
);
int nCol = pq.size() * 2;
if(nCol >= 100)
nCol = 100;
maxCol = Math.max(maxCol,nCol);
int idx = 1;
while(!pq.isEmpty())
{
Node cur = pq.poll();
copy[i][idx] = cur.v;
idx = idx + 1;
copy[i][idx] = cur.c;
idx = idx + 1;
if(idx >= 100)
break;
}
}
board = copy;
return maxCol;
}
static void print(int row,int col)
{
for(int i=1;i<=row;i++)
{
for(int j=1;j<=col;j++)
{
System.out.print(board[i][j]+" ");
}
System.out.println();
}
System.out.println();
}
static int calC(int row,int col){
int maxRow = 0;
int copy[][] = new int[101][101];
for(int j=1;j<=col;j++)
{
HashMap<Integer, Integer> map = new HashMap<>();
for(int i=1;i<=row;i++)
{
if(board[i][j] == 0)
continue;
if (map.containsKey(board[i][j])) {
map.put(board[i][j],map.get(board[i][j])+1);
}
else{
map.put(board[i][j],1);
}
}
PriorityQueue<Node> pq = new PriorityQueue<>(
(x,y) -> {
if(x.c == y.c)
return x.v - y.v;
return x.c - y.c;
}
);
map.forEach(
(x,y)-> pq.add(new Node(x,y))
);
int nRow = pq.size() * 2;
if(nRow >= 100)
nRow = 100;
maxRow = Math.max(maxRow,nRow);
int idx = 1;
while(!pq.isEmpty())
{
Node cur = pq.poll();
copy[idx][j] = cur.v;
idx = idx + 1;
copy[idx][j] = cur.c;
idx = idx + 1;
if(idx >= 100)
break;
}
}
board = copy;
return maxRow;
}
}
class Node
{
int v;
int c;
Node(int v,int c)
{
this.v = v;
this.c = c;
}
}
'알고리즘 > 백준' 카테고리의 다른 글
백준 14890 (경사로) - java (0) | 2023.08.14 |
---|---|
백준 17837 (새로운 게임 2) - java (0) | 2023.08.09 |
백준 17779 (게리맨더링 2) - java (0) | 2023.08.07 |
백준 9935 (문자열 폭팔) - java (0) | 2023.08.04 |
백준 17471 (게리맨더링) - java (0) | 2023.08.01 |
공지사항
최근에 올라온 글
최근에 달린 댓글
- Total
- Today
- Yesterday
링크
TAG
- 백준 #14863 #서울에서 경산까지 #java #자바
- 백준 #4963 #섬의 개수
- 자바
- 백준 #치즈 #2638
- 백준 #25195 #yes or yes #java #자바
- 백준 #3980 #선발 명단
- 자바 #JAVA
- 백준 #1325 #효율적인 해킹
- 백준 #15686 #치킨 배달
- 백준 #다리 만들기 #2146
- 백준
- 17218
- Java
- 백준 #18405 #경쟁적 전염
- 백준 #5721 #사탕 줍기 대회 #java #자바
- 백준 #1759 #암호 만들기
- 백준 #12014 #주식 #자바 #java
- 백준 #17940 #주식 #자바 #java
- 백준 #1987 #알파벳 #자바 #java
- 백준 #25603 #짱해커 이동식 #java #자바
- 백준 #2636 #치즈
- 백준 #2580 #스도쿠
- 백준 #13549 #숨바꼭질3
- 백준 #28140 #빨강~ 빨강~ 파랑! 파랑! 달콤한 솜사탕! #java #자바
- 17394
- 백준 #1584 #게임 #java #자바
- 백준 #1727 #커플 만들기 #자바 #java
- 백준 #16973 #직사각형 탈출
- 백준 #인구 이동 #16234
- 백준 #
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 |
글 보관함