[3번째 알고리즘 모임] 4문제

장문의 글입니다. 필요한 부분 이 있다 면 찾기로 찾아주세요.
지난번 포스팅 은 미디엄에 있으니 요기로 이동해서 확인해주세요.

0615 PS 3문제.

이번 모임에는 따로 문제의 카테고리 없이 각자 한 문제씩 들고 와서 풀기로 했다, 새로운 분이 합류하여 총 4문제를 풀어야 한다. 각 문항당 30분의 시간이 주어지고, 30분 이 지나면 즉각적으로 풀이를 진행한다.

 

문제 1. 스도쿠(백준 2580, Java)
풀러 가기 (백준 스도쿠)

2580번: 스도쿠

내가 가져간 문제이고 나는 풀지 못했다, bfs를 활용해서 풀려고 접근했다가 머리 깡 당했다.

 

1. 비어있는 부분을 큐에 넣어준다.

2. 3*3 , 세로, 가로 모두 중복된 숫자가 없는지 확인한다.

3. 위의 2번이 통과된다면 숫자를 집어넣고 큐에서 제거한다. 아니라면 다시 큐에 넣어준다. 

 

위와 같은 방식으로 접근했고 줄줄이 틀렸다...... 😭 약 2일 동안 댐 같은 고집으로 이리저리 굴려 봤으나 실패했다...  어떤 부분이 실패의 주된 원인인가 확인해보니 내가 고려한 부분은 오로지 하나의 경우의 수만 고려했기 때문 에 정답이 나오지 않거나 혹은 무한히 스도쿠를 반복하는 경우가 발생한다...ㅠ

 

모임 안에서도 대부분 비슷한 접근법을 이용하였고, 몇몇 분들은 거의 근사한 접근법까지 접근했으나 시간 부족으로 구현에 실패했거나 혹은 스도쿠라는 개념이 생소하여 문제 이해에서 곤혹을 겪으신 분이 있다. 아래 코드 들은 스도쿠에 대한 기본적인 이해가 있어야 이해가 되니 스도쿠를 모른다면 검색해서 개괄적인 게임 룰을 인지하고 왔으면 한다.

 

총 3가지 의 방법을 소개하겠다. 하나만 이해가 된다면 모든 풀이법을 이해할수 있으니 읽기 쉽고 본인에게 직관적인 부분을 보고 구현에 힘을 써보자.

1. 풀이 입력을 받아온 숫자에서 만약 빈칸 에 들어갈 모든 수에 대해 dfs를 구현하고 그 수를 이용해 스도쿠를 완성 못한다면 다시 거슬러 올라가면서 문제를 해결하는 방법이다. 말은 쉬우나 막상 코드로 구현해보려면 정말 난해하다.

 

// 596 ms
public class Boj2580 {
    static int[][] grid;

    public static void main(String[] args) throws IOException {
        grid = new int[9][9];
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        for (int i = 0; i < grid.length; i++) {
          String[] inputs = bf.readLine().split(" ");
           for (int j = 0; j < inputs.length; j++) {
             grid[i][j] = Integer.parseInt(inputs[j]);
           }
         }
         dfs(0, 0); // 0,0 즉 좍측 제일 위에부터 dfs 를 진행할 예정이다.
         bf.close();
        s.main();
    }
	/*
   	dfs 에서 해야할 일
     - 1. 모든 스도쿠 방문을 순회해야 한다.
     - 2. 만약 비어있는 공간이라면 그곳에 대한 숫자 판별을 하고 다음으로 넘겨주어야 한다.
     - 3. 모든 칸을 순회했지만 아직 비어있는 곳이 있다면 ? 다시 거슬로 올라와 다른 숫자를 판별한다.
    */
    public static void dfs(int row, int col) {
        if (col == 9) { //col 기준 으로 진행 되기때문에 가장 먼저 if 체크를 해준다.
            dfs(row + 1, 0); // col이 8 이 된다면 1줄 증가시켜준다.
            return;
        }
        if (row == 9) { // 모든 방문이 끝났다. 그대로 종료해준다.
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < 9; i++) {
                for (int j = 0; j < 9; j++) {
                    sb.append(grid[i][j]).append(' ');
                }
                sb.append('\n');
            }
            System.out.println(sb.toString());
            System.exit(0); // 이부분이 없다면, 결국 2가지의 해답을 얻는다. 모두 채워진 경우 or 아무것도 채우지 않은 경우
        }

