[알고스팟] ITES - 외계 신호 분석 (C++, 큐)

문제

 

https://algospot.com/judge/problem/read/ITES

algospot.com :: ITES

 

 

풀이

 

종만북 난이도: 중

 

큐를 사용하여 해결하는 문제.

신호의 기록은 입력값으로 주어지는 것이 아니라 직접 생성하는 문제이다.

특이 신호의 개수 N은 최대 50,000,000이므로 생성하여 저장하기보단 각 테스트 케이스마다 다시 생성하여 사용하는 것이 메모리를 절약할 수 있다. 

 

우리는 신호의 수열에서 부분 연속 수열의 원소합이 K인 부분 수열의 개수를 찾아야 한다.

연속 수열은 모든 원소가 연속되어야 하므로 첫 신호부터 차례대로 아래의 조건에 따라 큐에 push혹은 pop한다. 

 

현재의 신호 A[i] 값으로 계산한 입력 신호를 input_num그리고 지금까지 큐에 담은 신호들의 합을 total_sum이라고 하자.

 

1. total_sum + input_num > K

지금까지 큐에 담은 신호들의 합 total_sum과 input_num의 합이 K보다 크다면

연속 수열의 가장 앞 원소를 수열에서 때어내준다. (연속 수열이므로 뒤에서 값을 추가하려면 앞에서 밖에 때어낼 수 없음. 즉, 큐가 가장 적합한 자료구조이다.)

이를 total_sum + input_num > K가 아닐 때까지 반복해준다.

 

예를 들어 1 3 6 2 5 2의 수열에서 input_num: 6, K: 7인 경우를 생각해보자.

큐에는 1과 3이 담겨 total_sum은 4이다. total_sum + input_num = 10으로 K보다 크다.

따라서 6을 큐에 담으려면 적어도 total_sum + input_num <7일 때까지 원소를 빼내 주어야 한다.

결과적으로 6이 담기면 앞의 두 원소 1, 3은 큐의 앞에서 pop 해된다.

 

2. total_sum + input_num == K

큐에 지금까지 담긴 연속 수열의 값 total_sum에 input_num이 추가되면 K가 된다.

따라서 큐에 input_num을 push 해주고 해당 부분 수열을 카운트해준다.

모든 신호는 1 이상의 값이므로 total_sum = K인 현재 상태에서는 값을 추가할 수 없으므로 앞의 원소를 pop 해준다.

 

3. total_sum + input_num < K

 연속 수열의 값에 input_num가 추가되어도 여전히 K를 만족시키지 못하므로 큐에 input_num을 push 해준다.

 

1 3 6 2 5 2의 수열은 다음과 같이 진행된다.

파란 수가 현재 큐에 담긴 수이고 빨간 수가 현재의 신호 값이다.

 

total_sum =0, input_num =1
1 3 6 2 5 2  =>  0+1 <7, 1을 push

 

total_sum =1, input_num =3

1 3 6 2 5 2  => 1+3 <7, 3을 push

 

total_sum =4, input_num =6

1 3 6 2 5 2  => 4+6>7, 1을 pop

 

total_sum =3, input_num =6

1 3 6 2 5 2  => 3+6>7,  3을 pop

 

total_sum =0, input_num =6

1 3 6 2 5 2  => 0+6 <7,  6을 push

 

total_sum =6, input_num =2

1 3 6 2 5 2  => 6+2>7, 6을 pop

 

total_sum =0, input_num =2

1 3 6 2 5 2  => 0+2 <7, 2를 push

 

total_sum =2, input_num =5

1 3 6 2 5 2  => 2+5=7, 카운트, 5는 push, 2는 pop

 

total_sum =5, input_num =2

1 3 6 2 5 2  => 5+2=7, 카운트, 5는 pop, 2는 push

 

 

신호들은 적어도 한 번은 큐에 push 되고 다시 pop 될 수 있으므로 시간 복잡도는 O(2N)이다.

 

 

코드