2022-06-29 [5회차] 알고리즘 스터디

 

1. 색종이 만들기 - 실버 2

출처:  백준 2630번 https://www.acmicpc.net/problem/2630

2630번: 색종이 만들기

 

  MySol)

    - while문으로 작성하려 해서 결국 못 풀었다.

    - 재귀함수, 백트래킹을 이용해서 풀어야한다.

 

  Sol) 스터디원 코드

     - 종이를 자를지 말지 결정한다.

    - 재귀함수 인덱스 두 가지를 넘긴다.

 

    - 두 번째 방법: cut2()

      -> gap은 간격의 길이 

      -> boolean cutFlag: 잘라야 하는지 판단한다.

<hide/>
rrays;

public class Practice094 {
    static int[][] arr;
    static int blueCnt, whiteCnt, gap;
    static boolean cutFlag;
    // cut 풀이에 추가로 필요한 변수
    static int[] leftUpIdx, rightDownIdx;
    // cut2 풀이에 추가로 필요한 변수
    static int x, y;



    public static void solution(int gap) {
//        cut(new int[]{0,0}, new int[]{gap - 1, gap - 1}, gap - 1);
        cut2(0, 0, gap);
        System.out.println(whiteCnt);
        System.out.println(blueCnt);
    }

    public static void cut(int[] leftUpIdx, int[] rightDownIdx, int gap) {
        cutFlag = false; // 초기화
        // 1칸짜리 종이임
        if(Arrays.equals(leftUpIdx, rightDownIdx)) {
            if(arr[leftUpIdx[0]][leftUpIdx[1]] == 1) {
                blueCnt++;
            } else {
                whiteCnt++;
            }
            return;
        }
        // 다른 숫자가 있으면 잘라
        for (int i = 0; i <= gap; i++) {
            for (int j = 1; j <= gap; j++) {
                if(arr[leftUpIdx[0] + i][leftUpIdx[1]] != arr[leftUpIdx[0] + i][leftUpIdx[1] + j]) {
                    cutFlag = true;
                    break;
                }
            }
            if(i < gap && arr[leftUpIdx[0] + i][leftUpIdx[1] + gap] != arr[leftUpIdx[0] + i + 1][leftUpIdx[1]]) {
                cutFlag = true;
                break;
            }
            if(cutFlag) {
                break;
            }
        }
        // 잘라야 하면
        if(cutFlag == true) {
            gap = (rightDownIdx[0] - leftUpIdx[0]) / 2; // gap은 종이의 가로&세로 사이즈
            int next = gap + 1; // next는 다음 종이까지의 인덱스 차이
            cut(new int[]{leftUpIdx[0], leftUpIdx[1]}, new int[]{leftUpIdx[0] + gap, leftUpIdx[1] + gap}, gap); // 왼쪽 위
            cut(new int[]{leftUpIdx[0], leftUpIdx[1] + next}, new int[]{rightDownIdx[0] - next, rightDownIdx[1]}, gap); // 오른쪽 위
            cut(new int[]{leftUpIdx[0] + next, leftUpIdx[1]}, new int[]{rightDownIdx[0], rightDownIdx[1] - next}, gap); // 왼쪽 아래
            cut(new int[]{rightDownIdx[0] - gap, rightDownIdx[1] - gap}, new int[]{rightDownIdx[0], rightDownIdx[1]}, gap); // 오른쪽 아래
        } else {
            if(arr[leftUpIdx[0]][leftUpIdx[1]] == 1) {
                blueCnt++;
                return;
            } else {
                whiteCnt++;
                return;
            }
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        gap = Integer.parseInt(br.readLine());
        arr = new int[gap][gap];

        for (int i = 0; i < gap; i++) {
            String[] s = br.readLine().split(" ");
            for (int j = 0; j < gap; j++) {
                arr[i][j] = Integer.parseInt(s[j]);
            }
        }
        solution(gap);
    }

    // 다른 풀이
    public static void cut2(int x, int y, int gap) {
        if(gap == 1) { // 1장짜리 종이면
            if(arr[x][y] == 1) {
                blueCnt++;
            } else {
                whiteCnt++;
            }
            return;
        }
        // 잘라야 하는지 확인
        for (int i = x; i < x + gap; i++) {
            for (int j = y; j < y + gap; j++) {
                if(arr[x][y] != arr[i][j]) {
                    cutFlag = true;
                    break;
                }
            }
            if(cutFlag) {
                break;
            }
        }
        // 잘라야 하면
        if(cutFlag) {
            cutFlag = false;
            // 재귀호출
           cut2(x, y, gap/2); // 왼쪽 위
           cut2(x, y + (gap/2), gap/2); // 오른쪽 위
           cut2(x + (gap/2), y, gap/2); // 왼쪽 아래
           cut2(x + (gap/2), y + (gap/2), gap/2); // 오른쪽 아래
        } else {
            if(arr[x][y] == 1) {
                blueCnt++;
            } else {
                whiteCnt++;
            }
        }
    }
}

 