        if (grid[row][col] == 0) { // 0 이 된다면 ? 체크를 진행해주자
            for (int i = 1; i < 10; i++) {
                if (checker(row, col, i)) { 아래함수 를 참조
                    grid[row][col] = i; 결과 값에 따른 업데이트
                    dfs(row, col + 1); 다음 칼럼으로 진행
                }
            }
            grid[row][col] = 0; for 를 이용해 돌았지만 아직 0 이고 다음함수로 못넘어가고 아래로 내려온다면 ? 0으로 복귀
            return; //이후 현재 재귀를 종료, 현재 진행중인 칸이 답이 아니니 그 전칸으로 거슬로 올라가자.
        }
        dfs(row, col + 1); //0이 아니고 col 이 8 도 아니고 row 가 8 도아니라면 ? 다음으로 가자
    }

    public static boolean checker(int row, int col, int val) {
        // 칼럼 체크를 위한 for문 확인
        for (int i = 0; i < 9; i++) {
            if (grid[i][col] == val)
                return false;
        }
        // 로우 체크를 위한 for 문 확인
        for (int i = 0; i < 9; i++) {
            if (grid[row][i] == val)
                return false;
        }
        // 3*3  확인을 위한 for 문
        int startRow = (row / 3) * 3;
        int startCol = (col / 3) * 3;
        for (int i = startRow; i < startRow + 3; i++) {
            for (int j = startCol; j < startCol + 3; j++) {
                if (grid[i][j] == val)
                    return false;
            }
        }
        return true;
    }
}

개괄적인 설명은 위에 주석이 첨부 되어있으니 가장 핵심적인 부분을 다시 반복해서 말하겠다. 

 왼쪽 이미지를 보자 우리는 칼럼에 의해 순서를 따라가기 때문에 첫 번째 0 에는 1 또는 9 가 들어간다

우리 for 문 logic 에 의해 1 이 가장 먼저 검사가 되고 인증된 숫자로 0자리에 1이 들어가게 된다. 자 두 번째 0 검사를 시작하자 어라 9가 중복되어 들어간다. 3*3 배열을 확인해보니 여기는 숫자가 들어갈 수가 없다.

 

우리의 재귀는 1 (채운수) > 0 인것이다. 다시 거슬러 올라가(현재 재귀를 리턴으로 종료한다.) for 문의 2부터 다시 탐색을 시작해 결국 9 가 들어가게 되는 것이다. 말을 이렇게 풀어놔서 그렇지 본인이 직접 그려보자. 이해가 더욱 빠를 것이다.

 

2. 두 번째 풀이를 보자. 큰 포괄적인 개념은 위에 설명한 것과 동일하다.

// 500ms
class Boj2580_03 {
    static int[][] grid;

