티스토리 뷰

알고리즘/백준

백준 17140 (이차원 배열과 연산) - java

김다미김태리신시아 2023. 8. 8. 00:06

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