  Note) 입출력 예시

<hide/>
4
1 1 0 0 
1 1 0 0 
0 0 1 1
0 0 1 1
2
2
4
1 1 1 1 
1 1 1 1 
1 1 1 1 
1 1 1 1
0
1
4
1 0 1 0 
1 0 1 0
0 1 0 1
0 1 0 1
8
8
4
1 1 0 0
0 0 1 1
1 1 0 0
0 0 1 1
8
8
4
1 0 1 0
0 1 0 1
1 0 1 0
0 1 0 1
8
8
4
1 0 1 0
0 0 0 0
0 1 0 1
1 1 1 1
8
8
8
1 1 0 0 0 0 1 1
1 0 1 0 0 0 1 1
0 0 0 0 1 1 0 0
0 0 0 0 1 1 0 0
1 0 0 0 1 1 1 1
0 1 0 0 1 1 1 1
0 0 1 1 1 1 0 1
0 0 1 1 1 1 1 1
13
15
4
0 0 1 0
0 0 0 0
1 0 0 0
1 1 1 1
7
6

 

 

 

2.  순간 이동 - 프로그래머스

출처: https://school.programmers.co.kr/learn/courses/30/lessons/12980

프로그래머스

 

  Sol) 스터디원 코드 -  0.0xx ms 

<hide/>
import java.util.*;
public class Solution {
    public static int solution(int n) {
        /*int ans = 0;
        while(n > 0){
            if(n%2 == 0){
                n = n/2;
            }
            else{
                n = n - 1;
                ans++;
            }
        }
        return ans;*/
        return Integer.bitCount(n);
    }

    public static void main(String[] args) {
        System.out.println(solution(15));
    }
}

    - n -> 0으로 가는 방법을 생각한다.

      -> 처음 문제를 풀면서 이 생각을 잠깐 하기는 했는데 왠지(?) 아닐 것 같다는 느낌에 시도하지 않았다.

      -> 그런데 이렇게 간단하게 풀리는 걸 보니까 스치는 아이디어라도 도전해봐야겠다는 생각이 들었다.

    - n이 짝수인 경우는 2로 나누고 홀수인 경우는 n = n - 1해서 n = 0이 된 경우의 answer를 반환하도록한다.

    - 그런데, 한 줄 짜리 코드가 있다는 건 정말 놀라웠다.

     -> Integer클래스의 bitCount() 메서드(이진수로 나타냈을 때 1의 개수)를 이용하면 정답을 바로 반환할 수 있다. 

    - 이 문제와 다르게 뒤로도 갈 수 있는 경우가 포함된 문제는 그리디로 푼다.

 

 

3.  스도쿠 -  Amazon 기출

출처:  https://leetcode.com/problems/sudoku-solver/

Sudoku Solver - LeetCode

  Sol) 스터디원 코드

