[Algorithm] SW 기출문제 - 이차원 배열과 연산(17140) 자바 풀이

안녕하세요. 회사와 함께 성장하고 싶은 KOSE입니다.

이번 포스팅은 백준 SW 기출문제 - 이차원 배열과 연산 자바 풀이를 진행하고자 합니다.

문제 출처: https://www.acmicpc.net/problem/17140

17140번: 이차원 배열과 연산

 

1. 풀이 소스

 

import java.util.*;
import java.io.*;
import static java.lang.Integer.parseInt;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        int r = parseInt(st.nextToken());
        int c = parseInt(st.nextToken());
        int k = parseInt(st.nextToken());
        
        ArrayCalculation array = new ArrayCalculation(r, c, k);
        
        for (int row = 1; row <= 3; row++) {
            st = new StringTokenizer(br.readLine());
            for (int col = 1; col <= 3; col++) {
                array.setMap(row, col, parseInt(st.nextToken()));
            }
        }
        
        array.start();
        System.out.println(array.getTime());
    }
}

class ArrayCalculation {
    int r; // 찾아야 하는 행
    int c; // 찾아야 하는 열
    int k; // 되어야 하는 값
    int time; // k가 되는데까지 걸린 시간
    int rowCnt = 3; // 처음 시작은 3 by 3 이므로 행의 개수
    int colCnt = 3; // 열의 개수
    int[][] map = new int[101][101]; // 총 열과 행의 개수는 100을 넘지 않음 (101 인 이유는 1행, 1열 부터 시작)
    Point[] points = new Point[101];
    
    ArrayCalculation (int r, int c, int k) {
        this.r = r;
        this.c = c;
        this.k = k;
        
        for (int i = 1; i <= 100; i++) points[i] = new Point(i); // 포인트 초기화
    }
    
    void setMap(int row, int col, int value) {
        map[row][col] = value;
    }
    
    void start() {
        while(time < 101) {

            if (map[r][c] == k) return; // 종료 조건

            int nextRowCnt = rowCnt; // 다음 while문에 적용 할 RowCnt
            int nextColCnt = colCnt; // 다음 while문에 적용 할 ColCnt

            if (rowCnt >= colCnt) { // 행이 열보다 같거나 긴 경우
                for (int row = 1; row <= rowCnt; row++) {
                    List<Point> sortList = new ArrayList<>();
                    
                    for (int col = 1; col <= colCnt; col++) {
                        int value = map[row][col]; // map에 저장된 값

                        if (value == 0) continue;
                        Point p = points[value];

                        p.cnt++;
                        if (!p.in) { // 만약 p가 리스트에 없다면
                            p.in = true; // 리스트에 있다는 표시
                            sortList.add(p); // 리스트 추가
                        }
                    }

                    sortList.sort(Comparator.comparing((Point po) -> po.cnt)
                            .thenComparing(po -> po.num));

                    int idx = 1;
                    for (Point p : sortList) {
                        if (idx >= 101) break;
                        map[row][idx] = p.num; // 먼저 1번 인덱스 수
                        map[row][++idx] = p.cnt; // 그 다음 인덱스로 cnt
                        idx++; // idx 증가시키기
                    }
                    
                    for (int col = idx; col < 101; col++) {
                        map[row][col] = 0; // 남아있는 열은 모두 0으로 설정하기
                    }
                    
                    if (row == 1) nextColCnt = idx; // 변경된 col 개수 업데이트
                    else nextColCnt = Math.max(nextColCnt, idx);
                    
                    for (Point p : sortList) {
                        p.cnt = 0; // 초기화 작업
                        p.in = false; // 초기화 작업
                    }
                }
            } 
            
            else {
                for (int col = 1; col <= colCnt; col++) {
                    List<Point> sortList = new ArrayList<>();

                    for (int row = 1; row <= rowCnt; row++) {
                        int value = map[row][col]; // map에 저장된 값
                        if (value == 0) continue;
                        Point p = points[value];

                        p.cnt++;
                        if (!p.in) {
                            p.in = true;
                            sortList.add(p);
                        }
                    }

                    sortList.sort(Comparator.comparing((Point po) -> po.cnt)
                            .thenComparing(po -> po.num));

                    int idx = 1;
                    for (Point p : sortList) {
                        if (idx >= 101) break;
                        map[idx][col] = p.num; // 먼저 1번 인덱스 수
                        map[++idx][col] = p.cnt; // 그 다음 인덱스로 cnt
                        idx++; // idx 증가시키기
                    }

                    for (int row = idx; row < 101; row++) {
                        map[row][col] = 0; // 남아있는 열은 모두 0으로 설정하기
                    }

                    if (col == 1) nextRowCnt = idx; // 변경된 col 개수 업데이트
                    else nextRowCnt = Math.max(nextRowCnt, idx);

                    for (Point p : sortList) {
                        p.cnt = 0; // 초기화 작업
                        p.in = false; // 초기화 작업
                    }
                }
            }

            rowCnt = nextRowCnt;
            colCnt = nextColCnt;

            time++;
        }
    }
    