    public void main() throws IOException {
        grid = new int[9][9];
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        for (int i = 0; i < grid.length; i++) {
            String[] inputs = bf.readLine().split(" ");
            for (int j = 0; j < inputs.length; j++) {
                grid[i][j] = Integer.parseInt(inputs[j]);
            }
        }
        solve(0);

        System.out.println("done");

        StringBuffer sb = new StringBuffer();
        for (int[] g : grid) {
            for (int x : g) {
                sb.append(x + " ");
            }
            sb.append("\n");
        }
        System.out.println(sb.toString());
    }
	// 불리언을 반환해 재귀 호출 할떄 이용한다.
    public boolean solve(int n) { // 좌표를 넘겨주는것이 아닌 현재 탐색된 갯수를 넘겨준다.
        if (n == 81) // 총 9*9 칸이므로 이와같은 결과 가 나온다.
            return true;
        int row = n / 9; //나눈값은 로우가 되고
        int col = n % 9; // 나머지값은 칼럼이된다. 알아두면 유용하니 기억해두자.
        if (grid[row][col] != 0) {
            return solve(n + 1); //0이 아니라면 체크해줄 이유가 없으니 다음으로 넘어간다.
        } else {
            for (int i = 1; i < 10; i++) {
                if (isValid(row, col, i)) {
                    grid[row][col] = i;
                    // 다음 재귀로 넘겨주는것을 if 로 받는다..
                    if (solve(n + 1)) 
                        return true;
                    grid[row][col] = 0; //if에걸리지 않아 리턴못한다면 ? 0으로 초기화해준후
                }
            }
            return false; // false 를 리턴한다.
        }
    }

    public boolean isValid(int row, int col, int val) {
    // 일기 힘들지만 자세히 본다면 한번에 for 문을 체크하기 때문에 납득할만하다.
        for (int i = 0; i < 9; i++) {
            if (grid[row][i] == val ||
                    grid[i][col] == val ||
                    grid[(row / 3) * 3 + i / 3][(col / 3) * 3 + i % 3] == val) {
                return false;
            }
        }
        return true;
    }
}

1번 코드가 이해되었다면 2번 코드 또한 자연스레 이해가 될 것이다.

이 풀이의  특징이라면 재귀의 반환 값을 불리언을 지정하고 그것을 이용하는 것 과 좌표 가 아닌 숫자를 넘겨 좌표 계산하는 방법이다.

 

3. 세 번째 풀이

//392ms

class Boj2580_02 {
    static int[][] grid;

    public void main() throws IOException {
        grid = new int[9][9];
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        for (int i = 0; i < grid.length; i++) {
            String[] inputs = bf.readLine().split(" ");
            for (int j = 0; j < inputs.length; j++) {
                grid[i][j] = Integer.parseInt(inputs[j]);
            }
        }
        solve(0);
        System.out.println("done");
        StringBuffer sb = new StringBuffer();
        for (int[] g : grid) {
            for (int x : g) {
                sb.append(x + " ");
            }
            sb.append("\n");
        }
        System.out.println(sb.toString());
    }

    public boolean solve(int cur) {
        if (cur == 81)
            return true;
        int row = cur / 9;
        int col = cur % 9;
        if (grid[row][col] != 0)
            return solve(cur + 1);
        boolean[] flag = new boolean[10]; // 숫자를 체크해줄 배열
        validCheck(row, col, flag); 
        for (int i = 1; i < 10; i++) {
            if (flag[i]) { //그숫자가 트루인 경우에만 다음으로 넘어간다.
                grid[row][col] = i;
                if (solve(cur + 1)) {
                    return true;
                }
            }
        }
        grid[row][col] = 0; //위의 for loop 이끝나도록 반환이 안된다면? 0으로 바꾼후 false
        return false;
    }