<hide/>
class Solution1 {
    public void solveSudoku(char[][] board) {
        helper(board,0,0); // 좌표
        for(char[] c : board){
            System.out.println(Arrays.toString(c));
        }
    }
    public boolean helper(char[][] board, int row,int col){
        if(col == 9){ //한줄끝나서 다음줄로 넘겨주는 조건
            return helper(board,row+1,0);
        }
        if(row == 9){
            return true; //우리가 찾을 케이스 단하나.
        }
        if(board[row][col] == '.'){
            for (int i = 1; i <= 9; i++) {
                if(validateCheck(board,row,col,i)){
                    board[row][col] = (char)(i+'0');
//                    return helper(board,row,col+1);
                    if(helper(board,row,col+1)){
                        return true;
//                    }
                }
            }
            board[row][col] = '.';
            //위에서 함수 가 다음으로 나아기자못하고 아래로 내려온다면 ? 다시 원복 시키고 false 를 리턴해
            // 현재 진행중인 재귀를 종료시켜줍니다.
            return false;
        }else{
            return helper(board,row,col+1);
        }
    }
    public boolean validateCheck(char[][] board,int row,int col,int target){
        char tg = (char)(target+'0');
        //Col check
        for (int i = 0; i < 9; i++) {
            if(board[i][col] == tg) return false;
        }
        //Row check
        for (int i = 0; i < 9; i++) {
            if(board[row][i] == tg) return false;
        }
        //Subbox check
        int nRow = row/3*3;
        int nCol = col/3*3;
        for (int i = nRow; i < nRow+3; i++) {
            for (int j = nCol; j < nCol+3; j++) {
                if(board[i][j] == tg) return false;
            }
        }
        return true;
    }
}
//Coordinate Intermediate
class Solution2 {
    public void solveSudoku(char[][] board) {
        helper(board,0);
        for(char[] c : board){
            System.out.println(Arrays.toString(c));
        }
    }
    public boolean helper(char[][] board,int n){
        if(n == 81)return true; // 왜 끝났으니깐 9*9 ? 81 우리는 0부터 출발합니다.
        int row = n/9,col = n%9; // 로우칼럼 계산하기 항상 칼럼으로 나누고 나머지 연산 해주면 로우칼럼 나오는 트릭.
        if(board[row][col]!= '.') return helper(board,n+1);  // 비어있지 않기 떄문에 넘겨줍니다.

        for (int i = 1; i <= 9; i++) { //어떤 숫자가 검증이 된지 모르기 떄문에 for 를돌려줍니다. 1번부터 가던 9번부터 가던 어쩃든 모든 숫자 돌면됩니다.
            if(validateCheck(board,row,col,i)){ // 검증 된 숫자라면 진행 시켜 줍니다.
                board[row][col] = (char) (i + '0');
                if(helper(board,n+1)){
                    //false 가 경우 단하나. helper 함수가 끝까지 내려가는경우
                    // 즉 어는 숫자도 검증되지 못해 여기서 다음 재귀로 넘어가지 를 못해 아래로 내려가는 경우
                    return true;
                }
            }
        }
        board[row][col] = '.'; // 저 위에서 다음 재귀로 못넘어간 나머지 가치 가 없으니 원복시키고 함수를 종료 합니다.
        return false;
    }
    public boolean validateCheck(char[][] board,int row,int col,int target){
        char tg = (char)(target+'0');
        //row check && col check;
        for (int i = 0; i < 9; i++) {
            if(board[row][i] == tg || board[i][col] == tg){
                return false;
            }
        }
        //3*3 chcck;
        int nRow = row/3*3;
        int nCol = col/3*3;
        for (int i = nRow; i < nRow+3; i++) {
            for (int j = nCol; j < nCol+3; j++) {
                if(board[i][j] == tg) return false;
            }
        }
        return true;
    }
}
//Coordinate Master 10.9k view Solution
class Solution3 {
    public void solveSudoku(char[][] board) {
        dfs(board,0);
    }
    private boolean dfs(char[][] board, int d) {
        if (d==81) return true; //found solution
        int i=d/9, j=d%9;
        if (board[i][j]!='.') return dfs(board,d+1);//prefill number skip

        boolean[] flag=new boolean[10];
        validate(board,i,j,flag);
        for (int k=1; k<=9; k++) {
            if (flag[k]) {
                board[i][j]=(char)('0'+k);
                if (dfs(board,d+1)) return true;
            }
        }
        board[i][j]='.'; //if can not solve, in the wrong path, change back to '.' and out
        return false;
    }
    private void validate(char[][] board, int i, int j, boolean[] flag) {
        Arrays.fill(flag,true);
        for (int k=0; k<9; k++) {
            if (board[i][k]!='.') flag[board[i][k]-'0']=false;
            if (board[k][j]!='.') flag[board[k][j]-'0']=false;
            int r=i/3*3+k/3;
            int c=j/3*3+k%3;
            if (board[r][c]!='.') flag[board[r][c]-'0']=false;
        }
    }
}

  - 한 칸씩 DFS를 돌린다.

  - 전에 백준에서 스도쿠를 가져왔던 분께서 유형이 조금 다른 문제를 가져왔다.