    int getTime() {
        return time <= 100 ? time : -1; // 100 이하라면 그대로, 101이 된다면 -1
    }
    
    static class Point {
        int num; // point 번호 (숫자)
        int cnt; // 숫자가 행 혹은 열에 나온 갯수
        boolean in; // 리스트에 있는지 없는지 판단
        
        Point (int num) {
            this.num = num;
        }
    }
}

 

 

2. 풀이 중점 사항

 

먼저, 해당 문제는 행과 열을 비교하고 정렬하는 과정이 필요했고, 0.5초의 짧은 시간제한이 있기 때문에 시간 복잡도를 계산하는 과정이 필요했습니다.

 

time은 최대 100, 행 최대 100, 열 최대 100 이므로 약 100만입니다. O(k * n * m) 

arrayList를 생성하여 값을 추가한 후 정렬하는 과정을 생각하였을 때,

sort 정렬은 TimSort 기준으로 O(nlogn)이고 n은 최대 100입니다. (모든 숫자가 전부 다를 수 있으므로)

 

따라서, O(k * n * m + k * n * m logm) => O(k * n * m log m)이라고 볼 수 있기에

약 200만 정도의 시간 복잡도를 가진다고 볼 수 있습니다.

 

1초당 약 1억개의 연산이므로 0.5초는 대략 5000만 개 정도의 연산을 할 수 있다고 생각하면 while 루프 내부에서 이중 for문과 정렬을 활용한 방법을 사용한다면 시간 내에 해결할 수 있을 것이라고 판단하였습니다.

 

Point[] points = new Point[101];
    
ArrayCalculation (int r, int c, int k) {
    this.r = r;
    this.c = c;
    this.k = k;

    for (int i = 1; i <= 100; i++) points[i] = new Point(i); // 포인트 초기화
}

 

핵심은 행에 있는 각 컬럼들의 숫자의 개수에 따라 정렬을 해야 하는 것입니다. 이 문제를 해결하기 위해,
Point를 담은 point 배열을 선언하였고 미리 초기화 하였습니다.

 

if (rowCnt >= colCnt) { // 행이 열보다 같거나 긴 경우
    for (int row = 1; row <= rowCnt; row++) {
        List<Point> sortList = new ArrayList<>();
        
        for (int col = 1; col <= colCnt; col++) {
            int value = map[row][col]; // map에 저장된 값

            if (value == 0) continue;
            Point p = points[value];

            p.cnt++;
            if (!p.in) { // 만약 p가 리스트에 없다면
                p.in = true; // 리스트에 있다는 표시
                sortList.add(p); // 리스트 추가
            }
        }

 

만약 p.in 이 false라면, 아직 정렬을 위한 리스트에 추가되지 않은 것이라고 판단하여 p.in = true로 표시한 후 sortList에 추가하였습니다.

 

sortList.sort(Comparator.comparing((Point po) -> po.cnt)
        .thenComparing(po -> po.num));

int idx = 1;
for (Point p : sortList) {
    if (idx >= 101) break;
    map[row][idx] = p.num; // 먼저 1번 인덱스 수
    map[row][++idx] = p.cnt; // 그 다음 인덱스로 cnt
    idx++; // idx 증가시키기
}

for (int col = idx; col < 101; col++) {
    map[row][col] = 0; // 남아있는 열은 모두 0으로 설정하기
}

 

Comporator.comparing().thenComparing()을 활용하여, 문제 상황에 맞도록 숫자의 개수로 오름차순 정렬, 숫자 개수가 같다면 숫자로 오름차순 하여 정렬하였습니다.

sortList를 순회하여 idx를 설정하여 num, cnt 순서 다시 2차원 배열 map에 추가하였습니다.

idx는 num, cnt로 설정되며 만약 100 이전에 끝난다면 하단의 for문이 실행되고, 101이 되어 종료된 것이라면 하단 for문은 col < 101을 만족하지 않게 됩니다.

 

if (row == 1) nextColCnt = idx; // 변경된 col 개수 업데이트
else nextColCnt = Math.max(nextColCnt, idx);

for (Point p : sortList) {
    p.cnt = 0; // 초기화 작업
    p.in = false; // 초기화 작업
}

 

앞 서 nextRowCnt, nextColCnt를 선언한 이유는 한 번의 while문이 실행된 후 루프를 돌 때, rowCnt, colCnt를 업데이트하기 위함입니다. 해당 로직은 for(int row = 1 ~ ) 내부에 있기 때문에, rowCnt 혹은 colCnt를 바꿔버리면 다음 행에 영향을 주게 됩니다. 한 행에 대한 로직을 마쳤으므로 sortList에서 Point 인스턴스를 순회하며 다시 초기화해주었습니다.

 

이상으로 백준 이차원 배열과 연산 자바 풀이를 마치도록 하겠습니다. 감사합니다.!!!