import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Solution { static int[][] data; static int[][] temp; public static void main(String[] args) throws Exception { BufferedReader sc = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer t = new StringTokenizer(sc.readLine()); int n = Integer.parseInt(t.nextToken()); int k = Integer.parseInt(t.nextToken()); data = new int[n][2]; temp = new int[n][2]; t = new StringTokenizer(sc.readLine()); for (int i = 1; i <= n; i++) { data[i - 1][0] = Integer.parseInt(t.nextToken()); data[i - 1][1] = i; } mergeSort(0, n - 1); while (k > 0) { t = new StringTokenizer(sc.readLine()); int x = Integer.parseInt(t.nextToken()); int y = Integer.parseInt(t.nextToken()); int z = Integer.parseInt(t.nextToken()); System.out.println(q(x, y, z)); k--; } sc.close(); } private static int q(int i, int j, int k) { int c = 0; for (int x = 0; x < data.length; x++) { if (data[x][1] >= i && data[x][1] <= j) { c++; if (c == k) { return (data[x][0]); } } } return 0; } private static void mergeSort(int low, int high) { if (low < high) { int mid = low + (high - low) / 2; mergeSort(low, mid); mergeSort(mid + 1, high); merge(low, mid, high); } } private static void merge(int low, int mid, int high) { for (int i = low; i <= high; i++) { temp[i][0] = data[i][0]; temp[i][1] = data[i][1]; } int i = low; int j = mid + 1; int k = low; while (i <= mid && j <= high) { if (temp[i][0] < temp[j][0]) { data[k][0] = temp[i][0]; data[k][1] = temp[i][1]; i++; } else { data[k][0] = temp[j][0]; data[k][1] = temp[j][1]; j++; } k++; } while (i <= mid) { data[k][0] = temp[i][0]; data[k][1] = temp[i][1]; i++; k++; } } }
[백준 알고리즘 풀이] 7469번 K번째 숫자
쉬운 문제 같지만 Q함수 내에서 매번 정렬한다면 속도가 나오지 않을 것이다. 전체 배열을 한번 정렬할때 원래 index 값을 달아놓으면, 매 Q함수 내에서 해당 i, j 범위 내 K번째를 찾는 것으로 해결한다.
Subscribe to:
Post Comments (Atom)
-
음성 인공지능 분야에서 스타트업이 생각해볼 수 있는 전략은 아마 다음과 같이 3가지 정도가 있을 것이다: 독자적 Vertical 음성 인공지능 Application 구축 기 음성 플랫폼을 활용한 B2B2C 형태의 비지니스 구축 기 음성 플랫폼...
-
개발자 컨퍼런스같은 것도 방문한게 언제인지 까마득합니다. 코로나로 왠지 교류가 많이 없어졌습니다. 패스트캠퍼스로부터 좋은 기회를 얻어 강연을 하나 오픈하였습니다. 제가 강연에서 주로 다룰 내용은, 인터넷 역사 이래 발전해온 서버 사이드 기술들에 대해 ...
-
패밀리 세단으로 새차 구입은 좀 무리일 것 같아서, 중고로 하나 얻어왔습니다. 중고차라고 티 내는건지 :-) 시거잭에 전원이 안들어오더군요. 요즘 참 세상 좋아졌다고 생각드는게, 유튜브에서 시거잭 전원 불량에 대한 단서를 얻었습니다. 바로 퓨즈가 나가...
-
무한 집합의 크기 Cardinality , 즉 원소의 개수를 수학에서는 '농도'라고 말한다. 유한 집합의 크기는 그대로 원소의 개수 이지만, 무한 집합의 경우는 원소의 개수를 낱낱이 셈하는 것은 불가능하기 때문에 '농도'라...
No comments:
Post a Comment