  - 코드가 길기는 하지만 복습을 제대로 해야겠다.

 

 

4. 222폴링 - 실버 2

출처:  https://www.acmicpc.net/problem/17829

17829번: 222-풀링

 

 Sol) 스터디원 코드 - 900ms

<hide/>
package backjoon17829;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Collections;
import java.util.PriorityQueue;

public class Main {

    static int N;
    static int[][] matrix;
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        N = Integer.parseInt(br.readLine());

        // 입력받은 수로 N * N 행렬 만드는 부분
        matrix = new int[N][N];
        for (int i = 0; i < N; i++) {
            String[] s = br.readLine().split(" ");
            for (int j = 0; j < N; j++) {
                matrix[i][j] = Integer.parseInt(s[j]);
            }
        }

        int size = N;
        while (size > 1) { // N * N 행렬의 가로 세로가 1보다 클 때 까지 반복

            // 현재 행렬 가로(세로)길이를 2로 나눈 값을 제곱하면 다음 N * N 행렬을 만드는 데 필요한 수를 저장할 수 있는 1차원 배열의 사이즈를 알 수 있음
            // 예를 들어 현재 N * N 행렬의 가로(세로)길이가 8이면 (8 / 2)^2 = 16 -> 4 * 4의 행렬을 만들 수 있음
            // 그리고 고정된 2 * 2 크기의 행렬 안에서 두 번째 큰 수를 구해야 하므로 i, j를 +2 씩 증가 시키면서 반복, small_matrix에 저장
            int[] small_matrix = new int[(int) Math.pow(size / 2, 2)];
            int idx = 0;
            for (int i = 0; i < size; i += 2) {
                for (int j = 0; j < size; j += 2) {
                    small_matrix[idx++] = getNum(i, j);
                }
            }

            // N * N 행렬을 전체 탐색 후 크기를 반으로 줄임
            // 4 * 4 행렬로 예를 들면 small_matrix의 길이는 16이고 i = 0 ~ 15까지 반복하면서
            // row = 0 / 4 = 0, col = 0 % 4 = 0
            // row = 1 / 4 = 0, col = 0 % 4 = 1
            // row = 2 / 4 = 0, col = 0 % 4 = 2
            // row = 3 / 4 = 0, col = 0 % 4 = 3
            // row = 4 / 4 = 1, col = 4 % 4 = 0
            // row = 5 / 4 = 1, col = 5 % 4 = 1
            // row = 6 / 4 = 1, col = 6 % 4 = 2
            // row = 7 / 4 = 1, col = 7 % 4 = 3
            // 이런식으로 4 * 4 행렬의 값을 채워줄 수 있음
            matrix = new int[size / 2][size / 2];
            for (int i = 0; i < small_matrix.length; i++) {
                int row = i / (size / 2);
                int col = i % (size / 2);
                matrix[row][col] = small_matrix[i];
            }

            // matrix에 새로운 값을 넣어준 후 size를 줄여줌
            size /= 2;
        }

        // 맨 마지막에 남은 값 출력
        System.out.println(matrix[0][0]);
    }

    public static int getNum(int row_start, int col_start) {
        // 두 번째 큰 수를 뽑기위한 내림차순 우선순위 큐
        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(Collections.reverseOrder());
        for (int i = row_start; i < row_start + 2; i++) {
            for (int j = col_start; j < col_start + 2; j++) {
                priorityQueue.offer(matrix[i][j]);
            }
        }

        priorityQueue.poll();
        return priorityQueue.poll();
    }
}

    - 우선순위 큐를 이용하면 두번째로 큰 수를 뽑는게 수월해진다. 메서드 getNum()

      -> 우선순위 큐로 내림차순 정렬하여 두 번 poll()하면 두 번째로 큰 값이 나온다. 

    - while문을 실행할 때 새로운 1차원 배열 선언, smallMat[] 를 2차원 배열이 아닌 1차원 배열로 둔다.

      -> board가 8 * 8행렬이면 네 칸 짜리 서브 배열이 64 / 4 = 16개 만들어진다. (while문 마지막에 board의 크기를 바꿔서 다시 선언하고 smallMat값을 각각 대입)

      -> 그러면 16개의 구역에 대한 두 번째 작은 값을 각각 뽑아서  smallMat[idx++] = getNum(i, j) 에 저장한다.

      -> 2차원 배열의 각 구역에서 두번째 작은 값을 => 1차원 배열에 각각 저장하고  => 2차원 배열에 다시 저장

      -> 이 부분이 참신하다고 느꼈다. 비슷한 유형이 나오면 꼭 활용해야겠다.

    - for(int i = 0;i < smallMat; ++i){} :

      -> i  / (size / 2) => 새로운 배열의 row,  

      -> i  % (size / 2) => 새로운 배열의 col, 

      -> board[row][col] = smallMat[i];가 된다. 

    - for문에 i나 j가 단항 연산자로 쓰이지 않고 +2 할 수도 있다. (당연한 부분인데 코드가 낯설었다.)

 

  MySol)  스터디원 코드 수정