    public void validCheck(int row, int col, boolean[] flag) {
        Arrays.fill(flag, true); // 모두 트루로 채워주고 검사를 통해 false 로 바꿔준다.
        for (int i = 0; i < 9; i++) {
            if (grid[row][i] != 0)
                flag[grid[row][i]] = false;
            if (grid[i][col] != 0)
                flag[grid[i][col]] = false;
            int r = (row / 3) * 3 + i / 3;
            int c = (col / 3) * 3 + i % 3;
            if (grid[r][c] != 0)
                flag[grid[r][c]] = false;
        }
    }

가장 좋다고 생각한 풀이이다. 배열을 이용해 숫자를 체크해주고 그에 대한 반환 값과 for loop의 연산이 모두 종료된 이후 처리해주는 모든 부분이 제일 직관적이고 빠르다.

 

문제 2. 영역 구하기(백준 2583, Java)

풀러 가기

2583번: 영역 구하기

제대로 못 풀었다, 좌표를 받아와 이차원 배열에 넣을 때 어떻게 계산을 해주어야 할지 계속 고민하고 그려보고 몇 번을 그려 봤는지 모르겠다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

/**
 * 5 7 3
 * 0 2 4 4
 * 1 1 2 5
 * 4 0 6 2
 * */

public class Test{
    static int N;
    static int M;
    static int[][] grid;
    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        String[] inputs = bf.readLine().split(" ");
        N=Integer.parseInt(inputs[0]) ;
        M=Integer.parseInt(inputs[1]) ;
        grid = new int[N][M];
        for (int i = 0; i < Integer.parseInt(inputs[2]); i++) {
            String[] coordinates = bf.readLine().split(" ");
            for (int j = Integer.parseInt(coordinates[1]); j < Integer.parseInt(coordinates[3]); j++) {
                for (int k = Integer.parseInt(coordinates[0]); k < Integer.parseInt(coordinates[2]); k++) {
                    grid[j][k] = 1;
                }
            }
        }
        bf.close();
        for(int[] x :grid){
            for(int c : x){
                System.out.print(c+" ");
            }
            System.out.println();
        }
        ArrayList<Integer> answer = new ArrayList<>();
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[i].length; j++) {
                if(grid[i][j]  == 0){
                    grid[i][j] = 1;
                    answer.add(bfs(i,j));
                }
            }
        }
        System.out.println(answer.size());
        Collections.sort(answer);
        for (Integer integer : answer) {
            System.out.print(integer + " ");
        }
    }
    static int bfs(int row,int col){
        int[] dirs = {0,1,0,-1,0};
        Queue<int[]> q = new LinkedList<>();
        q.offer(new int[]{row,col});
        int cnt = 1;
        while(!q.isEmpty()){
            int[] cur = q.poll();
            for (int i = 1; i < dirs.length; i++) {
                int nRow = cur[0]+dirs[i];
                int nCol = cur[1]+dirs[i-1];
                if(0<= nRow && nRow < N && 0<=nCol && nCol<M && grid[nRow][nCol] != 1){
                    grid[nRow][nCol] = 1;
                    q.offer(new int[]{nRow,nCol});
                    cnt++;
                }
            }
        }
        return cnt;
    }
}

문제 가져오신 분의 설명을 듣고 bfs로 구현해 보았다. 좌표를 그리드에 넣는 부분이 이문제의 키포인트이다.

좌표를 가져와서 그대로 좌우반전만 해서 그리드에 넣는다면 아마 상하 반전이 될 텐데 그걸 이해하고 넘어가야 좌표를 그리드에 집어넣을 수 있다.나머지 부분은 일반 bfs와 다를 바 없다.

 

문제 가져오신 분의 dfs를 보자.

import java.io.*;
import java.util.*;

// 백준 2583번
// https://www.acmicpc.net/problem/2583
public class Practice070 {
    public static ArrayList<Integer> area; // 각 분리된 부분의 넓이 배열
    public static int areatmp; // 재귀돌면서 넓이 저장할 변수
    public static int[][] grid; // 땅
    public static void dfs(int[][] grid, int i, int j) {
        int[][] dir = {{1,0}, {0,1}, {-1,0}, {0,-1}}; // 동서남북
        grid[i][j] = 1; // 1로 바꾸고 (방문배열이 필요한 경우도 있음)
        areatmp++; // 넓이 더하기
        for (int[] d : dir) {
            int x = i + d[0];
            int y = j + d[1];
            // 그리드 안에 있으면서, 0인 경우
            if(x>=0 && y>=0 && x<grid.length && y<grid[0].length && grid[x][y]==0) {
                dfs(grid, x, y); // 재귀호출
            }
        }
    }

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int m, n, times;
        String[] tmp1 = br.readLine().split(" ");
        m = Integer.parseInt(tmp1[0]);
        n = Integer.parseInt(tmp1[1]);
        times = Integer.parseInt(tmp1[2]);

