[해커랭크(HackerRank) JAVA 풀이] - Java 1D Array (Part 2)

해커랭크 - https://www.hackerrank.com/
Prepare > Java > Data Structures > Java 1D Array (Part 2)

HackerRank

 

배열에서 게임을 합시다! 당신은 game이라는 n-요소 배열의 인덱스 0에 서 있습니다. 일부 인덱스 i(여기서 0 ≤ i ≤ n)에서 다음 동작 중 하나를 수행할 수 있습니다.

• 뒤로 이동: 셀 i - 1이 존재하고 0이 포함된 경우 셀 i - 1로 다시 이동할 수 있습니다.
• 앞으로 움직이다:
  ο 셀 i + 1에 0이 포함되어 있으면 셀 i + 1까지 걸어갈 수 있습니다.
  ο 셀 i + leap에 0이 포함되어 있으면 셀 i + leap으로 이동할 수 있습니다.
  ο 셀 n - 1 또는 i + leap ≥ n 값에 서 있는 경우 배열의 끝에서 걷거나 점프하여 게임에서 승리할 수 있습니다.

즉, 대상 인덱스가 0을 포함하는 셀이면 인덱스 i에서 인덱스 i + 1, i - 1 또는 i + leap로 이동할 수 있습니다. 대상 인덱스가 n - 1보다 크면 승리합니다.

 

Function Description

아래 에디터에서 canWin 기능을 완성하세요.
canWin에는 다음 매개변수가 있습니다.

• int leap : 도약의 크기
• int game[n] : 탐색할 배열

 

Returns

boolean: 게임에서 이길 수 있으면 true, 그렇지 않으면 false

 

Input Format

첫 번째 줄에는 쿼리(즉, 함수 호출) 수를 나타내는 정수 q가 포함됩니다.
2 · q 후속 줄은 두 줄에 걸쳐 각 쿼리를 설명합니다.

1. 첫 번째 줄에는 n 및 leap의 각 값을 설명하는 두 개의 공백으로 구분된 정수가 있습니다.
2. 두 번째 줄에는 game₀, game₁, ... , gameₙ₋₁의 각 값을 설명하는 n개의 공백으로 구분된 이진 정수(0과 1)가 있습니다.

 

Constraints

• 1 ≤ q ≤ 5000
• 2 ≤ n ≤ 100
• 0 ≤ leap ≤ 100
• game[0]의 값은 항상 0입니다.

 

 

Sample Input

STDIN           Function
-----           --------
4               q = 4 (number of queries)
5 3             game[] size n = 5, leap = 3 (first query)
0 0 0 0 0       game = [0, 0, 0, 0, 0]
6 5             game[] size n = 6, leap = 5 (second query)
0 0 0 1 1 1     . . .
6 3
0 0 1 1 1 0
3 1
0 1 0

 

Sample Output

YES
YES
NO
NO

 

Explanation

다음 q = 4 쿼리를 수행합니다.

1. game = [0, 0, 0, 0, 0] 및 leap = 3의 경우 모든 셀에 0이 포함되어 있기 때문에 배열의 끝으로 걷거나 점프할 수 있습니다. 이길 수 있기 때문에 true를 반환합니다.
2. game = [0, 0, 0, 1, 1, 1] 및 leap = 5의 경우 인덱스 1로 걸어간 다음 i + leap = 1+ 5 = 6 단위를 배열의 끝까지 이동할 수 있습니다. 우리가 이길 수 있기 때문에 우리는 true를 반환합니다.
3. game = [0, 0, 1, 1, 1, 0] 및 leap = 3의 경우 연속 3개를 지나갈 방법이 없습니다. 우리는 이길 수 없기 때문에 false를 반환합니다.
4. game = [0, 1, 0] 및 leap = 1의 경우 인덱스 1에 있는 것을 지나칠 방법이 없습니다. 이길 수 없기 때문에 false를 반환합니다.

 

 

Code

import java.util.*;

public class Solution {

    public static boolean canWin(int leap, int[] game) {
        // Return true if you can win the game; otherwise, return false.
        return canWin(leap, game, 0);
    }
    
    public static boolean canWin(int leap, int[] game, int pos) {
        if( pos < 0 ) return false;
        if( game[pos] == 1 ) return false;
        if( pos+leap >= game.length ) return true;
        if( pos+1 >= game.length ) return true;
        game[pos] = 1;
        return canWin(leap, game, pos+leap)
            || canWin(leap, game, pos+1)
            || canWin(leap, game, pos-1);
    }

    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int q = scan.nextInt();
        while (q-- > 0) {
            int n = scan.nextInt();
            int leap = scan.nextInt();
            
            int[] game = new int[n];
            for (int i = 0; i < n; i++) {
                game[i] = scan.nextInt();
            }

            System.out.println( (canWin(leap, game)) ? "YES" : "NO" );
        }
        scan.close();
    }
}

 

 

재귀(Recursion)
어떠한 것을 정의할 때 자기 자신을 참조하는 것.
자기 언급과도 관련된 재귀는 언어학에서 논리학에 이르기까지 다양한 분야에서 연구되는 주제로, 특히 컴퓨터 과학과 수학에서 재귀는 함수가 자신의 정의에 의해 정의될 때의 개념을 가리킨다.
- 위키백과

재귀함수(Recursive method)
함수가 직접, 간접적으로 자신을 호출하는 프로세스.
쉽게 생각하면 어떤 함수 내부에서 자기 자신 함수를 다시 호출하는 것.
반복적인 일을 처리할 때 반복문도 사용하지만 재귀함수도 사용한다.

 

 

 

개인 공부를 위한 포스팅입니다.
모든 번역, 코드는 완벽하지 않을 수 있습니다.