문제 24511번: queuestack 첫째 줄에 queuestack을 구성하는 자료구조의 개수 $N$이 주어진다. ($1 \leq N \leq 100\,000$) 둘째 줄에 길이 $N$의 수열 $A$가 주어진다. $i$번 자료구조가 큐라면 $A_i = 0$, 스택이라면 $A_i = 1$이다. 셋째 줄 www.acmicpc.net 풀이 처음에는 리스트를 이용해 큐스택을 직접 구현하여 해결하려 했지만, 당연하게도 시간 초과가 발생했다. 모든 요소에서 계산을 처리하면 시간복잡도가 O(NxM)이 되는데, 문제에서 주어진 범위에 따라 N = 10만, M이 10만일 때는 100억의 계산이 필요하기 때문이다. 대신 큐와 스택의 특성을 이용해 계산하는 방법을 생각해 보아야한다. 먼저 스택은 현재 삽입된 원소가 다시 ..

문제 1644번: 소수의 연속합 첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 4,000,000) www.acmicpc.net 풀이 에라토스테네스의 체를 활용하여 소수 판정을 먼저 수행하고, 투 포인터를 이용하여 합이 입력받은 값이 되는 경우를 세어주면 된다. 에라토스테네스의 체는 범위 내에서 소수의 배수는 모두 지워가며 소수를 구하는 방법이다. 다음의 그림을 보면 쉽게 이해할 수 있다. 먼저 입력받은 범위까지의 소수를 구하고, 그 소수를 리스트에 저장한다. 이 리스트를 시작과 끝을 가리키는 start와 end 포인터를 활용하여 탐색한다. 두 포인터는 초기에 0으로 초기화되며, 두 포인터 사이의 값의 합과 찾으려는 값을 비교하면서 탐색한다. 만약 현재까지의 누적 합이 찾으려는 값보다 작다면 end 포..

문제 12789번: 도키도키 간식드리미 인하대학교 학생회에서는 중간, 기말고사 때마다 시험 공부에 지친 학우들을 위해 간식을 나눠주는 간식 드리미 행사를 실시한다. 승환이는 시험 기간이 될 때마다 간식을 받을 생각에 두근두 www.acmicpc.net 풀이 대기열의 왼쪽에 있는 공간을 스택으로 생각하여 풀이하면 된다. 스택은 선입후출 구조이므로 왼쪽 공간에 먼저 들어간 번호는 나중에 나온다. 현재 도시락을 받을 번호를 나타내는 변수 cur을 1로 초기화하고 선언한다. 입력받은 대기열을 앞에서부터 순회하면서 cur과 같은 번호를 만나면 도시락을 받은 것으로 처리하고, cur을 1 증가시켜서 다음으로 받을 사람을 나타낸다. 만약 cur과 다른 번호를 만난 경우에는 스택에 추가한다. 이 때, 현재 스택에서 가..

문제 1806번: 부분합 첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다. www.acmicpc.net 풀이 시작과 끝을 가리키는 start와 end 포인터를 활용하여 탐색한다. 두 포인터는 초기에 0으로 초기화되며, 두 포인터 사이의 값의 합과 찾으려는 값을 비교하면서 탐색한다. 만약 현재까지의 누적 합이 찾으려는 값보다 작다면 end 포인터를 뒤로 이동시킨다. 만약 end 포인터가 이미 배열의 끝까지 도달했다면 반복문을 종료한다. 누적 합이 찾으려는 값보다 크거나 같다면 현재 구간의 길이를 갱신하고 start 포인터를 뒤로 이동시킨다. 코드..

문제 2470번: 두 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 1,000,00 www.acmicpc.net 풀이 투 포인터 알고리즘으로 해결할 수 있다. 입력받은 용액을 오름차순으로 정렬한다. 시작과 끝을 가르키는 두 포인터를 선언하여 반복문을 통해 탐색한다. 두 포인터가 가르키는 용액의 합이 0에 가까워질 때마다 결과를 갱신해준다. 만약 합이 0보다 작다면 시작 포인터를 뒤로 움직이고, 0보다 크다면 끝 포인터를 앞으로 움직여준다. 코드 import kotlin.math.* fun main() { val br = System...