구간 합 구하기 (문제 003) (BufferedReader 활용법)

문제 003. 구간 합 구하기

수 N개가 주어졌을때 i 번째 수에서 j 번째 수까지의 합을 구하는 프로그램을 작성하시오.

입력
1번째 줄에 수의 개수 N(1<= N <= 100,000), 합을 구해야 하는 횟수 M(1 <= M <= 100,000), 2번째 줄에 N개의 수가 주어진다. 각 수는 1,000 보다 작거나 같은 자연수다. 3번째 줄부터는 M개의 줄에 합을 구해야 하는 구간 i와 j가 주어진다.

늘 1차적으로 확인해야하는 건 구해야하는 조건의 데이터 범위 확인.

여기선, N과 M의 범위. 둘 다 10만까지 가능하다는 것이 확인하다.

앞서 시간 복잡도 개념을 공부할 때 코딩 테스트는 늘 최악의 경우를 고려해서 풀어야 한다고 했다. 

(2022.09.21 - [CS 전공지식(강의록 비공개)/Do it_알고리즘_코딩 테스트] - 시간 복잡도의 개념 참조)

때문에 문제를 풀 때, 가장 큰 데이터가 들어온다고 가정을 하고 문제를 풀어야 한다. 

출력
총 M개의 줄에 입력으로 주어진 i 번째 수에서 j 번째 수까지의 합을 출력한다.

예시 입력값과 출력값

 

1 2 3 4 5 (합배열 인덱스)

5 4 3 2 1이 원본의 데이터이고 

두번째 질의에서 인덱스 2(값:4)부터 인덱스 4(값:2). 즉 2~4번까지의 구간 합은 4+3+2+1 = 9

 

1단계 문제 분석하기

문제에서 주어진 가장 큰 배열의 범위인 10만개의 숫자가 주어졌다고 했을 때, 이들을 일일히 하나하나 구간합 배열로 구하면 문제에서 제시한 0.5초의 시간제한 안에 풀수 없다. 왜 그럴까?

 

항상 최악의 케이스를 생각해야하기 때문이다

 

1. 구간합을 구해야하는 배열의 길이 자체가 10만개가 들어왔다고 가정을 하고, 질의 횟수도 10만개라고 가정을 하자.

2. 첫번째 질의가 1부터 10만개까지의 부분합을 구해야한다고 할 때, 구간합을 일일히 구하면 10만개의 연산횟수가 된다.

3. 구하는데 10만번의 연산횟수가 들어간다는 말은. 질의 1번에 최악의 케이스이면 10만번의 연산이 일어난다는 것.

4. 게다가, 이 질의가 10만번 구할 수 있는데 10만번 * 10만번은 1억번이 넘는다.

5. 그러면 1억번의 연산횟수가 1초가 걸린다고 가정하는  자바에서는 시간제한인 0.5초 안에 구할 수 없는 것이다.  

 

처음 주어진 예시 입출력을 다시 보자

 

예시 입력 1 에서 정해둔 배열 5 4 3 2 1 은 픽스 된 값이다. 

심지어 여기서 질의의 개수가 엄청 많다?  이럴 때 구간 합 배열 알고리즘을 활용하는 것이다.

** 다시한번 픽스된 배열, 시간제한, 연산 횟수가 많을 때 활용하는 것이 구간 합 알고리즘

 

2단계 손으로 풀어보기

1. N개의 수를 입력받음과 동시에 합 배열을 생성한다.

=> 어떻게? 앞에서 배운 합 배열 공식(S[i] = S[i-1] + A[i]) 를 이용해서 

합 배열 공식
S[i] = S[i-1] + A[i]

헷갈리지 말아야 하는 부분이 위의 파란색 인덱스 숫자는 합배열 s의 인덱스도 아니고, 배열 a의 인덱스도 아니다!!!

그저 1부터 3까지의 구간 합, 3번째 부터 5까지의 구간합이라는 문제의 조건에 주어진 인덱스이다!!! (혼동 금지!!)

 

(** 변하지 않는 사실은 합 배열 S[0]은 항상 배열 A[0]과 같다는 것. S[0] = A[0] )

 

합배열 S는 구하는 것이 간단해서 입력과 동시에 바로 구할 수 있다.

그래서, 시간 제한 안에 구할 수 있는 것. 합 배열을 이용한 구간 합을 구해서 바로바로 정답을 출력하면 된다.

 

2. 구간 i ~ j 가 주어지면 구간 합을 구하는 공식으로 정답을 출력한다.

구간 합 공식
S[j] - S[i-1]

그럼 질의에서 1번째부터 3번째 구간을 구한다고 가정한다면,

 

그렇다면 질의 1에서 보이듯, 1번째 부터 3번째 구간까지의 합을 구한다고 한다면? 

공식에 의해서 S[3] - S[0]을 구해야한다. 그런데 여기선 0번째 인덱스 값이 없다? S[0]과 A[0]은 앞서서 0으로 있다고 가정한다. 아래의 강의록에서와 같다. 

S[3]은 인덱스가 1부터 시작하니까 12이다. (기존에 우리가 배열 0부터 시작하는 것과 다르다. 왜? 문제 조건에서 주어진  구간은 1번째부터 시작하니까) S[0]은 0이다. 

 

문제에서 주어진 대로 1번째 ~ 부터 시작하므로 인덱스도 1번 부터로 바뀌었다. 0번째 값은 0으로 계산한다.

 

3단계 슈도 코드 작성하기

suNo(숫자 개수), quizNo(질의 개수) 저장하기
for(숫자 개수만큼 반복하기) {                                        // 데이터를 받으면서 바로 포문으로 S배열을 만들어준다. 
     합 배열 생성하기(S[i] = S[i - 1] + A[i])                       // 공식 활용
}
for(질의 개수만큼 반복하기) {
     질의 범위 받기(i ~ j)
      구간 합 출력하기(S[j] - S[i - 1])
}

 

4단계 코드 구현하기

먼저 숫자 개수도 옆으로 10만개이고, 질의 개수도 10만개이듯

이렇게 받는 데이터가 많을 때에는 스캐너 보다는 버퍼드 리더를 사용하는게 좋다. 

보통 자바에서 입력은 스캐너를 사용했었다. 하지만 양이 많을 땐 하나하나 전달하지 않고 버퍼에 한 번에 모아서 전달하는 버퍼드 리더 클래스가 효율적이다. 

BufferedReader 클래스는 버퍼를 이용한 대표적인 I/O(Input/Output) 클래스다.
입력된 데이터를 바로 전달하는 것이 아니라, 버퍼에 저장해두었다가 전달하는 방법이다. 

Scanner 클래스는 Space, Enter 모두 경계로 입력값을 인식하고,
BufferedReader 클래스는 Enter만을 경계로 입력값을 인식한다
그래서 가공하는 작업이 추가로 필요하다 (구분하여 나누기 작업)

Stream으로 끝나는 클래스 : 바이트 단위로 입출력을 수행하는 클래스
Reader / Writer로 끝나는 클래스 : 캐릭터 단위로 입출력을 수행하는 클래스
File로 시작하는 클래스 : 하드디스크의 파일을 사용하는 클래스
Data로 시작하는 클래스 : 자바의 원시 자료형을 출력하기 위한 클래스
Buffered로 시작하는 클래스 : 시스템의 버퍼를 사용하는 클래스                         // 출처 : https://snupi.tistory.com/48

 

최종 코드 작성

각 라인마다 달아놓은 해설 각주. 헷갈릴 때마다 보려고 자세히 적어놨다.

 

문제 3번 드디어 .. 끝~