<hide/>
import java.util.*;


// 풀링

public class Test5 {

    static int[][] board;
    static int N;

    public static int getNum(int _rowStart, int _colStart){

        PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());

        for(int i = _rowStart; i < _rowStart + 2; ++i){
            for(int j = _colStart;j < _colStart + 2; ++j){
                pq.offer(board[i][j]);
            }
        }
        pq.poll();
        return pq.poll();
    }

    public static void main(String[] args){

        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        board = new int[n][n];

        for(int i = 0; i < n; ++i){
            for(int j = 0; j < n; ++j){
                board[i][j] = scanner.nextInt();
            }
        }
        int size = n;
        while(size > 1){
            int[] smallMat = new int[(int) Math.pow(size / 2, 2)];  // (n / 2) * (n / 2) => 1차원 배열로 선언

            int idx = 0;
            for(int i = 0; i < size; i += 2){   // 행과 열을 모두 두 칸씩 이동
                for(int j = 0;j < size; j += 2){    //
                    smallMat[idx++] = getNum(i, j); // 두번째로 큰값을 넣는다.
                }
            }

            board = new int[size / 2][size / 2];

            for(int i = 0;i < smallMat.length; ++i){
                int row = i / (size / 2);
                int col= i % (size / 2);
                board[row][col] = smallMat[i];
            }
            size /= 2;
        }
        System.out.println(board[0][0]);
    }
}

  Note) 입출력 예시

<hide/>
[입력]
8
-1 2 14 7 4 -5 8 9
10 6 23 2 -1 -1 7 11
9 3 5 -2 4 4 6 6
7 15 0 8 21 20 6 6
19 8 12 -8 4 5 2 9
1 2 3 4 5 6 7 8
9 10 11 12 13 14 15 16
17 18 19 20 21 22 23 24

[출력]
17


[입력]
4
-6 -8 7 -4
-5 -5 14 11
11 11 -1 -1
4 9 -2 -4

[출력]
11

 

 

5. H-index

출처: https://school.programmers.co.kr/learn/courses/30/lessons/42747

프로그래머스

 

  Sol 1) 내가 가져간 문제

<hide/>

import java.util.*;

// 프로그래머스 lv 2 H-idx
//
public class Test1 {

    public static int solution(int[] citations) {

        int answer = 0;
        Arrays.sort(citations); //  arr2 = [0 1 3 5 6 7 9]
        System.out.println();
        System.out.println(Arrays.toString(citations));

        for(int i = 0; i < citations.length; ++i){
        // 0번 이상 인용된 논문: 7개, 1번 이상: 6개, 3번 이상: 5개, 5번 이상: 4개, 6번 이상 3개, ...

            int H = citations.length - i;   // H: i번째 논문만큼 많이 인용된 논문의 개수
            if( citations[i] >=  H){
                System.out.printf("citation[%d] = %d >= %d %n", i, citations[i], H);
                return H;
            }
        }
        return  0;
    }

