[코딩테스트] LeetCode 75 level 2 Day1. Implementation

Implementation / Simulation

오늘은 LeetCode 75 level 2 Day1. Implementation / Simulation 문제들을 풀었다. 

easy 문제는 간단했는데 medium 2문제는 생각보다 어려워서 몇 시간을 붙잡고 있었다. 30분 ~ 1시간 이상이 걸리는 문제는 풀이를 보고 개념을 이해한 다음에 다시 풀어보자 항상 다짐하지만 쫌만 더 생각하면 풀릴 것 같아서 자꾸 붙잡고 있게 된다. 반성하자.

 

많은 고민의 흔적들..

문제 풀이

구현 문제를 처음 접한 느낌은 확률 문제를 처음 봤을때 느낌처럼 그림도 그려보고 아이디어를 잘 떠올려서(?) 나름의 규칙성을 발견한 다음에 그 아이디어를 구현시켜야 하는 줄 알았다. 그 결과 몇 시간이나 버린..

LeetCode 75 Level 2 Day 1 Implementation/Simulation 문제

202. Happy Number

Write an algorithm to determine if a number n is happy. A happy number is a number defined by the following process: Starting with any positive integer, replace the number by the sum of the squares of its digits. Repeat the process until the number equals 1 (where it will stay), or it loops endlessly in a cycle which does not include 1. Those numbers for which this process ends in 1 are happy. Return true if n is a happy number, and false if not.

문제는 주어진 숫자의 각 자릿수를 제곱한 숫자의 합의 각 자릿수를 제곱..하기를 반복하다가 마지막으로 1이 나오면 true를 반환하는 문제이다. 

샘플 입・출력

// Sample 01
Input: n = 19
Output: true

Explanation:
12 + 92 = 82
82 + 22 = 68
62 + 82 = 100
12 + 02 + 02 = 1

// Sample 02
Input: n = 2
Output: false

사고 과정

문제를 풀 때 사고 과정은 아래와 같았다.

1. 각 자릿수를 구한다
2. 해당 자릿수를 제곱하고 누적해서 합을 구한다
3. 결과 값이 1인지 체크하고 아니라면 다시 1, 2 과정을 반복한다.
4. 결과 값이 1이라면 true를 반환한다.
5. 근데 언제 끝내지? -> 이 부분이 떠오르지 않아 인터넷의 힘을 빌렸다.
   종료 조건 : 결과 숫자들을 전부 저장하고 있다가 한 번 나왔던 결과가 다시 나오면 1이 될 수 없는 숫자이므로 반복문을 종료하고 false를 반환한다.

package leetcode.implementation;

import java.util.HashSet;
import java.util.Set;

public class No_202 {
    public static void main(String[] args) {
        System.out.println(isHappy(19));
        System.out.println(isHappy(2));
    }

    public static boolean isHappy(int n) {
        Set<Integer> alreadyExistNumber = new HashSet<>();
        while (!alreadyExistNumber.contains(n)) {
            alreadyExistNumber.add(n);

            int length = Integer.toString(n).length();
            if ((n = getSquareNumber(length, n)) == 1)
                return true;
        }
        return false;
    }

    public static int getSquareNumber(int length, int number) {
        int squareNumber = 0;

        for (int i = 1; i <= length; i++) {
            int digit = (int) ((number % Math.pow(10, i))/ Math.pow(10, i - 1));
            squareNumber += Math.pow(digit, 2);
        }

        return squareNumber;
    }
}

 

54. Spiral Matrix

Given an m x n matrix, return all elements of the matrix in spiral order.

주어진 m*n 행렬을 회오리 모양으로 출력해주면 되는 문제이다. 

샘플 입・출력

Spiral Matrix

// Sample 01
Input: matrix = [[1,2,3],[4,5,6],[7,8,9]]
Output: [1,2,3,6,9,8,7,4,5]

// Sample 02
Input: matrix = [[1,2,3,4],[5,6,7,8],[9,10,11,12]]
Output: [1,2,3,4,8,12,11,10,9,5,6,7]

사고 과정

 