        grid = new int[m][n];
        area = new ArrayList<>();

        // 배열에 1 집어넣기
        for (int i = 0; i < times; i++) {
            int x1, x2, y1, y2;
            String[] tmp2 = br.readLine().split(" ");
            x1 = Integer.parseInt(tmp2[0]);
            y1 = Integer.parseInt(tmp2[1]);
            x2 = Integer.parseInt(tmp2[2]);
            y2 = Integer.parseInt(tmp2[3]);
            for (int j = y1; j < y2; j++) { // <- for문을 돌때
                for (int k = x1; k < x2; k++) { // <- 미리 배열의 인덱스를 제대로 처리해보자
                    grid[j][k] = 1;
                }
            }
        }

        // 배열 돌면서 0이면 dfs돌기
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if(grid[i][j]==0) {
                    dfs(grid, i, j);
                    area.add(areatmp);
                    areatmp = 0;
                }
            }
        }
        // 출력
        area.sort(Comparator.naturalOrder());
        System.out.println(area.size());
        for (int i = 0; i < area.size(); i++) {
            System.out.print(area.get(i) + " ");
        }
    }
}

주석이 너무 깔끔해 설명은 생략하겠다.

 

문제 3. 랜선 자르기(백준 1654, Java)

풀러 가기

1654번: 랜선 자르기

주어진 랜선을 잘라 원하는 개수를 맞춰주어야 하는데,,, 범위가 어마 무시하다. 이분 탐색을 바로 생각해 어렵지 않게 풀이가 가능했다.

import java.io.*;

public class Test{
    static int N;
    static int target;
    static int[] lenCable;
    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        String[] inputs = bf.readLine().split(" ");
        N = Integer.parseInt(inputs[0]);
        target = Integer.parseInt(inputs[1]);
        lenCable = new int[N];

        long total = 0;
        for (int i = 0; i < N; i++) {
            lenCable[i] = Integer.parseInt(bf.readLine());
            total += lenCable[i];
        }

        long left = 1;
        long right = (total/target);
        while(left <= right){
            long mid = (left+right)/2;
            int cnt = 0;
            for (int i = 0; i < lenCable.length; i++) {
                cnt += (int)lenCable[i]/mid;
            }
            if(cnt < target){
                right = mid-1;
            }else{
                left = mid+1;
            }
        }
        System.out.println(left-1);
    }
}

left와 right의 범위를 설정해주는 부분만 신경 쓴다면 어렵지 않은 문제이다. long을 이용해 범위가 아웃되는 예외를 처리해주고,  들어갈 전깃줄의 모든합 을 이용해 나누어주어 최대 값을 선정하는 부분이 이문제의 키포인트이다.

문제를 가져온 분과 매우 유사한 풀이가 이기에 코드를 첨부하지 않겠다.

 

문제 4. 기능 개발(프로그래머스, Java)

풀러 가기

코딩테스트 연습 - 기능개발

현재의 진행된 작업과 작업의 진행의 속도가 다르고, 또 작업은 앞에서부터 순차적으로 마무리되어야 한다.

최초 생각은 arraylist를 이용해 작업을 해 줄생각을 해보니 굳이 지우고 해줄 필요가 없는 것이다.. 큐를 이용하면 들어온 순서로 쉽게 구현이 가능한데 굳이 돌아갈 이유가 없어 반줄 정도 작성한 코드를 지우고 큐를 이용해 구성했다. 

 

문제 가져오신 분의 코드를 보자 주석과 설명이 깔끔하다.

 

import java.util.*;

public class Test1 {

