기록방

👉 문제링크 1059번: 좋은 구간 [9, 10], [9, 11], [9, 12], [10, 11], [10, 12] www.acmicpc.net 🔸 문제 분석 🔸 l개의 배열 S의 원소를 포함하지 않고, n은 포함하는 범위( [a,b] )의 경우의 수를 출력한다. 배열 원소를 n과 하나씩 비교해서 범위를 찾는다. 원소가 n보다 작고 기존의 a보다 크거나 같으면, a에 저장한다. 원소가 n보다 크고 기존의 b보다 작거나 같으면, b에 저장한다. 만약 원소가 n과 같다면, 범위가 생길 수 없으므로 0을 출력하고 종료한다. a부터 b중에 n을 포함하는 범위의 수를 세고 출력한다. 🔸 코드 🔸 import java.io.BufferedReader; import java.io.IOException; import..

👉 문제링크 11004번: K번째 수 수 N개 A1, A2, ..., AN이 주어진다. A를 오름차순 정렬했을 때, 앞에서부터 K번째 있는 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 🔸 문제 분석 🔸 입력받은 N개의 수를 오름차순으로 정렬했을때 K번재 수를 출력한다. N이 최대 5,000,000(5백만)이므로, O(nlogn)은 약 3천만이 나온다. 일반적인 정렬 알고리즘의 평균 시간 복잡도가 O(nlogn)이므로, 제한시간 2초안에 든다. 🔸 코드 🔸 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Arrays; import java...

👉 문제링크 6996번: 애너그램 첫째 줄에 테스트 케이스의 개수(

👉 문제링크 10989번: 수 정렬하기 3 첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 10,000보다 작거나 같은 자연수이다. www.acmicpc.net 🔸 문제 분석 🔸 중복 가능한 n개의 수가 10,000,000개 이하로 입력되면 오름차순 정렬 후 출력한다. O(n^2) 일때, 100,000,000,000,000(백 조) 이므로 제한시간 3초를 넘기게 된다. 일반적인 Arrays.sort()는 평균 O(nlogn)이지만, 최악의 경우 O(n^2)이 나온다. 이 문제는 입출력 속도를 빠르게 하면 아슬아슬하게 통과는 가능하다. 카운팅 정렬을 사용해야한다. 입력되는 숫자를 인덱스로, 카운트를 진행하고 출력한다. 🔸 코드 🔸..

👉 문제링크 1015번: 수열 정렬 P[0], P[1], ...., P[N-1]은 0부터 N-1까지(포함)의 수를 한 번씩 포함하고 있는 수열이다. 수열 P를 길이가 N인 배열 A에 적용하면 길이가 N인 배열 B가 된다. 적용하는 방법은 B[P[i]] = A[i]이다. 배열 A가 주 www.acmicpc.net 🔸 문제 분석 🔸 입력된 배열의 숫자들이 정렬됐을때 어느 인덱스로 가는지 출력한다. 🔸 코드 🔸 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Arrays; import java.util.StringTokenizer; public class Main..