1. 행 -> 열 -> 행 -> 열을 반복하며 데이터를 리스트에 저장하고 중복 데이터는 저장되지 않게 하면 되지 않을까?
2. 행 데이터를 추가할 땐 행 데이터를 고정시키고 열만 i로 달라지게 하면 되고, 열 데이터를 추가할 땐 열 데이터를 고정시키고 행만 i로 달라지게 하면 되겠다.
3. i는 근데 어떻게 값을 바꿔줘야 하지.. 고정시킬 행과 열의 값은 어떻게 바꿔주지..-> 계속 고민하다가 인터넷의 힘을 빌렸다. 로직을 잘 설명해주는 영상이 있어 공유한다.
4. 문제의 핵심은 상,하,좌,우의 기준점과 화살표가 이동할 수 있는 방향을 정의해주는 것이었다.

import java.util.ArrayList;
import java.util.List;

public class No_54 {
    public static void main(String[] args) {
        System.out.println(spiralOrder(new int[][]{{1,2,3},{4,5,6},{7,8,9}}));
        System.out.println(spiralOrder(new int[][]{{1,2,3,4},{5,6,7,8},{9,10,11,12}}));
    }

    public static List<Integer> spiralOrder(int[][] matrix) {
        List<Integer> answer = new ArrayList<>();

        // 기준점
        int top = 0; int down = matrix.length - 1;
        int left = 0; int right = matrix[0].length - 1;

        // 방향 0: →, 1: ↓, 2: ←, 3: ↑
        int direction = 0;

        // 상하좌우 기준점이 만날때까지 반복
        while (top <= down && left <= right) {
            if (direction == 0) {
                for (int i = left; i <= right; i++)
                    answer.add(matrix[top][i]);
                top++;
            } else if (direction == 1) {
                for (int i = top; i <= down; i++)
                    answer.add(matrix[i][right]);
                right--;
            } else if (direction == 2) {
                for (int i = right; i >= left; i--)
                    answer.add(matrix[down][i]);
                down--;
            } else if (direction == 3) {
                for (int i = down; i >= top; i--)
                    answer.add(matrix[i][left]);
                left++;
            }
            direction = (direction + 1) % 4;
        }

        return answer;
    }
}

1706. Where Will the Ball Fall

You have a 2-D grid of size m x n representing a box, and you have n balls. The box is open on the top and bottom sides. Each cell in the box has a diagonal board spanning two corners of the cell that can redirect a ball to the right or to the left. A board that redirects the ball to the right spans the top-left corner to the bottom-right corner and is represented in the grid as 1. A board that redirects the ball to the left spans the top-right corner to the bottom-left corner and is represented in the grid as -1. We drop one ball at the top of each column of the box. Each ball can get stuck in the box or fall out of the bottom. A ball gets stuck if it hits a "V" shaped pattern between two boards or if a board redirects the ball into either wall of the box. Return an array answer of size n where answer[i] is the column that the ball falls out of at the bottom after dropping the ball from the ith column at the top, or -1 if the ball gets stuck in the box.

주어진 1과 -1로 이루어진 행렬에서 1은 공의 궤적이 오른쪽으로 -1은 공의 궤적이 왼쪽으로 이동하는 것을 의미할 때 공이 모두 이동한 후의 각 공의 위치를 반환하는 문제이다.

샘플 입・출력

Where Will the Ball Fall

// Sample 1
Input: grid = [[1,1,1,-1,-1],[1,1,1,-1,-1],[-1,-1,-1,1,1],[1,1,1,1,-1],[-1,-1,-1,-1,-1]]
Output: [1,-1,-1,-1,-1]

// Sample 2
Input: grid = [[-1]]
Output: [-1]

// Sample 3
Input: grid = [[1,1,1,1,1,1],[-1,-1,-1,-1,-1,-1],[1,1,1,1,1,1],[-1,-1,-1,-1,-1,-1]]
Output: [0,1,2,3,4,-1]

사고 과정

1. 공이 아래로 흘러갈 때 1과 -1이 연속으로 나오면 길이 막힌다.
2. 공의 위치가 0보다 작아지면 길이 막힌 것이다.
3. 공의 위치가 열 크기보다 커지면 길이 막힌 것이다.
4. 코드를 구현하는데 1,2,3의 예외 상황이 나와서 계속 고민하다가 인터넷의 힘을 빌렸다. 
   1. 나는 이중 for 문을 사용해서 각 행을 지난 공의 위치를 구하고 다음 행으로 넘어가는 방식으로 문제를 풀려고 했다. (grid의 입장)
   2. 찾아본 대부분의 문제 풀이는 단일 for문 사용해서 공 하나 하나의 위치를 구하는 방식으로 문제를 접근하고 있었다. (공의 입장)
   3. 즉, 공의 입장에서 현재 궤적이 오른쪽이었을 때 다음 궤적도 같은 방향이어야 막히지 않고 내려간다는 개념을 이용한 풀이였다.
      (\  \) or  (/  /)

