[백준] 구간 합 구하기 4(11659)

https://www.acmicpc.net/problem/11659

입력할 수의 개수와 숫자가 주어지면, i번째부터 j번째까지 수의 합을 구하는 문제이다.

문제에서 수의 개수와 합을 구해야하는 횟수는 최대 100,000 이다. 따라서 i번째부터 j번째 수가 주어질때마다 매번 구간 합을 계산하면 이중 for문이 되므로, 최악의 경우 $O(n^2)$이 된다.

Python

근데 파이썬에서는 1초에 2,000만번 연산을 수행한다고 가정하고 있다. 따라서 시간복잡도를 생각해보면 아래와 같다.

$O(n^2) > 시간 제한 1초 * 2,000만$
$= (100,000)^2 > (20,000,000)$

결론적으로 1억 회 이상 연산을 수행하게 되어 1초 이상의 수행시간이 필요하고, 이는 곧 시간 초과로 이어진다.

• 🧑‍💻 시간복잡도와 시간초과
  파이썬 프로그램에서는 2,000만번 ~ 1억 번의 연산을 1초안에 수행할 수 있는 능력이 있다.

  우리는 항상 최악의 경우를 기준으로 생각해야 하므로 파이썬은 1초에 2,000만번 연산을 수행한다고 생각하면 된다.

  또한 문제에서 주어지는 범위에서도 최악의 경우를 생각해야 하므로, 이 역시 가장 큰 데이터를 기준(이 문제에서는 100,000)으로 설정하면 된다.

따라서 문제 풀이 방법은 각 구간에 해당하는 합을 미리 구해놓고 계산하는 것이다.

합 배열 공식

$S[i] = S[i - 1] + A[i]$

A가 우리가 입력받은 원본 배열이고, S가 각 구간에 대한 합 배열이다. 예를 들어 A = [5, 4, 3, 2, 1]이면 S = [5, 9, 12, 14, 15]가 되는 것이다.

구간 합 공식

$S[j] - S[i - 1]$

특정 구간에 대한 합을 구하는 방법이다. 예를 들어 (1, 3)에 대한 구간 합을 구하고 싶으면 S[3] - S[0]을 하면 된다.
(수학시간에 배운 점화식을 생각해보자)

따라서 최종 코드는 아래와 같다.

# 입력 시간을 줄여줄 수 있도록 sys.stdin.readline 사용
import sys
input = sys.stdin.readline

N = list(map(int, input().split()))
num_arr = list(map(int, input().split()))

# 배열에 미리 0을 넣어놓음
# 배열의 인덱스는 1부터 시작
sum_arr = [0]
temp = 0

# 합 배열 구하기
for i in num_arr:
    temp += i
    sum_arr.append(temp)

# 구간 합 공식
for i in range(N[1]):
    s, e = map(int, input().split())
    print(sum_arr[e] - sum_arr[s - 1])

미리 구간 합을 구하니 시간복잡도가 $O(N)$이 되어 시간초과가 발생하지 않고 문제 요건에 부합하는 정답을 도출할 수 있다.

☃️ sys.stdin.readline()

참고로 input() 대신 sys.stdin.readline을 사용하면 입력 시간이 줄어드니 코테에서 자주 사용한다.

자세한 내용은 아래 링크에 잘 정리되어 있으니 참고하길 바란다.

이예서님의 velog: sys.stdin.readline 사용 이유 & 사용 방법
https://velog.io/@yeseolee/Python-%ED%8C%8C%EC%9D%B4%EC%8D%AC-%EC%9E%85%EB%A0%A5-%EC%A0%95%EB%A6%ACsys.stdin.readline

Java

자바 역시 시간복잡도는 파이썬과 동일하게, 1초에 2,000만번 연산을 수행한다고 가정하고 있다. 따라서 시간복잡도를 생각해보면 아래와 같다.

$O(n^2) > 시간 제한 1초 * 2,000만$
$= (100,000)^2 > (20,000,000)$

결론적으로 1억 회 이상 연산을 수행하게 되어 1초 이상의 수행시간이 필요하고, 이는 곧 시간 초과로 이어진다.

