Q. 수 N개가 주어졌을 때 i번째 수에서 j 번재 수까지의 합을 구하는 프로그램을 작성하시오.
(난이도: 실버 III)
(1) 입력: 1번째 줄에 수의 개수 N(1 <= N <= 100,000), 합을 구해야 하는 횟수 M(1 <= M <= 100,000), 2번째 줄에 N개의 수가 주어진다. 각 수는 1,000보다 작거나 같은 자연수다. 3번째 줄부터는 M개의 줄에 합을 구해야 하는 구간 i와j가 주어진다.
(2) 출력: 총 M개의 줄에 입력으로 주어진 i 번째 수에서 j번째 수까지의 합을 출력한다.
- 문제 분석
그렇다면 이 문제에서 해결해야 할 task는 무엇일까요? 바로
1. 숫자의 수, 구간 합 범위 지정 횟수, 배열 숫자 입력받기
2. 1번에서 입력 받은 배열을 기반으로 누적합 배열 s 만들기
3. 1번에서 입력 받은 구간 합 범위 지정 횟수만큼 돌면서 "범위"(인덱스)를 입력 받아 그 사이의 누적합 구하기
이 세가지가 이 문제에서 해결해야 할 task가 될 것 입니다.
예를 들어서 한 번 구체적으로 살펴보겠습니다.
아래와 같은 입력이 들어온다고 가정할게요. 이미지에도 나와 있지만
첫 번째 줄에는 입력받을 숫자의 수와 몇 번 구간 합을 구할건지를 입력받고 있고,
두 번째 줄에는 배열에 담을 숫자들을 입력받습니다.
배열을 입력 받았으면 위 이미지의 맨 위 배열처럼 표현될 수 있겠죠? 그 배열을 기반으로 가장 앞부터 차례대로 누적 합을 구하는겁니다. 예를 들어, 입력 배열의 두 번째 즉 arr[ 1 ]까지의 누적 합을 구하고 싶으면 1 + 2가 s[ i ]의 값으로 들어가게 되는거죠. 그래서 위와 같은 합 배열 공식이 성립 할 수 있는거구요.
이후 누적 합 범위 i, j를 입력 받아서 s [ j ]에서 i의 바로 이전 인덱스인 i-1의 요소 즉 s [i-1] 를 빼면 그 구간의 누적 합이 나오게 될 것입니다!
- 코드구현
코드 구현 한 번 살펴 볼까요?
주석에 달려있는 1 2 3 표시는 위에 언급 했던 3가지 task와 대응되는 부분이며,
위 문제 분석에서 언급한 구간 합 범위 i, j는 start와 end로 표현하였습니다.
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
//1. 문제의 조건에 따라 배열 크기, 구간합을 구하는 횟수 입력 받기
System.out.printf("입력받을 숫자의 수와 범위지정 횟수: ");
Scanner sc = new Scanner(System.in);
int num1 = sc.nextInt(); //java의 nextInt는 공백이나 개행문자를 기준으로 int형 숫자 하나만 받아들임
int num2 = sc.nextInt();
//1. 문제의 조건에 따라 배열 값들 입력 받기
int[] arr = new int[num1];
for(int i = 0; i < num1; i++)
arr[i] = sc.nextInt();
//2. 배열 arr의 누적합을 담고 있는 배열 s 구하기
int[] s = new int[num1];
for(int i = 0;i < num1;i++) {
if(i == 0)
s[i] = arr[i];
else
s[i] = s[i-1]+arr[i];
}
//3. 구간합을 구하는 횟수만큼 돌면서 구간합 구하기
int start,end;
for(int i = 0; i < num2;i++) {
System.out.printf("start end: ");
start = sc.nextInt();
end = sc.nextInt();
if(start == 1)
System.out.printf("%d부터 %d까지의 구간합은?: %d\n",start,end,s[end-1]);
else
System.out.printf("%d부터 %d까지의 구간합은?: %d\n",start,end,s[end-1]-s[start-2]);
}
}
}
출력 화면은 다음과 같습니다.
잘 나오죠? 오늘 코딩테스트 마무리 하겠습니다 :)
'Coding Test' 카테고리의 다른 글
do it 코딩 테스트: 평균 구하기 (0) | 2023.09.11 |
---|---|
do it 코딩 테스트: 숫자의 합 구하기 (0) | 2023.09.08 |