기록방

👉 문제링크 2750번: 수 정렬하기 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수 주어진다. 이 수는 절댓값이 1,000보다 작거나 같은 정수이다. 수는 중복되지 않는다. www.acmicpc.net 🔸 문제 분석 🔸 N의 최대 범위가 1,000으로 매우 작기 때문에 O(n^2) 시간 복잡도 알고리즘으로 풀 수 있다 버블 정렬의 시간 복잡도가 O(n^2)이므로 버블 정렬 알고리즘을 이용해 정렬해도 시간 복잡도 안에서 문제를 해결할 수 있다 🔸 코드 🔸 import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(Sys..

👉 문제링크 11286번: 절댓값 힙 첫째 줄에 연산의 개수 N(1≤N≤100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 0이 아니라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0 www.acmicpc.net 🔸 문제 분석 🔸 n의 범위가 100,000이므로 O(nlogn) 시간 복잡도 알고리즘으로 풀 수 있다. 데이터가 삽입 될 때마다 절댓값으로 정렬되는 우선순위 큐를 사용한다. 🔸 코드 🔸 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.PriorityQueue; public class..

👉 문제링크 2164번: 카드2 N장의 카드가 있다. 각각의 카드는 차례로 1부터 N까지의 번호가 붙어 있으며, 1번 카드가 제일 위에, N번 카드가 제일 아래인 상태로 순서대로 카드가 놓여 있다. 이제 다음과 같은 동작을 카드가 www.acmicpc.net 🔸 문제 분석 🔸 큐에 1개의 원소가 남을때까지 계산을 반복한다. 맨 앞 원소를 제거한다(poll). 다시 맨 앞 원소를 빼서 가장 아래에 넣는다(add(poll)). 마지막 원소를 출력한다. 🔸 코드 🔸 import java.util.LinkedList; import java.util.Queue; import java.util.Scanner; public class Main { public static void main(String[] args) ..

👉 문제링크 17298번: 오큰수 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다. www.acmicpc.net 🔸 문제 분석 🔸 배열arr을 입력받으면, 한 인덱스 i의 오른쪽으로 처음 등장하는 arr[i] 보다 큰 값(오큰수)을 정답 배열 answer[i]에 저장한다. n이 1,000,000(백만)이므로 인덱스마다 오른쪽 탐색을 진행하면 O(n^2)로 시간초과가 난다. 스택을 이용해서 오큰수를 찾지 못한 인덱스만 스택에 남기며 계산을 진행한다. 스택의 arr[top]이 push하려는 arr[i]보다 작다면, 인덱스 top의 오큰수는 arr[i]이다. 배열 순회가 끝나도..

👉 문제링크 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 🔸 문제 분석 🔸 스택의 pop, push 연산과 후입 선출 개념을 정확하게 알고 있는지 묻는 문제이다. 스택에 넣는 자연수 값은 오름 차순 정렬이다. 현재 수열 값 >= 자연수 자연수가 현재 수열 값과 같아질 때 까지 자연수를 1증가시키며 스택에 push한다. 마지막은 출력하기 위해 1번 pop한다. 현재 수열 값 < 자연수 pop해서 스택의 가장 위 값을 확인한다...