    public static  int[] solution(int[] progresses, int[] speeds) {

        Queue<Integer> daysQueue = new LinkedList<>();
        Queue<Integer> resQueue = new LinkedList<>();

        for(int i = 0; i < progresses.length; ++i) {
            int d = (100 - progresses[i] + speeds[i] - 1) / speeds[i];
            // 올림한다. ceil()과 같음

            daysQueue.offer(d);
            // daysQueue = [7, 3, 9] 로부터 [2, 1]을 반환하도록 한다.
            // [7 3] [9]으로 찢어서 [2, 1]이 나오도록
        }

        int day = daysQueue.poll();     // 7
        int cnt = 1;

        while(!daysQueue.isEmpty()){
            int n = daysQueue.poll();   // 3

            if(day >= n){       //  기준값(day)보다 작은 값이 나오면? (기준값보다 큰 값이 나올 때 까지 ++cnt)
                ++cnt;
                continue;
            }

            // 기준값(day)보다 n이 큰 경우는?
            // 현재 cnt를 resQueue에 넣고 cnt를 1로 초기화해야하는 상황
            resQueue.offer(cnt);
            cnt = 1;
            day = n;    // 7이었던 비교 기준이 9로 바뀐다.
        }

        resQueue.offer(cnt);    // 마지막 데이터에 대한 cnt를 넣는다.
        return resQueue.stream().mapToInt(Integer::intValue).toArray();
    }
}

두 개의 queue를 이용해 작업이 완성되면 완성 큐에 넣어주고 완성 큐를 반환한다. 깔끔하다.
모임원 중 한 분이 큐&스택 태그인데 어떻게 스택으로 푸는지도 궁금해하셔서 코드를 작성해 보았다.

 

class Solution01 {
    public int[] solution(int[] progresses, int[] speeds) {
        //**님이 말씀하신 것처럼 스택 을 이용해서 풀어보고자 이렇게 스택선언!
        Stack<Deploy> stack = new Stack<>(); 
        //역순으로 집어넣기 위한 for 문
        for (int i = progresses.length - 1; i >= 0; i--) {
            stack.push(new Deploy(progresses[i], speeds[i]));
        }
        // 정답의 추가를 위한 list
        ArrayList<Integer> list = new ArrayList<>();
        // 누적된 일수를 기록
        int days = 0;
        while (!stack.isEmpty()) {
            Deploy d = stack.pop();  
            int deployed = 1; // 항상 뽑으면 1을 진행한 횟수입니다 !!
            d.current = d.current + d.speeds * days; // 현재 배포진행 율 업데이트 위한 구역
            days += (100 - d.current + d.speeds - 1) / d.speeds; //  days 에 나눠준만큼 더하기(란님이 알려주신 내용 사용)
            while (stack.size() > 0 && stack.peek().current + stack.peek().speeds * days >= 100) {
                //peek 을이용해 다음을 구분하고, poll 사용시 하나 제거됨으로 peek
                //다음 stack 에서 나오는 진행율 + 현재 일자*배포진행속도 가 100 이상이라면 ? 바로 pop 진행하고 배포를 하나 늘려줍니다
                stack.pop();
                deployed++;
            }
            list.add(deployed);
        }
        System.out.println(list);
        return list.stream().mapToInt(Integer::intValue).toArray();
    }

    class Deploy {
        int current;
        int speeds;

        Deploy(int current, int speeds) {
            this.current = current;
            this.speeds = speeds;
        }
    }
}

스택을 이용하기 위해 for문을 이용해 역으로 쌓아 올렸다.

이외에 while 문을 이용해 하나씩 빼서 돌리신 분도 있다. 코드를 보자.

public static ArrayList<Integer> solution(int[] progresses, int[] speeds) {
    ArrayList<Integer> answer = new ArrayList<>();

    int serveIdx = 0; // 배포된 서비스 인덱스
    int serveCnt = 0; // 한번 배포될 때 배포된 기능 카운트
    // 배포를 다 할때까지
    while(serveIdx < progresses.length) {
        // 각 기능 개발
        for (int i = 0; i < progresses.length; i++) {
            if(progresses[i] < 100) {
                progresses[i] += speeds[i];
            }
        }
        // 기능이 완성된것이 있으면 인덱스 옮기고
        if(progresses[serveIdx] >= 100) {
            while(progresses[serveIdx]>=100) {
                serveIdx++;
                serveCnt++;
                if(serveIdx == progresses.length) {
                    answer.add(serveCnt);
                    return answer;
                }
            }
            // 배포된 기능개수 정답배열에 더하기
            answer.add(serveCnt);
            serveCnt = 0;
        }
    }
    return answer;
}

