11659 문제풀이
문제
수 N개가 주어졌을 때, i번째 수부터 j번째 수까지 합을 구하는 프로그램을 작성하시오.
입력
첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j가 주어진다.
출력
총 M개의 줄에 입력으로 주어진 i번째 수부터 j번째 수까지 합을 출력한다.
문제풀이
최근 러스트 언어를 공부하고 있기에 Rust 프로그램을 사용하여 작성해보았는데, 매우 간단하게 시간초과가 떴다.
fn main() {
let mut input = String::new();
std::io::stdin().read_line(&mut input).unwrap();
let (input_count, output_count) = input.trim_end().split_once(" ").unwrap();
let input_count = input_count.parse::<usize>().unwrap();
let output_count = output_count.parse::<usize>().unwrap();
let mut input_vector = Vec::new();
{
input.clear();
std::io::stdin().read_line(&mut input).unwrap();
let mut input_some = input.trim_end().split(" ");
for _ in 0..input_count {
input_vector.push(input_some.next().unwrap().parse::<usize>().unwrap());
}
}
for _ in 0..output_count {
input.clear();
std::io::stdin().read_line(&mut input).unwrap();
let (from, to) = input.trim_end().split_once(" ").unwrap();
let from = from.parse::<usize>().unwrap() - 1;
let to = to.parse::<usize>().unwrap() - 1;
let mut sum = 0;
for now in input_vector[from..=to].iter() {
sum += now;
}
println!("{}", sum);
}
}
이후, 다음과 같은 시도를 하여도 시간이 제대로 측정되지 않았다.
- string 버퍼 비우는 작업이 느릴것이라 판단하여 clear()메소드대신 { }을 사용하여 소멸하도록 변경
- 모든 입력값을 read_line을 통해 비우지 않고 한번에 받아 파싱을 나중에 하기
문제를 해결한 다음에 생각하는것인데, clear()메소드 대신 { }을 사용하여 변수가 소멸하도록 만든것은 그리 성능을 많이 개선시키지 못했을 것 같다.
이후, 입력 관련해서 시간을 더 줄이는데 신경을 썼다.
그리하여 프로그램 입력 성능 개선 관련 주석이 많이 달려있는 15552 문제를 참고해 다음과 같은 모듈을 작성하였다.
/* 이번 문제는 자연수만을 입력받기 때문에 다음과 같이 입력하였지만, 음수 및 소수도 비슷한 방법으로 가능하다. */
fn read_fastest() -> usize {
let mut sum = 0;
loop {
/* stdin()에서 한바이트를 입력받아 처리한다. */
// 다른 코드를 보면 이곳에서 결과가 제대로 나왔는지 체크하며
// char형태로 바꾸는 연산이 있었으나,
// 성능을 개선하기 위해 바이트 형태 그대로 읽어들이는 방법을 사용하였다.
let input = std::io::stdin().bytes().next().unwrap().unwrap();
/* \r이면 입력을 한번 더 받고 종료 */
if input == 13 {
continue;
}
/* 공백이나 \n이 오면 연산한 수를 출력한다. */
if input == 32 || input == 10 {
return sum;
}
/* 기존 값에 10을 곱해준 다음 */
sum *= 10;
/* 입력값을 숫자로 바꿔 0xf로 마스킹해준다 (아스키코드의 숫자로 바꾼다) */
sum += (input as usize) & 0xf;
}
}
다음과 같이 모듈을 작성하여 사용하여도, 시간초과가 나타났다.
이후 수의 합을 구하는 속도를 더 빠르게 연산하기 위해, 다음과 같은 시도를 해보았다.
- vector의 push 속도 줄이기 - capacity를 기입해 줘 벡터에 값을 넣는 시간을 줄였다
- vector의 한 데이터 읽는 속도 줄이기 - 포인터를 사용해 vector의 객체에 직접접근
for _ in 0..output_count {
let from = read();
let to = read();
let mut sum = 0;
let mut now: *const usize = &input_vector[from - 1];
for _ in from..to {
sum += unsafe { *now };
unsafe {
now = now.offset(1);
}
}
sum += unsafe { *now };
println!("{}", sum);
}
- 즉시 println!을 통한 출력이 아닌, 문자열로 저장하였다가 한번에 출력
하지만 다음과 같은 시도에도 시간초과가 계속 나타나, 결국 어떤 문제인지 알 수 없어 인터넷에 검색을 하여 파이썬 코드를 집어넣은 다음, 러스트로 맞춘 사람들의 소스코드를 열람하였다.
맞춘 사람의 소스코드를 보니, 받은 입력값을 구하는 방법은 달랐지만, 위의 소스코드의 성능이 다른 소스코드보다 좋게 나올것으로 기대하여 연산 속도에 차이가 날 수 있는 다른 구간을 찾아보았다.
이내, 다른 프로그램은 알고리즘적인 방법을 사용하여 구간의 합을 구하는 방법을 사용하고 있다는 것을 알게 되었다. (문제의 이름이 구간 합이었는데 입력속도에 문제가 있다고만 생각하여, 구간 합 알고리즘을 생각하지 못했다)
구간 합 알고리즘을 적용하여 작성한 완성 코드는 다음과 같다.
use std::io::Read;
fn main() {
let input_count = read();
let output_count = read();
let mut input_vector = vec![0; input_count];
for now in 0..input_count {
input_vector[now] = read();
}
let mut sums = Vec::with_capacity(input_count);
sums.push(input_vector[0]);
for now in 1..input_count {
sums.push(input_vector[now] + sums[now - 1]);
}
let mut out = String::new();
for _ in 0..output_count {
let from = read();
let to = read();
if from > 1 {
out.push_str(format!("{}\n", sums[to - 1] - sums[from - 2]).as_str());
} else {
out.push_str(format!("{}\n", sums[to - 1]).as_str());
}
}
print!("{}", out);
}
fn read() -> usize {
let mut sum = 0;
loop {
let input = std::io::stdin().bytes().next().unwrap().unwrap();
if input == 13 {
continue;
}
if input == 32 || input == 10 {
return sum;
}
sum *= 10;
sum += (input as usize) & 0xf;
}
}