본문 바로가기

Coding Test

 (131)
[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..
[Java] 3단계. 커트라인 [25305번] https://www.acmicpc.net/problem/25305예제 입력15 2100 76 85 93 98예제 출력198문제 접근입력첫번째 줄응시자수 N (1 상을 받는 사람 수 k (1 ≤ k ≤ N)두번째 줄각 학생의 점수 x (0 ≤ x ≤ 10000)출력상을 받는 커트라인 점수 출력문제 해결응시자수는 최대 999명으로 시간의 복잡도가 O(n^2)인 정렬 알고리즘도 사용 가능정렬 후 N - k번째 점수 출력→ Arrays.sort는 원시타입으로 내림차순 정렬이 안되기 때문 기존 풀이 [메모리 : 14592KB / 시간 : 112ms]public static void main(String[] args) throws IOException { BufferedReader br = new Buffe..
[Java] 키 순서 [2458번] https://www.acmicpc.net/problem/2458예제 입력16 61 53 45 44 24 65 2예제 출력11예제 입력26 71 31 53 45 44 24 65 2예제 출력22예제 입력36 31 22 34 5예제 출력30문제 접근입력학생의 수 N, 두 학생을 비교한 횟수 MM개의 줄에 작은 학생(a) 큰 학생(b)출력자신의 키가 몇 번째인지 알 수 있는 학생의 수 출력문제 해결시작이 주어지지 않았으므로 플로이드 워셜 문제배열의 자기자신은 0, 나머지는 무한대로 초기화플로이드 워셜의 점화식을 사용a학생이 b학생보다 작거나 b학생이 a학생이 작다면 키를 비교할 수 있다는 의미배열[a][b] check == N(학생 수)와 같다면 모든 학생과 직,간접적으로 연결이 되어있다는 의미로 자신의 키가..

티스토리툴바