서비스의 인덱스를 기록해주는 것이 이 코드의 포인트이다. 큐 스택을 따로 이용하지 않기 위해 포인트 지접이 되는 곳을 하나씩 기록을 해주는 것이다.

 

문제 5. 정수 삼각형(프로그래머스, Java)

풀러 가기

코딩테스트 연습 - 정수 삼각형

삼각형이 주어지고 하나의 선을 그리면서 아래로 이동후  마지막 줄에서 가장 큰 수를 반환하는 것이다.  즉 위에서 부터 숫자를 가지고 내려가는 방식으로 진행이 된다. 그냥 더해주면서 가면 되고, 중간 숫자들은 윗줄의 앞뒤 숫자를 비교해 큰 값을 넣어주면 되겠다 싶어서 재귀 함수로 구현했다.

import java.util.*;

class Solution {
    public int solution(int[][] triangle) {
        helper(triangle, 1);
        return Arrays.stream(triangle[triangle.length - 1]).max().getAsInt();
    }

    public void helper(int[][] triangle, int level) {
        if (level == triangle.length) {
            return;
        }
        triangle[level][0]+= triangle[level-1][0];
        triangle[level][triangle[level].length-1] += triangle[level-1][triangle[level-1].length-1];
        for (int i = 1; i < triangle[level].length-1; i++) {
            triangle[level][i] += Math.max(triangle[level - 1][i - 1], triangle[level -
                        1][i]);
        }
        helper(triangle, level + 1);
    }
}

 

특별할 것은 따로 없다 단지 좌우측 끝에 들어갈 아이들은 for 문밖에서 미리 계산을 해주고 가운데 들어갈 아이들은 max 메서드를 이용해 큰 수를 더해주는 방법이다. 

 

문제 가져오신 분의 코드를 보자 2종류이다.

 

class Solution {
    /*
    public int solution(int[][] triangle) {
        int answer = 0;
        for(int i = 1; i < triangle.length ; i++){
            for(int j = 0; j < triangle[i].length; j++){
                if(j == 0) 
                    triangle[i][j] = triangle[i][j] + triangle[i-1][j];
                else if(i == j)
                    triangle[i][j] = triangle[i][j] + triangle[i-1][j-1];
                else{
                    int left = triangle[i][j] + triangle[i-1][j-1];
                    int right = triangle[i][j] + triangle[i-1][j];
                    triangle[i][j] =  Math.max(left, right);
                }
                answer = Math.max(answer, triangle[i][j]);
            }
        }
        return answer;
    }
    */
    ////
    
    public int solution(int[][] triangle) {
        for(int i = triangle.length-2; i >= 0 ; i--){
            for(int j = 0; j < triangle[i].length; j++){
                int left = triangle[i][j] + triangle[i+1][j];
                int right = triangle[i][j] + triangle[i+1][j+1];
                triangle[i][j] = Math.max(left, right);
            }
        }
        return triangle[0][0];
    }
    
}

위에서 내가 구현한 코드를 for 문으로 바꾼다면 위에 첫 번째 설루션과 동일하다 신기한 것은 2번째 설루션이다.

생각의 발상을 바꿔 for 문을 역으로 도는 것이다 아래에서부터 위로 올라가 결국 마지막 하나 남은 꼭대기를 반환하는 와 참신하고 효율적인 방법이라고 생각한다.!!

 

대략 4시간 정도를 슬랙의 화상회의를 이용해 문제풀이 및 해설을 진행하였고, 오늘 역시 배워가는 부분이 많아 블로그 작성 중 에도 다시 한번 코드를 보게 되어 좋았다.