[Java] 백준 11659 구간 합 구하기4

안녕하세요 백준 11659 구간합 구하기 문제를 풀어보겠습니다.

 

11659번: 구간 합 구하기 4

11659번: 구간 합 구하기 4

 

---

문제풀이

1) 문제 분석하기

• 수의 개수, 합의 개수 횟수 최대 100,000 회
• 시간제한 0.5초
• 구간 합 공식 이용 해야함
  • 구간 합 공식 이용하지 않을 시, 매번 계산을 해야 함으로, 시간을 초과하게 될 것이다.
• 보통 1억번 연산 = 1초 라고 생각하면 됨.

 

2) 요구조건 구현하기

• N개의 수를 입력받음과 동시에 합 배열 생성하기
  • S[i] = S[i-1]+A[i] ⇒ 합 배열 구하기

• 구간 합 생성 하기
  • 공식 : S[j] = S[j] - S[i-1]
  • 질의(1,3) → S[3] - S[0] (0부터3까지 합을 구하라는 뜻)
  • 질의(2,4) → S[4] - S[1] (1부터 4까지 합을 구라는 뜻)
  • 질의(5,5) → S[5] - S[4] (4부터 5까지 합을 구하라는 뜻)

 

3) 슈도 코드 작성

• suNo(숫자 개수), quizNo(질문 개수) 저장
• for(숫자 개수만큼 반복)
  • 합 배열 생성 후 바로 저장 ( S[i] = S[i-1] + A[i]
• for(질문 개수만큼 반복)
  • 질의 범위 받기
  • 구간 합 출력하기 ( S[j] = S[j] -S[i-1]

 

4) 코드 작성

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

public class B11659 {
	public static void main(String[] args) throws IOException {
		BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));

		//데이터를 한줄로 쭉 받아올 때 사용
		StringTokenizer stringTokenizer = new StringTokenizer(bufferedReader.readLine());

		//int 값이므로 stringTokenizer를 파싱에서 받아와야함
		int suNo = Integer.parseInt(stringTokenizer.nextToken());
		int quizNo = Integer.parseInt(stringTokenizer.nextToken());

		//배열 0번째 인덱스 무시하고 1부터 시작하게 하려고 +1을 함
		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]);
		}

	}
}

• 위 코드는 Scanner로 입력을 받지 않았습니다.
  • BufferReader를 사용해서 입력을 받았습니다
  • Scanner 랑 BufferReader의 차이는 입력이 많을 때는 BufferReader가 속도가 빨라 더 좋다고 합니다. 보통 Scanner도 좋지만 데이터가 많을 떄는 BufferReader를 사용하는게 좋다고 합니다
  • 결국 두개를 다 사용해보면 좋을 것 같기 때문에 번걸아 가면서 사용을 해보려고 합니다.
• 그리고 원래 입력을 받을 떄 scanner 같은경우는 scanner.nextInt() 처럼 입력을 받지만, BufferReader는 bufferedReader.readLine() 로 입력을 받는다는 차이가 있습니다.
• 그리고 위 코드에서 뜬금 없이 StringTokenizer 클래스를 사용한 이유는 입력을 받을 때 구분자를 설정하기 위해서 입니다.
  • 즉 우리가 배열을 입력을 받을 때 109876 보다는 10 9 8 7 6 ⇒ 이런식으로 띄어쓰기 위함 입니다.
  • 위 코드는 구분자를 공백으로 잡았기 때문에 입력을 할때 한개 입력하고 띄어쓰기하고 이런식으로 수를 입력해야 합니다.
• 위 과정으로 입력을 받고, suNo, quizNo라는 숫자 2개를 stringTokenizer을 nextToken() 메소드를 활용해서 입력받습니다.
  • 형변환을 하는 이유는 int로 선언한 변수지만, stringTokenizer 는 String 값이기 때문에 형 변환을 해줬습니다.
  • **stringTokenizer.nextToken()**은 다음 토큰을 반환하기 위한 메소드 입니다.
    • 우리는 토큰을 띄워쓰기 를 기준으로 나눴기 때문에 띄워쓰기 후 다음 값을 반환합니다.
  • 예시

  StringTokenizer stringTokenizer = new StringTokenizer("Hello World");
  String token = stringTokenizer.nextToken();
  System.out.println(token); 
  // 출력: Hello
  

2) Scanner사용한 버전 

import java.util.Scanner;

public class B11659 {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        // suNo와 quizNo를 입력받음
        int suNo = scanner.nextInt();
        int quizNo = scanner.nextInt();

        // 배열 초기화 및 합 배열 구하기
        long[] S = new long[suNo + 1];
        for (int i = 1; i <= suNo; i++) {
            S[i] = S[i - 1] + scanner.nextInt();
        }

        // 구간합 구하기
        for (int q = 0; q < quizNo; q++) {
            int i = scanner.nextInt();
            int j = scanner.nextInt();
            System.out.println(S[j] - S[i - 1]);
        }

        // 사용이 끝난 Scanner 닫기
        scanner.close();
    }
}

이상 구간 합 구하기 마치겠습니다.

감사합니다.