[해커랭크(HackerRank) JAVA 풀이] - Java Subarray

해커랭크 - https://www.hackerrank.com/
Prepare > Java > Data Structures > Java Subarray

HackerRank

 

다음을 정의합니다.

• n-요소 배열의 하위 배열은 원래 배열 요소의 연속 블록으로 구성된 배열입니다. 
  예를 들어 array=[1, 2, 3]이면 하위 배열은 [1], [2], [3], [1, 2], [2, 3] 및 [1, 2, 3]입니다.
  [1, 3]과 같은 것은 원래 배열의 연속적인 하위 섹션이 아니므로 하위 배열이 아닙니다.
• 배열의 합은 해당 요소의 총합입니다.
  배열 요소의 총합이 음수이면 배열의 합은 음수입니다.
  배열 요소의 총합이 양수이면 배열의 합은 양수입니다.

n개의 정수 배열이 주어지면 음수 하위 배열의 수를 찾아 새 줄에 출력합니다.

 

Input Format

• 첫 번째 줄에는 배열 A = [a₀, a₁, ... , aₙ₋₁]의 길이를 나타내는 단일 정수 n이 있습니다.
• 두 번째 줄에는 배열 A의 각 요소 aᵢ를 설명하는 n개의 공백으로 구분된 정수가 포함되어 있습니다.

 

Constraints

• 1 ≤ n ≤ 100
• -10⁴ ≤ aᵢ ≤ 10⁴

 

Output Format

합이 음수인 A 의 부분배열 개수를 출력합니다.

 

 

Sample Input

5
1 -2 4 -5 1

 

Sample Output

9

 

Explanation

다음과 같은 9개의 음수 하위 배열 A = [1, -2, 4, -5, 1]이 있습니다.

1. [1 : 1] ⇒ -2
2. [3 : 3] ⇒ -5
3. [0 : 1] ⇒ 1 + -2 = -1
4. [2 : 3] ⇒ 4 + -5 = -1
5. [3 : 4] ⇒ -5 + 1 = -4
6. [1 : 3] ⇒ -2 + 4 + -5 = -3
7. [0 : 3] ⇒ 1 + -2 + 4 + -5 = -2
8. [1 : 4] ⇒ -2 + 4 + -5 + 1 = -2
9. [0 : 4] ⇒ 1 + -2 + 4 + -5 + 1 = -1

따라서 새 줄에 9를 출력합니다.

 

 

Code

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

public class Solution {

    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        int[] a = new int[n];
        for(int i=0; i<n; i++) a[i] = scan.nextInt();
        scan.close();
        
        int sum, cnt = 0;
        for(int i=0; i<n; i++) {
            sum = 0;
            for(int j=i; j<n; j++) {
                sum += a[j];
                if( sum < 0 ) cnt++;
            }
        }
        
        System.out.println(cnt);
    }
}

 

 

 

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