import java.util.Arrays;

public class No_1706 {
    public static void main(String[] args) {
        System.out.println(
                Arrays.toString(
                        findBall(new int[][]{
                                {1, 1, 1, -1, -1},
                                {1, 1, 1, -1, -1},
                                {-1, -1, -1, 1, 1},
                                {1, 1, 1, 1, -1},
                                {-1, -1, -1, -1, -1}
                        })
                ));
        System.out.println(
                Arrays.toString(
                        findBall(new int[][]{
                                {1,1,1,1,1,1},
                                {-1,-1,-1,-1,-1,-1},
                                {1,1,1,1,1,1},
                                {-1,-1,-1,-1,-1,-1}
                        })
                ));
        System.out.println(
                Arrays.toString(
                        findBall(new int[][]{
                                {1,1,1,1,1},
                                {-1,-1,-1,1,1},
                                {-1,-1,1,-1,1},
                                {1,1,-1,1,-1}
                        })
                ));

        System.out.println(
                Arrays.toString(
                        findBall(new int[][]{
                                {-1,1,-1,-1,-1,-1,-1,-1,1,-1, -1,-1,-1,1,1,-1,-1,-1,1,1}
                        })
                ));

        System.out.println(
                Arrays.toString(
                        findBall(new int[][]{
                                {1,-1,-1,1,-1,1,1,1,1,1,-1,1,1,1,1,1,1,-1,-1,-1,-1,-1,-1,1,-1,1,-1,1,-1,-1,-1,-1,1,-1,1,1,-1,-1,-1,-1,-1,1},
                                {-1,1,1,1,-1,-1,-1,-1,1,1,1,-1,-1,-1,1,-1,-1,1,1,1,1,1,1,-1,1,-1,-1,-1,-1,-1,1,-1,1,-1,-1,-1,-1,1,1,-1,1,1},
                                {1,-1,-1,-1,-1,1,-1,1,1,1,1,1,1,1,-1,1,-1,-1,-1,1,-1,-1,1,-1,1,-1,1,-1,-1,1,-1,1,-1,1,1,-1,-1,1,1,-1,1,-1}
                        })
                ));
    }

    public static int[] findBall(int[][] grid) {
        int colSize = grid[0].length;

        int[] ballPosition = new int[colSize];

        for (int col = 0; col < colSize; col++) {
            ballPosition[col] = findPosition(grid, 0, col);
        }

        return ballPosition;
    }

    /**
     * dfs 방식(?)
     * */
    public static int findPosition(int[][] grid, int row, int col) {
        if (row == grid.length) return col;
        if (checkPosition(grid.length, grid[0].length, row, col)) {
            if (grid[row][col] == 1) { // 오른쪽으로 흐르는 궤적인 경우
                if (checkPosition(grid.length, grid[0].length, row, col+1)
                        && grid[row][col+1] == 1)
                    return findPosition(grid, row+1, col+1); // 다음 궤적도 오른쪽이어야 아래로 흐른다.
            } else { // 왼쪽으로 흐르는 궤적
                if (checkPosition(grid.length, grid[0].length, row, col-1)
                        && grid[row][col-1] == -1)
                    return findPosition(grid, row+1, col-1); // 다음 궤적도 왼쪽이어야 아래로 흐른다.
            }
        }
        return -1;
    }

    /**
     * 공의 위치가 그리드의 크기를 넘지 않는지 체크
     * */
    public static boolean checkPosition(int rowSize, int colSize, int row, int col) {
        return rowSize > row && colSize > col && col >= 0 && row >= 0;
    }

후기 ・ 배운 점

• 한 문제를 2~3시간 이상 고민하는 것은 지금 나에게 도움이 되지 않는 것 같다. 1시간 이상 문제를 붙잡고 있지 말고 바로 문제의 접근 방식을 찾아보자.
• 다만, 코드를 보는 것보다 문제를 푸는 과정을 확인하고 코드는 직접 구현해보는 식으로 공부하자.
• 구현 문제에서 행렬이 주어지고 풀이하는 문제의 경우에는 기준점과 이동하는 방향을 정의하는 것이 사고의 첫순위인 것 같다.