Coding Test/Step13. 정렬 (11) 썸네일형 리스트형 [Java] 11단계. 좌표 압축 [18870번] https://www.acmicpc.net/problem/18870예제 입력152 4 -10 4 -9예제 출력12 3 0 3 1예제 입력261000 999 1000 999 1000 999예제 출력21 0 1 0 1 0문제 접근가장 작은 값을 0으로 설정하고 그 다음 작은 값을 1로 설정하면서 멀리 떨어진 좌표들을 0~?까지 압축하는 것으로 예상 됨동일한 값이 주어진다면 같은 좌표로 취급N은 최대 100만개의 숫자가 주어질 수 있으므로 시간 복잡도가 O(N^2)인 알고리즘을 선택 시 1조번 연산(10000초)가 되어 시간 초과가 나올 것출력 ⇒ 압축한 좌표를 공백으로 출력문제 해결오름차순 정렬 필요선택, 삽입, 버블 정렬 사용 시 시간 초과최소 O(NlogN)이상의 알고리즘 사용 필요 (Heap, Quic.. [Java] 10단계. 나이순 정렬 [10814번] https://www.acmicpc.net/problem/10814예제 입력1321 Junkyu21 Dohyun20 Sunyoung예제 출력120 Sunyoung21 Junkyu21 Dohyun문제 접근입력회원수 N (1 ≤ N ≤ 10,000)N개의 줄만큼 회원의 나이와 이름이 공백으로 가입한 순서대로 입력→ 이름 : 알파벳 대소문자→ 나이 : 1 ~ 200출력나이 오름 차순나이가 같을 경우 가입 순서한 줄에 한 명씩 나이와 이름을 공백으로 출력문제 해결가입한 순서로 정렬도 하기 때문에 입력 받은 순서대로 인덱스가 필요회원 클래스를 생성하여 index, age, name을 매개 변수로 가지고 Comparable을 상속 받아 정렬기존 풀이 [메모리 : 53864 KB / 시간 : 632 ms]static.. [Java] 9단계. 단어 정렬 [1181번] https://www.acmicpc.net/problem/1181예제 입력113butiwonthesitatenomorenomoreitcannotwaitimyours예제 출력1iimitnobutmorewaitwontyourscannothesitate문제 접근짧은 길이부터 출력 + 같은 길이라면 사전 순 출력중복된 단어는 1번만 출력최대 길이는 20,000으로 시간복잡도가 O(n^2) 알고리즘일 경우 4억번의 연산(4초)로 시간 초과 예상문제 해결중복 단어가 있기 때문에 Set으로 중복 제거 또는 Stream을 이용한 배열 중복 제거 후 정렬정렬 시 최소 O(nlogn) 방식 사용단순 길이 정렬이 아니라, 같은 길이일 경우 사전 순 출력을 해야 하기 때문에 클래스를 생성 Comparable 상속 → 길이.. [Java] 8단계. 좌표 정렬하기2 [11651번] https://www.acmicpc.net/problem/11651예제 입력150 41 21 -12 23 3예제 출력11 -11 22 23 30 4문제 접근입력좌표의 개수 N (1 ≤ N ≤ 100,000)N개의 줄만큼 x좌표와 y좌표출력좌표 정렬 결과 출력문제 해결이전 문제와 동일한 문제이나, y좌표를 오름차순 정렬y좌표가 동일하다면 x좌표를 오름차순 정렬이번에는 클래스가 아닌 2차원 배열로 풀이기존 풀이 [메모리 : 81944 KB / 시간 : 812 ms]public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); .. [Java] 7단계. 좌표 정렬하기 [11650번] https://www.acmicpc.net/problem/11650예제 입력153 41 11 -12 23 3예제 출력11 -11 12 23 33 4문제 접근입력좌표의 개수 N (1 ≤ N ≤ 100,000)N개의 줄만큼 x와 y의 좌표출력좌표 정렬 결과를 출력문제 해결x좌표를 오름차순으로 정렬x좌표가 동일하다면 y좌표를 비교하여 오름차순 정렬Coordinate 클래스를 생성하여 Comparable 인터페이스를 상속 받아 정렬 기준 설정하여 풀이기존 풀이 [메모리 : KB / 시간 : ms]static class Coordinate implements Comparable { int x; int y; public Coordinate(int x, int y){ this.x = x;.. [Java] 6단계. 소트인사이드 [1427번] https://www.acmicpc.net/problem/1427예제 입력12143예제 출력14321예제 입력2999998999예제 출력2999999998예제 입력361423예제 출력364321예제 입력4500613009예제 출력4965310000문제 접근입력정렬하려는 수 N (N ≤ 1,000,000,000)출력자리수를 내림차순 정렬문제 해결N의 수가 10억이긴 하지만 이것은 String으로 실질적으로 10억더라도 10자리밖에 되지 않음문자열을 char 배열로 바꿔서 정렬한 뒤 맨 뒤에서부터 출력기존 풀이 [메모리 : 14244 KB / 시간 : 96 ms]public static void main(String[] args) throws IOException { BufferedReader br =.. [Java] 5단계. 수 정렬하기3 [10989번] https://www.acmicpc.net/problem/10989예제 입력1105231423517예제 출력11122334557문제 접근시간 제한 : Java 11 → 3초입력입력될 숫자 N(1 ≤ N ≤ 10,000,000)N개의 줄만큼 숫자 입력(10,000이하의 자연수, 중복 가능)출력오름차순으로 정렬 결과 출력문제 해결시간복잡도가 O(NlogN)인 알고리즘으로 풀게 되면 1,000만 * 24 = 2.4억 ⇒ 2.4초 소요Arrays.sort()를 사용하여 풀었을 때 문제가 통과되기는 하지만 이것은 Counting Sort를 사용해서 푸는 것을 의도한 것으로 예상 됨숫자의 값이 1 ~ 10,000밖에 되지 않기 때문에 메모리적으로도 시간적으로도 더 좋을 것으로 예상Dual-pivot Quick So.. [Java] 4단계. 수 정렬하기2 [2751번] https://www.acmicpc.net/problem/2751예제 입력1554321예제 출력112345문제 접근입력입력될 숫자 N (1 ≤ N ≤ 1,000,000)N개의 숫자 입력출력오름차순으로 정렬문제 해결N의 최댓값이 100만이기 때문에 시간 복잡도가 O(n^2)의 알고리즘으로 풀게 되면 1조의 연산으로 10,000초(1억의 연산 = 1초) 소요시간 복잡도가 O(NlogN)으로 풀 경우 100만 * 20 = 2,000만 ⇒ 0.2초로 시간 제한이 문제 되지 않음Arrays.sort 또는 Collections.sort는 평균 시간의 복잡도가 O(NlogN)이므로 두 개의 정렬 중 선택기존 풀이 [메모리 : 185496 KB / 시간 : 4844 ms]public static void main(St.. 이전 1 2 다음
