기록방

👉 문제링크 4158번: CD 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 상근이가 가지고 있는 CD의 수 N, 선영이가 가지고 있는 CD의 수 M이 주어진다. N과 M은 최대 백만이다. 다음 줄 www.acmicpc.net 🔸 문제 분석 🔸 n과 m이 입력되면 n개의 수와 m개의 수가 입력되고 겹치는 숫자의 개수를 출력한다. 오름차순 정렬된 수가 입력되므로 투 포인터 알고리즘을 사용해 풀이한다. 0 0이 입력 될 때까지 반복한다. 🔸 코드 🔸 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Scanner; import ..

👉 문제링크 23253번: 자료구조는 정말 최고야 위 그림처럼 책이 쌓여 있으므로, 첫 번째 더미 - 두 번째 더미 - 첫 번째 더미 - 두 번째 더미 순으로 꺼내면 책 번호순으로 나열할 수 있다. www.acmicpc.net 🔸 문제 분석 🔸 여러개의 스택형식 책더미에서 번호 순서대로 책을 뽑을 수 있는지 판별한다. 스택과 책의 개수가 최대 20만이므로 pop을 반복해서 탐색하는건 시간초과가 난다. 각 책 무더기가 내림차순으로 정렬되어 있으면 문제 조건을 만족하므로, 정렬을 확인한다. 🔸 코드 🔸 import sys input = sys.stdin.readline n, m = map(int, input().split()) for _ in range(m): book = int(input()) books ..

👉 문제링크 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]이다. 배열 순회가 끝나도..