기록방

👉 문제링크 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해서 스택의 가장 위 값을 확인한다...

👉 문제링크 11003번: 최솟값 찾기 N개의 수 A1, A2, ..., AN과 L이 주어진다. Di = Ai-L+1 ~ Ai 중의 최솟값이라고 할 때, D에 저장된 수를 출력하는 프로그램을 작성하시오. 이때, i ≤ 0 인 Ai는 무시하고 D를 구해야 한다. www.acmicpc.net 🔸 문제 분석 🔸 일정 범위 안에서 최소값을 구하는 문제이므로 슬라이딩 윈도우와 정렬을 사용해야 한다. 윈도우의 크기는 최소값을 구하는 범위가 i-L+1 ~ i 이므로 L로 생각한다. 일반적으로 정렬은 O(nlogn)인데 N,L 의 범위가 5,000,000까지 이므로 정렬은 사용하지 못한다. O(n)의 시간 복잡도로 해결해야되므로 윈도우를 덱(deque)로 구현하여 정렬 효과를 낸다. 덱은 (인덱스, 숫자) 형태의 노드..

👉 문제링크 1417번: 국회의원 선거 첫째 줄에 후보의 수 N이 주어진다. 둘째 줄부터 차례대로 기호 1번을 찍으려고 하는 사람의 수, 기호 2번을 찍으려고 하는 수, 이렇게 총 N개의 줄에 걸쳐 입력이 들어온다. N은 50보다 작거나 같 www.acmicpc.net 🔸 문제 분석 🔸 배열의 첫째자리가 최대값이 되도록 다른 인덱스에서 값을 가져오는데 드는 최소 횟수를 출력한다. 🔸 코드 🔸 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; public class Main { public static void main(String[] args) throws IOException { Buff..

👉 문제링크 10815번: 숫자 카드 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10, www.acmicpc.net 🔸 문제 분석 🔸 -10,000,000 ~ 10,000,000 중에서 n개의 수가 입력된다. 또 m개의 수가 입력되면, 이전에 입력된 것인지 출력한다. 🔸 코드 🔸 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main ..

👉 문제링크 1253번: 좋다 첫째 줄에는 수의 개수 N(1 ≤ N ≤ 2,000), 두 번째 줄에는 i번째 수를 나타내는 Ai가 N개 주어진다. (|Ai| ≤ 1,000,000,000, Ai는 정수) www.acmicpc.net 🔸 문제 분석 🔸 N개의 수에서 서로 다른 두 수로 만들 수 있는 수의 개수를 출력한다. 인덱스가 다르면 값이 같아도 다른 수이다. 시간 복잡도 N의 개수가 최대값 2,000이라 가정해도 좋은 수 하나를 찾는 알고리즘의 시간 복잡도는 N^2보다 작아야 한다. (N^2 를 사용하면 다시 N번 반복해서 최종 시간 복잡도는 N^3가 되기 때문) 좋은 수 하나를 찾는 알고리즘은 최소 O(nlongn)이어야 한다. 정렬과 투 포인터 알고리즘 사용 단, 정렬된 데이터에서 자기 자신을 좋은..