[알고리즘_코딩 테스트_JAVA] 구간 합 (JAVA, PYTHON)

본문은 알고리즘 코딩테스트 자바편을 정리한 내용입니다 :)

 

🟫 구간 합 핵심 이론 

• 합 배열 S를 만드는 공식

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

• 구간 합을 구하는 공식

S[j] - S[i-1] // i에서 J까지 구간 합

✔ 문제 001 숫자의 합 구하기

문제 바로가기 💨 

JAVA

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

class Main {
	public static void main (String[] args) throws java.lang.Exception {
	    
	    // 받는 데이터가 많을때는 bufferedReader 사용
	    BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
	    StringTokenizer stringTokenizer = new StringTokenizer(bufferedReader.readLine());
	    
	    int suNo = Integer.parseInt(stringTokenizer.nextToken());
	    int quizNo = Integer.parseInt(stringTokenizer.nextToken());
	    
	    long[] S = new long[suNo + 1];
	    
	    stringTokenizer = new StringTokenizer(bufferedReader.readLine());
	    for(int i = 1; i <= suNo; i++) {
	        S[i] = S[i - 1] + Integer.parseInt(stringTokenizer.nextToken());
	    }
	    for(int q = 0; q < quizNo; q++){
	        stringTokenizer = new StringTokenizer(bufferedReader.readLine());
	        int i = Integer.parseInt(stringTokenizer.nextToken());
	        int j = Integer.parseInt(stringTokenizer.nextToken());
	        System.out.println(S[j] - S[i-1]);
	    }
	    
	}
}

 

Python

import sys
input = sys.stdin.readline
 
m, n = map(int, input().split())
arr = list(map(int, input().split()))
prefix_sum = [0]    # init prefix_sum    
 
temp = 0    
for i in arr:    # accumulate arr section 
    temp += i
    prefix_sum.append(temp)

for i in range(n):
    i, j = map(int, input().split())
    print(prefix_sum[j] - prefix_sum[i-1])

 

✔ 문제 002 구간 합 구하기 5

문제 바로가기 💨 

 

그냥 구하면 시간 초과가 날 수 있다! 따라서 구간합을 이용

🟡 D[i][j]의 값을 채우는 합 공식

• D[i][j] = D[i][j-1] + D[i-1][j] - D[i-1][j-1] + A[i][j]

 

🟡  X1,X2,Y1,Y2 구간합 구하는 법

• D[X2][Y2] = D[X1-Y2]-D[X2][Y1-1]+D[X1-1][Y1-1]

JAVA

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

class Main {
	public static void main (String[] args) throws java.lang.Exception {
	    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	    StringTokenizer st = new StringTokenizer(br.readLine());
	    int N = Integer.parseInt(st.nextToken()); // 2 차원 배열 크기
	    int M = Integer.parseInt(st.nextToken()); // 구해야하는 구간 합 수
	    
	    // 배열 입력과 동시에 합 배열 구하기
	    int[][] S = new int[N+1][N+1];
	    for(int i = 1; i < N+1; i++){
	        st = new StringTokenizer(br.readLine());
	        for(int j = 1; j < N+1; j++) {
	            S[i][j] = S[i][j-1] + S[i-1][j] - S[i-1][j-1] + Integer.parseInt(st.nextToken());
	        }
	    }
	    
	    // 구간 합 구한 후 출력
	    int result = 0;
	    for(int i=0; i<M; i++){
	        st = new StringTokenizer(br.readLine());
	        int x1 = Integer.parseInt(st.nextToken());
	        int y1 = Integer.parseInt(st.nextToken());
	        int x2 = Integer.parseInt(st.nextToken());
	        int y2 = Integer.parseInt(st.nextToken());
            result = S[x2][y2] - S[x1-1][y2] - S[x2][y1-1] + S[x1-1][y1-1];
            System.out.println(result);
	    }
	}
}

 

Python

import sys

input = sys.stdin.readline

N, M = map(int, input().split()) # 리스트 크기,질의 수
A = [[0] * (N + 1)] # 원본 리스트 (0으로 초기화)
D = [[0] * (N + 1) for _ in range(N+1)] # 합 배열