    public static void main(String[] args){

        int[] arr1 = {3, 0, 6, 1, 5};
        int[] arr2 = {0, 1, 3, 5, 6, 7, 9};     // 정렬 후: 0 1 3 5 6 7 9
        int[] arr3 = {3, 0, 6, 1, 5, 2, 4, 7, 8};   // 0 1 2 3 4 5 6 7 8
        int[] arr4 = {3, 0, 6, 1, 5, 2, 4, 7, 8, 10, 11, 12, 13};   // 0 1 2 3 4 5 6 7 8 10 11 12 13
        int[] arr5 = {0, 1, 3, 5, 6, 7, 9}; //

        System.out.println(solution(arr1)); // 3
        System.out.println(solution(arr2)); // 4
        System.out.println(solution(arr3)); // 4
        System.out.println(solution(arr4)); // 6
        System.out.println(solution(arr5)); // 4
    }
}

    - 문제의 입출력 예시가 하나 밖에 없고 문제 설명이 모호해서 푸는데 좀 오래 걸렸다.

    - 반환해야 하는 부분이 arr[i]보다 큰 배열의 원소의 개수보다 arr[i] 크거나 같은 부분의 개수이다.

      -> 정렬해서 length - i를 하면 arr[i]보다 크거나 같은 원소들의 개수가 나온다.

    - 뒤에서부터 카운트하는 방법으로 다시 작성하면 그게 더 쉬울 것 같다. (아래에 코드를 짰는데 테스트 하나가 오답이다.)

    - 전에 공부했던 문제지만 확실히 이해하지 못해서 공부하려고 가져간 문제이다.

    - 내가 가져가서 스터디원 분들한테 설명했는데 다들 어렵다고 하셨다. 다음부터는 그림을 미리 그려가거나 준비해서 다같이 이해할 수 있도록 스터디 준비를 해야겠다.

 

 

  Sol 2)

<hide/>
import java.util.*;

// 프로그래머스 lv 2 H-idx
//
public class Test1 {

    public static int solution(int[] citations) {

        int answer = 0;
        Arrays.sort(citations); //  arr2 = [0 1 3 5 6 7 9]
        System.out.println();
        System.out.println(Arrays.toString(citations));

        for(int i = citations.length - 1; i >= 0; --i) {
            int H = citations.length - i; // 크거나 같은 것들의 개수

            if (H == citations[i]){
                return H;
            }else if(H > citations[i]) {
                return H - 1;
            }
            if(i == 0){
                return H;
            }
        }
        return  0;
    }

    public static void main(String[] args){

        int[] arr1 = {3, 0, 6, 1, 5};
        int[] arr2 = {0, 1, 3, 5, 6, 7, 9};     // 정렬 후: 0 1 3 5 6 7 9
        int[] arr3 = {3, 0, 6, 1, 5, 2, 4, 7, 8};   // 0 1 2 3 4 5 6 7 8
        int[] arr4 = {3, 0, 6, 1, 5, 2, 4, 7, 8, 10, 11, 12, 13};   // 0 1 2 3 4 5 6 7 8 10 11 12 13
        int[] arr5 = {0, 1, 3, 5, 6, 7, 9}; //
        int[] arr6 = {1, 3, 4, 2, 6, 7,8, 10, 13, 14, 8, 12}; //
        int[] arr7 = {1, 2, 3, 16, 17,  18, 19,  20, 21, 22,  23, 8000, 9000, 9500, 10000}; //

        int[] arr8 = {3, 0, 6, 1, 5}; //
        int[] arr9 = {20, 19, 18, 1}; //
        int[] arr10 = {22, 42}; //
        int[] arr11 = {5, 5, 5, 5}; //


        System.out.println(solution(arr1)); // 3
        System.out.println(solution(arr2)); // 4
        System.out.println(solution(arr3)); // 4
        System.out.println(solution(arr4)); // 6
        System.out.println(solution(arr5)); // 4
        System.out.println(solution(arr6)); // 7
        System.out.println(solution(arr7)); // 12

        System.out.println(solution(arr8)); // 3
        System.out.println(solution(arr9)); // 3
        System.out.println(solution(arr10)); // 2
        System.out.println(solution(arr11)); // 4

    }
}

  - 이렇게 하면 테스트 케이스 하나를 통과하지 못한다.

    - 처음에 위 사진처럼 통과하지 못했는데 solution 반환이 for문 안에서 끝날 수 있도록, i = 0일 때 H를 반환하도록 if문을 짜니까 통과했다.

    - 다른 블로그를 보면서 테스트 케이스를 추가해보니까 for문에서 가능한 i 끝까지 돌고났을 때의 경우를 생각하지 못하고  0을 반환하도록 짠 것이 화근이었다.

    - 엣지 케이스를 모두 고려해서 작성해야겠다.

    - 참고로 메서드의 맨 마지막 부분인 return 0까지는 실행되지 않는다.