백준알고리즘 11659번 구간 합 구하기 4 C#

세부 정보

• 사이트: 백준알고리즘
• 번호: 11659
• 문제명: 구간 합 구하기 4
• 언어: C#
• 분류: 누적 합
• 비고: 

 

문제

수 N개가 주어졌을 때, i번째 수부터 j번째 수까지 합을 구하는 프로그램을 작성하시오.

 

입력

첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j가 주어진다.

 

출력

총 M개의 줄에 입력으로 주어진 i번째 수부터 j번째 수까지 합을 출력한다.

 

풀이

StringBuilder의 Append를 사용해서 출력 내용물을 구현하면 더 빠르다. AppendLine(sum)으로 하면 오류가 날 수 있다.

using System.Text;
// 스트림 입력을 받을 준비를 한다.
StreamReader sr = new StreamReader(Console.OpenStandardInput());
// 스트림 출력을 할 준비를 한다.
StreamWriter sw = new StreamWriter(Console.OpenStandardOutput());
// 스트링빌더 선언
StringBuilder sb = new StringBuilder();

// 수의 개수와 합을 구해야 하는 횟수 입력
int[] nm = sr.ReadLine().Split().Select(int.Parse).ToArray();
// N개의 수를 저장할 변수 선언
int[] nNum = new int[nm[0]];
// N개의 수를 입력
nNum = sr.ReadLine().Split().Select(int.Parse).ToArray();

// 밑의 슬라이딩 윈도우 알고리즘에서 나온 누적합을 저장할 변수
int[] mNum = new int[nm[0] + 1];
// 슬라이딩 윈도우 알고리즘 사용
// i번째 입력까지의 누적합 저장
for(int i = 1; i <= nm[0]; i++)
    mNum[i] = mNum[i - 1] + nNum[i - 1];

for (int i = 0; i < nm[1]; i++)
{
    // 합을 구해야 하는 구간 입력
    int[] ij = sr.ReadLine().Split().Select(int.Parse).ToArray();
    // 지정 범위 내 누적합을 구한다
    int sum = mNum[ij[1]] - mNum[ij[0] - 1];
    // 스트링빌더에 구한 누적합을 대입한다.
    sb.Append(sum + "\n");
}
// 누적합 출력
sw.WriteLine(sb.ToString());

// 스트림 입력을 종료한다.
sr.Close();
// 스트림 출력을 종료한다.
sw.Close();

 

후기

처음 풀 때 StreamReader와 StreamWriter를 사용하는 것은 자연스럽게 이루어졌다. 소스 코드 작성도 순조로웠다. 작성 도중에 ReadLine().Split().Select(int.Parse).ToArray()가 생각나자 그대로 진행했다. 하지만 시간 초과가 나오면서 실패했다.

// 스트림 입력을 받을 준비를 한다.
StreamReader sr = new StreamReader(Console.OpenStandardInput());
// 스트림 출력을 할 준비를 한다.
StreamWriter sw = new StreamWriter(Console.OpenStandardOutput());

int[] nm = new int [2];

// 수의 개수와 합을 구해야 하는 횟수 입력
nm = sr.ReadLine().Split().Select(int.Parse).ToArray();

int[] nNum = new int[nm[0]];

// N개의 수를 입력
nNum = sr.ReadLine().Split().Select(int.Parse).ToArray();

int[] mNum = new int[nm[1]];
int[] sum = new int[nm[1]];

for (int i = 0; i < nm[1]; i++)
{
    // 합을 구해야 하는 구간 입력
    mNum = sr.ReadLine().Split().Select(int.Parse).ToArray();

    // 구간 내의 합을 구한다.
    for (int j = mNum[0]; j <= mNum[1]; j++)
        sum[i] += nNum[j - 1];
    
    sw.WriteLine(sum[i]);
}

// 스트림 입력을 종료한다.
sr.Close();
// 스트림 출력을 종료한다.
sw.Close();

 

일단 for문을 이중으로 사용하면 시간이 오래 걸린다는 것은 알고 있었다. Split()은O(N)의 시간 복잡도를 가지고 있는 것도 알아냈다. 인터넷에서는 슬라이딩 윈도우라는 개념으로 이 문제를 풀 수 있다는 것을 알아냈다. 또한 StringBuilder를 사용해서 소요 시간을 줄인 것도 확인헀다. 고정된 크기의 윈도우가 이동하면서 윈도우 내 데이터를 이용해서 문제를 푼다고 알려져 있다. 늘 쓰게 된 StreamReader와 StreamWriter와 같이 StringBuilder를 사용하면 시간 단축을 극대화할 수 있을 것이다.