리트코드 - 55. Jump Game

리트코드 -  55. Jump Game

출처 - https://leetcode.com/problems/jump-game/?envType=study-plan-v2&envId=top-interview-150

 

문제 설명

주어진 정수 배열 nums는 각 위치에서의 최대 점프 길이를 나타냅니다.

처음에는 배열의 첫 번째 인덱스에 위치해 있으며, 배열의 각 요소는 해당 위치에서의 최대 점프 길이를 나타냅니다.

마지막 인덱스에 도달할 수 있는 경우 true를 반환하고, 그렇지 않은 경우 false를 반환하세요.

 

의사코드

nums배열의 마지막을 도착지점으로 설정 반복문 시작[nums를 뒤에서부터 순회]     만일 인덱스+숫자가 도착지점보다 크면        새로운 도착 지점으로 설정     만일 도착 지점이 0이면        true를 반환     아닌 경우에는 false 반환 반복문 종료

풀이코드

class Solution {
    public boolean canJump(int[] nums) {
        int reach = nums.length - 1;

        for (int i = reach; i >= 0; i--) {
            if (i + nums[i] >= reach) {
                reach = i;
            }

            if (reach == 0) {
                return true;
            }    
        }
        return false;
    }
}

코드설명

배열의 마지막 인덱스에 도착하면 true를 반환하는 문제다.

마지막 인덱스를 먼저 reach로 도달 지점으로 정해놓고, 배열을 역으로 순회한다.

 

reach인 마지막 인덱스부터 값을 확인하여 i 값과 nums[i] 값을 더하여 reach보다 크면 해당 i를 reach로 갱신한다.

반복하여 갱신된 reach 값에 도달하는 값이 있으면 그 값의 i를 reach로 갱신하는데,

최종적으로 i != 0이면 갱신된 reach값에 도달하는 값이 없고 중간에 끊긴 것이다.

 

즉, 도달 지점을 계속 갱신하면서 최종적으로 첫번째 인덱스까지 도착하느냐를 묻는 문제이다.

 

시간복잡도 - O(n) (그리디 알고리즘)

공간복잡도 - O(1)

문제를 풀며 생각한 흐름과 배운 점

이 문제를 이해하는데 상당히 난해했다.

처음에는 단순하게 배열 값중에 0이 있으면 값이 끊겼다고 생각했는데, 그 앞에 수가 0을 뛰어넘으면 해결됐기 때문에 엄청나게 조건이 많이 달린 스파게티 코드가 되었다.

 

너무 해결이 안되어서 사실 이 문제는 다른 사람의 코드를 봤다. 푸는 방법이 그리디 알고리즘이라고 한다.

하지만 아무리봐도 이해가 안가서 더 고민하고 내 방식대로 그리디 알고리즘의 아이디어만 차용해서 풀었다.

 

왜 그리디 알고리즘이 아니라고 생각했냐면

그리디 알고리즘은 1) 현재 상황에서 최선의 선택을 한다. 2) 각각의 결과는 서로에 영향을 미치면 안된다. 가 핵심인데, 풀이들을 보면 2)번 조건을 해치는 경우가 있었다.

 

앞에서부터 순회하면 뒤에 계산하는 부분에 영향을 미치기 때문에 앞에서부터 순회하는 방법은 그리디가 아니라고 생각했다.

그리고 앞에서부터 순회하면 현재 상황에서 최선의 선택을 했는지 알기가 어렵다.

 

예를 들어 int[] arr = {3,2,1,0,4} 라는 배열이 있다고 치면,

앞에서부터 순회를 한다면 3을 선택했을때 갈수 있는 경우의 수는 arr[1]=2, arr[2]=1, arr[3]=0 이다.

 

이 세가지 경우의 수 중에 어떤 것이 가장 탐욕(이익을 많이보는)적인가 하면 3칸을 가는 arr[3]일 것이다.

그렇지만 실제로 그렇게 가게되면 ......

 

반박하는 글을 적다가 왜 저게 그리디 알고리즘이 되는지 이해되었다.

갈 수 있는 경우의 수중에 가장 큰 수가 가장 탐욕적인 것이 맞다.

 

그 탐욕적인 값이 다음에 갈수있는 값에 영향을 미치지는 않으므로 그 탐욕적인 수에서 다시 분기를 나누어 가면 되므로 그리디 알고리즘이 맞다.

 

흔히 이야기하는 빠른 길 찾기 문제로 그리디 알고리즘 예시를 드는데, 앞에서 선택한 A->B까지 가는 가장 빠른 길이 B->C까지 가는 가장 빠른길에 영향을 주지 않는다.

 

이렇게 서로의 영향을 미치면 안되는 문제인데, 이 문제의 경우 배열의 맨처음에서 갈 수 있는 경로가 나눠진다면 최종 결과값에 영향을 미치기 때문에 그리디 알고리즘이 아니라고 생각했다.

 

그런데 그렇게 따지면 빠른길 찾기 문제에서도 A->B를 택하는 경로에 따라 A->C까지 가는 최종경로 값이 달라지는 것이다.

하지만 A에서 B를 택했을 때, B에서 C로가는 경로의 수가 달라지지는 않는다.

 

마찬가지로 {3,2,1,0,4} 라는 배열에서도 처음 수 3을 보고 2로 가든 1로가든 0으로가든 이동하는 값이 바뀌지는 않기 때문에 그리디 알고리즘으로 볼 수 있다.

 

public class Solution {
    public boolean canJump(int[] nums) {
        int distance = 0;
        for (int i = 0; i <= distance; i++) {
            distance = Math.max(distance, i + nums[i]);
            if (distance >= nums.length - 1) {
                return true;
            }
        }
        return false;
    }
}

이 코드는 진짜 딱 넘치지 않게 구현한 코드다.

distance가 0이지만 i=0이라 한 번 실행되는데, 여기서 배열 한개짜리도 처리가 되는 신기한 코드다.

 

Math클래스의 max 메소드를 활용하여 더 갈수 있는 거리가 있다면 distance로 저장한다.

그리고 distance가 배열 길이를 넘으면, true를 반환한다.

 

정리

내가 푼 방식도 그리디 알고리즘에 해당하기는 한다. 거꾸로 순회하기는 하지만..

계속 배열 관련된 문제를 풀다보니 나는 뒤에서부터 뭔가 처리하는게 익숙하고 자연스러운 것 같다.

 

뒤에서부터 도착지점을 정하여 그 도착 지점을 갱신하며 값을 구하는 방법,

앞에서부터 가장 효율적인 값을 찾아 그 값으로 다시 갱신하며 찾는 방법

 

모두 알아두어야 겠다.