슈도코드
solution() {
int[] sum = numbers의 배열합 구하기
range에 해당하는 배열합 반환
}
main() {
N,M을 한줄에 입력받기 String
int N, M으로 변환
String numbers 입력받기
for(M만큼 반복) {
String range 입력받기
solution(range) 호출 및 출력
}
}Troubleshooting 1
for(int index = 0 ;index<M; index ++) {
String range = br.readLine();
bw.write(solution(numbers, range, N));
}오늘 처음으로 BufferedReader, BufferedWriter, StringTokenizer를 사용해봤다.
문제 1
- 입력은 제대로 들어가는데, 콘솔에 출력이 안되는 현상이 발생했다.(사진에서 '1 3', 다음줄 출력, '2 4', 다음줄 출력, '5 5', 다음줄 출력) 이렇게 돼야하는데, 입력만 들어가는상황..
원인
- 알고보니 BufferedWriter를 이용해 출력하려면,
.write()만 쓰면 안된다.
반드시.flush()까지 써야 콘솔에 출력이 된다고한다.
그리고 출력이 끝났으면, close()을 통해서 스트림을 닫는다고한다.
따라서 맨 마지막줄에bw.flush();를 추가했다. -> 문제2(Troubleshooting 2) 발생
Troubleshooting 2
문제 2
아래 사진처럼 '1 3' 다음줄에도 숫자를 입력해야하는데, 이후에 입력도 안들어가고 그렇다고 출력이 되는것도 아니다.
원인
❓write()는 개행기호를 만나야 그 전까지의 내용이 출력되는것같다..? (더 알아봐야함)
해결
bw.write(solution(numbers, range, N) + "\n");로 뒤에 개행기호 '\n'를 넣었다.
+System.out.println()로 수정해도된다.
Troubleshooting 3
문제
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;
public class Main {
public static int solution(String numbers, String range, int N) {
StringTokenizer st = new StringTokenizer(range);
int answer = 0;
int[] rangeSum = new int[N];
String[] numbersStrArray = numbers.split(" ");
rangeSum[0] = Integer.parseInt(numbersStrArray[0]);
for(int i=1; i<N; i++) {
rangeSum[i] = rangeSum[i-1] + Integer.parseInt(numbersStrArray[i]);
}
int start = Integer.parseInt(st.nextToken())-1;
int end = Integer.parseInt(st.nextToken())-1;
answer = rangeSum[end] - rangeSum[start] + Integer.parseInt(numbersStrArray[start]);
return answer;
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
String nAndM = br.readLine();
StringTokenizer st = new StringTokenizer(nAndM);
int N = Integer.parseInt(st.nextToken());
int M = Integer.parseInt(st.nextToken());
String numbers = br.readLine();
for(int index = 0 ;index<M; index ++) {
String range = br.readLine();
bw.write(solution(numbers, range, N) + "\n");
bw.flush();
}
}
}위의 코드가 IDE에서는 정상적으로 동작해서 제출했는데, 시간초과가 났다.
원인
합 배열을 solution에서 만들면, 결국 범위를 호출할때마다 매번 만들기때문에 합 배열의 목적인 시간단축의 의미가 사라지는것아닐까?싶었는데 역시나 그랬다.
해결
이 문제는 main 하나로 해결할 수 밖에 없을 것 같아서, main메소드에 통일했다.
제출 코드
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st = new StringTokenizer(br.readLine());
int N = Integer.parseInt(st.nextToken());
int M = Integer.parseInt(st.nextToken());
long[] rangeSum = new long[N+1];
st = new StringTokenizer(br.readLine());
for(int i=1; i<=N; i++) {
rangeSum[i] = rangeSum[i-1] + Integer.parseInt(st.nextToken());
}
for(int index = 0 ;index < M; index ++) {
st = new StringTokenizer(br.readLine());
int i = Integer.parseInt(st.nextToken());
int j = Integer.parseInt(st.nextToken());
bw.write((rangeSum[j] - rangeSum[i-1]) + "\n");
bw.flush();
}
}
}이 코드를 보며 배운점
- StringTokenizer은 처음에 선언한 이후, 또 사용할때에는 처음에 선언했던 변수명으로 동일하게 또 사용가능하며, 이후 선언할때에는 변수명앞에
StringTokenizer안써도된다. - 변수 선언시에는 항상 입력값의 범위를 생각하여 타입을 설정하여야한다.
- StringTokenizer의 파라미터값에서 바로 ₩bufferedReader.readLine()₩을 쓸 수 있다.
- 구간 합 배열을 만들 때 for문에서 index를 어떻게설정할지가 문제였는데, 구간합의 크기를 생성해야하는 값보다 하나 더 크게 주고, 첫번째 원소(index =0)는 없다고 가정하고 1부터 값을 넣으면된다. index0의 값을 0이라고 초기화하지 않아도 이후의 값이 정상적으로 들어간다. 여기서 이후에 이 합 배열을 사용할때에는 for문의 범위에 주의한다!
시간 복잡도
N의 최악 + M의 최악 = 100,000 + 100,000 = 200,000 -> 1억보다 작으므로 1초안에 될 것이다. 0.5초가 될지는 어떻게 판별하지..?❓
공부한 사항
- bufferedWriter
- bufferedReader
- StringTokenizer
- 합 배열 알고리즘
