[코드트리/INTERMEDIATE LOW] 정수 사각형 최장 증가 수열 (JAVA)

📖 문제

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

 

 

 

💡  풀이 방식

• DP (Tabulation)

- 각 칸에 적힌 수들 중 작은 값부터 순서대로 dp 값을 갱신해 저장한다.

→ 이를 위해 오름차순 정렬 필요

 

- 인접한 4칸에 대해 갱신을 진행한다. (단, 격자 범위 내에 있고, 현재 칸의 값보다 작은 경우)

- dp 배열에서 최댓값을 찾는다.

 

 

🔺 코드

import java.util.*;
import java.io.*;
 
public class Main {
    static int[] dx = {-1, 1, 0, 0};
    static int[] dy = {0, 0, -1, 1};
 
    static int N;
    static int[][] grid, dp;
    static int answer = 0;
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
 
        N = Integer.parseInt(br.readLine());
 
        grid = new int[N][N];
        dp = new int[N][N];
 
        PriorityQueue<int[]> pq = new PriorityQueue<>((o1, o2) -> Integer.compare(o1[2], o2[2]));   // 🔔 값 기준 오름차순 정렬
 
        for(int i = 0 ; i < N ; i++) {
            Arrays.fill(dp[i], 1);
 
            st = new StringTokenizer(br.readLine(), " ");            
            for(int j = 0 ; j < N ; j++) {
                grid[i][j] = Integer.parseInt(st.nextToken());
                pq.offer(new int[] {i, j, grid[i][j]});
            }
        }        
 
        while(!pq.isEmpty()) {
            int[] now = pq.poll();
            int x = now[0];
            int y = now[1];
            int num = now[2];
 
            for(int d = 0 ; d < 4 ; d++) {
                int nx = x + dx[d];
                int ny = y + dy[d];
 
                if(!inRange(nx, ny))    continue;
 
                if(num < grid[nx][ny]) {
                    dp[nx][ny] = Math.max(dp[nx][ny], dp[x][y] + 1);
                }
            }
 
            answer = Math.max(answer, dp[x][y]);
        }
 
        System.out.println(answer);
    }
 
    private static boolean inRange(int x, int y) {
        return (0 <= x && x < N && 0 <= y && y < N);
    }
}
 

 

 

 

 

➕ 다른 풀이 방식

클래스에 해당 칸의 값, 행, 열 값 저장하였고,

클래스 객체 리스트를 값의 오름차순 정렬하는 방법이 다르다. (Comparable, compareTo 사용)

import java.util.*;
import java.io.*;
 
public class Main {
    static int[] dx = {-1, 1,  0, 0};
    static int[] dy = { 0, 0, -1, 1};
    
    static int n;
    static int[][] grid, dp;
    
    static List<Cell> cells = new ArrayList<>();
    static int ans = 0;
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        
        grid = new int[n][n];
        dp = new int[n][n];
 
        for(int i = 0; i < n; i++) {
            Arrays.fill(dp[i], 1);  // 초기 DP 값 모두 1로 초기화
        
            for(int j = 0; j < n; j++) {
                grid[i][j] = sc.nextInt();
                cells.add(new Cell(grid[i][j], i, j));  // (값, 행, 열)
            }
        }
        Collections.sort(cells);    //  값 기준 오름차순 정렬⭐ 
 
        // 정수값이 작은 칸부터 보며 4방향에 대해 dp 값 갱신
        for(int i = 0; i < cells.size(); i++) {
            int x = cells.get(i).x;
            int y = cells.get(i).y;
 
            // 인접한 4개의 칸에 대해 갱신
            for(int d = 0; d < 4; d++) {
                int nx = x + dx[d];
                int ny = y + dy[d];
                
                if(inRange(nx, ny) && grid[nx][ny] > grid[x][y])
                    dp[nx][ny] = Math.max(dp[nx][ny], dp[x][y] + 1);
            }
        }
 
        // 전체 수들 중 최댓값 탐색
        for(int i = 0; i < n; i++)
            for(int j = 0; j < n; j++)
                ans = Math.max(ans, dp[i][j]);
 
        System.out.print(ans);
    }
    
    public static boolean inRange(int x, int y) {
        return 0 <= x && x < n && 0 <= y && y < n;
    }
}
 
 
class Cell implements Comparable<Cell> {
    int num, x, y;
 
    public Cell(int num, int x, int y) {
        this.num = num;
        this.x = x;
        this.y = y;
    }
 
    @Override
    public int compareTo(Cell c) {
        return this.num - c.num;      // num 기준 오름차순 정렬
    }
}

 

---

💦 어려웠던 점

- 메모이제이션 방식으로 dp 배열 채우려고 했는데 구현을 잘못했는지 답이 틀렸었다ㅠ 그래서 다른 분 풀이를 보았다..

 

 

 

1회독	2회독	3회독	4회독	5회독
V

---

(참고)

✔ 코드트리

코드트리_정수 사각형 최장 증가 수열