푸으름

✏️ 문제 링크 https://www.acmicpc.net/problem/1377 1377번: 버블 소트 첫째 줄에 N이 주어진다. N은 500,000보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 A[1]부터 A[N]까지 하나씩 주어진다. A에 들어있는 수는 1,000,000보다 작거나 같은 자연수 또는 0이다. www.acmicpc.net ✏️ 문제 설명 ✏️ 문제 풀이 false일 때 출력되기 위해서는 버블 정렬 중 swap이 한 번도 일어나지 않은 루프가 언제인지 알아내는 게 핵심 이중 for문을 다 돌리기에는 N의 값이 크기 때문에 버블 정렬로 풀면 시간 초과가 발생할 수 있음 vector를 생성해 pair쌍으로(입력값, 인덱스) push해주고 sort알고리즘을(O(nlogn)) 통해 v..

✏️ 문제 링크 https://www.acmicpc.net/problem/11286 11286번: 절댓값 힙 첫째 줄에 연산의 개수 N(1≤N≤100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 0이 아니라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0 www.acmicpc.net ✏️ 문제 설명 ✏️ 문제 풀이 큐 중에서도 우선순위 큐를 이용해서 푸는 문제 우선순위 큐를 생성하고 compare구조체를 만들어서 조건에 맞게 출력하도록 해야함 1. x가 0인 경우 if(큐가 비어있지 않다면) 절댓값이 가장 작은 값을 => 같은 게 있다면 음수를 출력 그리고 그 값을 제거 if(큐가 비어있다면) 0을 출력 2. x가 0이 아닌 경우 : x를..

✏️ 문제 링크 https://www.acmicpc.net/problem/17298 17298번: 오큰수 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다. www.acmicpc.net ✏️ 문제 설명 ✏️ 문제 풀이 ※ 스택을 이용해서 푸는 문제 ※ ● 스택에 새로 들어오는 수가 top존재하는 수보다 크면 그 수는 오큰수가 된다 ● 오큰수를 구한 후 수열에서 오큰수가 존재하지 않는 숫자에 -1을 출력해야 한다 ● 스택이 채워져 있고 A[index] > A[top]라면 pop한 인덱스를 이용하여 정답 수열에 오큰수를 저장 ● 현재 인덱스를 스택에 push하고 다음 인덱스로 ..

백준 1874번 스택 수열 https://www.acmicpc.net/problem/1874 1874번: 스택 수열 1부터 n까지에 수에 대해 차례로 [push, push, push, push, pop, pop, push, push, pop, push, push, pop, pop, pop, pop, pop] 연산을 수행하면 수열 [4, 3, 6, 8, 7, 5, 2, 1]을 얻을 수 있다. www.acmicpc.net ● 스택의 후입선출 구조를 이용하는 문제 ● 현재 수열 값 >= 자연수 while(수열 값>=자연수){ stack.push(자연수); 자연수++; result.push_back('+'); } stack.pop(); result.push_back('-'); → 만약 현재 수열 값이 4이고 자..