표현하는 언어만 자바로 바뀔 뿐 알고리즘은 구간 합을 그대로 적용하면 된다.

합 배열 공식

$S[i] = S[i - 1] + A[i]$

A가 우리가 입력받은 원본 배열이고, S가 각 구간에 대한 합 배열이다. 예를 들어 A = [5, 4, 3, 2, 1]이면 S = [5, 9, 12, 14, 15]가 되는 것이다.

구간 합 공식

$S[j] - S[i - 1]$

특정 구간에 대한 합을 구하는 방법이다. 예를 들어 (1, 3)에 대한 구간 합을 구하고 싶으면 S[3] - S[0]을 하면 된다.

다만 자바의 경우 안타깝게도 파이썬 처럼 간결한 문자열 처리를 지원하지 않는다... ㅠㅠ

그래서 자바로 입력이 잦은 문제를 풀려면 아래 2개 클래스를 꼭 기억해야 한다.

먼저 BufferedReader는 기존의 Scanner보다 빠른 입력 처리를 제공하며, 아래와 같이 사용한다.

// 빠른 입력 처리를 위해 BufferedReader 사용
// 바이트 스트림을 문자 스트림으로 변환하기 위해 InputStreamReader 사용
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

다음으로 StringTokenizer는 입력된 문자열을 구분자를 기준(default는 공백 기준)으로 토큰화하여 원하는 변수에 간편하게 저장할 수 있다.

// 특정 구분자(default 공백)를 기준으로 토큰화 해주는 StringTokenizer 사용
// 한 줄씩 읽어서 String 형태로 반환하는 readLine() 메서드
StringTokenizer st = new StringTokenizer(br.readLine());

// nextToken()을 통해 구분자를 기준으로 토큰화된 문자열들을 하나씩 들고옴
int suNo = Integer.parseInt(st.nextToken());
int quizNo = Integer.parseInt(st.nextToken());

BufferedReader와 StringTokenizer에 대한 자세한 설명은 아래 링크를 참고하길 바란다.

[프로그래머스] 코딩테스트에 필요한 자바 문법
https://velog.io/@wonotter/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-%EC%BD%94%EB%94%A9%ED%85%8C%EC%8A%A4%ED%8A%B8%EC%97%90-%ED%95%84%EC%9A%94%ED%95%9C-%EC%9E%90%EB%B0%94-%EB%AC%B8%EB%B2%95

따라서 전체 문제풀이 코드는 다음과 같다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class P_11659 {
    // BufferedReader 클래스의 readLine() 메서드가 IOException을 throws 하고 있음
    // 따라서 main 함수도 예외 처리를 JVM에 넘기기 위해 throws IOException 선언 필요
    public static void main(String[] args) throws IOException {
        // 빠른 입력 처리를 위해 BufferedReader 사용
        // 바이트 스트림을 문자 스트림으로 변환하기 위해 InputStreamReader 사용
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        // 특정 구분자(default 공백)를 기준으로 토큰화 해주는 StringTokenizer 사용
        // 한 줄씩 읽어서 String 형태로 반환하는 readLine() 메서드
        StringTokenizer st = new StringTokenizer(br.readLine());

        // nextToken()을 통해 구분자를 기준으로 토큰화된 문자열들을 하나씩 들고옴
        int suNo = Integer.parseInt(st.nextToken());
        int quizNo = Integer.parseInt(st.nextToken());

        // N + 1 크기의 배열 선언
        long[] S = new long[suNo + 1];
        st = new StringTokenizer(br.readLine());

        // 읽어들인 토큰(입력받은 배열)을 누적하여 더하며 합배열 생성
        for (int i = 1; i <= suNo; i++) {
            S[i] = S[i - 1] + Integer.parseInt(st.nextToken());
        }

        // 요청하는 구간합에 따라 구간 합을 구하여 정답 출력
        for (int q = 0; q < quizNo; q++) {
            st = new StringTokenizer(br.readLine());
            int i = Integer.parseInt(st.nextToken());
            int j = Integer.parseInt(st.nextToken());
            System.out.println(S[j] - S[i - 1]);
        }
    }
}