# 원본 리스트 데이터 저장
for i in range(N): # 각 행 입력 받기
    A_row =[0] + [int(x) for x in input().split()] # ((0 padding))
    A.append(A_row)

for i in range(1, N+1):
    for j in range(1, N+1):
        D[i][j] = D[i][j-1] + D[i-1][j] - D[i-1][j-1] + A[i][j]

for _ in range(M):
    x1, y1, x2, y2 = map(int,input().split())
    result = D[x2][y2] - D[x1-1][y2] - D[x2][y1-1] + D[x1-1][y1-1]
    print(result)

 

✔ 문제 003 나머지 합 구하기

문제 바로가기 💨 

문제 분석
N의 최대값이 10^6이라 연산량이 작게 느껴질 수 있지만,10^6에 대하여 모든 구간 합을 구해야 하므로 1초 안에 연산하기는 어렵다. 모든 구간합을 구하기에 1초는 너무 짧다(시간초과).

나머지 합 문제 풀이의 핵심 아이디어

• (A+B)%C는 ((A%C) + (B%C))%C와 같다 특정 구간 수들의 나머지 연산을 더해 나머지 연산을 한 값과 이 구간 합의 나머지 연산을 한 값은 동일하다.
• S[i] - S[j] 는 원본 배열의 j+1 부터 i 까지의 구간 합이다.
• S[i] % M 값과 S[j] % M의 값이 같다면 (S[i] - S[j]) % M은 0이다. 즉 구간 합 배열의 원소를 M으로 나눈 나머지 값을 업데이트하고 S[i] 와 S[j] 가 같은 (i,j)쌍을 찾으면 원본 배열에서 i + 1부터 j 가지의 구간 합이 M으로 나누어떨어진다는 것을 알 수 있다.

JAVA

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

class Main {
	public static void main (String[] args) throws java.lang.Exception {
	    Scanner sc = new Scanner(System.in);
	    int N = sc.nextInt();
	    int M = sc.nextInt();
	    long[] S = new long[N]; // 수열 합 배열
	    long[] C = new long[M]; // 같은 나머지의 인덱스를 카운트하는 배열
	    long answer = 0;
	    
	    S[0] = sc.nextInt();
	    
	    // 수열 합 배열 만들기
	    for(int i = 1; i < N; i++){
	        S[i] = S[i -1] + sc.nextInt();
	    }
	    
	    // 합 배열의 모든 값에 % 연산 수행하기
	    for(int i = 0; i < N; i++){
	        int remainder = (int) (S[i] % M);
	        // 0~i까지의 구간 합 자체가 0일때 정답에 더하기
	        if(remainder==0) answer++;
	        C[remainder]++; // 나머지가 같은 인덱스 개수 카운팅하기
	    }
	    
	    // C[i](i가 나머지인 인덱스의 개수)에서 2가지를 뽑는 경우의 수를 더하기
	    for(int i = 0; i < M; i++){
	        if(C[i]>1) {
	            answer = answer + (C[i] * (C[i] - 1) / 2);
	        }
	    }
	    System.out.println(answer);
	}
}

 

Python

import sys
input = sys.stdin.readline

n, m = map(int, input().split()) # 수열 개수, 나누어떨어져야 하는 수
a = list(map(int,input().split()))
s = [0] * n # 합 배열
c = [0] * m # 같은 나머지의 인덱스를 카운트하는 배열 (i가 나머지인 인덱스개수 배열)
answer = 0

# 합 배열 저장
s[0] = a[0]
for i in range(1, n):
    s[i] = s[i-1] + a[i] # 합 배열을 M으로 나눈 나머지 값

# 합 배열을 M으로 나눈 나머지 값
for i in range(n):
    remainder = s[i] % m
    if remainder == 0:
        answer+=1
    c[remainder] += 1

# c[i]중 두개를 뽑는 경우의 수 계산
for i in range(m):
    if c[i] > 1:
        answer += (c[i]*(c[i]-1) // 2) # c[i]개 중 2개를 뽑는 경우의 수

print(answer)

---

https://dev-coco.tistory.com/94

[Java] StringTokenizer 문자열 분리하기 (split과 차이는 뭘까?)