x, y 좌표가 n개 주어진다고 하자. x를 기준으로 오름차순 정렬하는데 만약 x가 같다면 y를 기준으로 오름차순 정렬시켜라 라고 하는 문제가 있다면 정렬 기준을 설정해주어야한다. Comparable 인터페이스는 이러한 x, y 값을 가지는 객체간의 비교를 가능하게 해준다. import java.util.*; class Coords implements Comparable { public int x, y; Coords(int x, int y) { this.x = x; this.y = y; } // x값에 의해 정렬하고, x값이 같을 경우 y값에 의해 정렬한다. // CompareTo에서 양수를 리턴 : 두 객체의 자리가 바뀐다. // 음수 or 0을 리턴 : 두 객체의 위치가 바뀌지 않는다. @Overri..
문제 출처 : https://www.acmicpc.net/problem/2108 2108번: 통계학 첫째 줄에 수의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 단, N은 홀수이다. 그 다음 N개의 줄에는 정수들이 주어진다. 입력되는 정수의 절댓값은 4,000을 넘지 않는다. www.acmicpc.net 풀이 ) 내 블로그 카테고리에 시간복잡도 O(N)을 가진 정렬 풀이법이 있다. 바로 생각났다. 수의 크기보다 N이 크다.거기다가 구해야하는 문제들을 보니 카운팅 정렬 알고리즘으로 풀면 괜찮을 것 같다. import java.util.*; import java.io.*; class Main { // 1 2 4 4 6 -> 0 1 1 0 2 0 1 (cntArr[4] = 2) public String..
basic : Scanner + Arrays.sort Scanner는 시간을 많이 잡아먹는데다, Arrays.sort는 평균 O(nlogn) 지만 최악의 경우 O(n2) 까지도 올라간다. =>BufferedReader, BufferedWriter(or StringBuilder) + Counting Sort 다만, Counting Sort가 많이 쓰이지 않는 이유는 K가 정렬할 수들 중에서 가장 큰 값을 의미하는데,만약 K가 N보다 작은 수이면 O(N)이 되지만, K가 N보다 매우 큰 수라면 시간복잡도가 엄청 커질 수 있다.예를 들어 10개 숫자 정렬하는데 가장 큰 숫자가 100일 경우엔 O(N^2)가 되고, 1000이라면 O(N^3)이 된다.즉, 정렬할 수들의 최대값에 영향을 받는 알고리즘이다. 따라서 ..
https://www.inflearn.com/course/%EC%9E%90%EB%B0%94-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EB%AC%B8%EC%A0%9C%ED%92%80%EC%9D%B4-%EC%BD%94%ED%85%8C%EB%8C%80%EB%B9%84/dashboard 자바(Java) 알고리즘 문제풀이 : 코딩테스트 대비 - 인프런 | 강의 자바(Java)로 코딩테스트를 준비하시는 분을 위한 강좌입니다. 코딩테스트에서 가장 많이 출제되는 Top 10 Topic을 다루고 있습니다. 주제와 연동하여 기초문제부터 중급문제까지 단계적으로 구성 www.inflearn.com 문제 4 : 캐시메모리 사용 규칙이 LRU 알고리즘(Least Recently Used)을 따른다. 만..
https://www.inflearn.com/course/%EC%9E%90%EB%B0%94-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EB%AC%B8%EC%A0%9C%ED%92%80%EC%9D%B4-%EC%BD%94%ED%85%8C%EB%8C%80%EB%B9%84/dashboard 자바(Java) 알고리즘 문제풀이 : 코딩테스트 대비 - 인프런 | 강의 자바(Java)로 코딩테스트를 준비하시는 분을 위한 강좌입니다. 코딩테스트에서 가장 많이 출제되는 Top 10 Topic을 다루고 있습니다. 주제와 연동하여 기초문제부터 중급문제까지 단계적으로 구성 www.inflearn.com 문제 1 : 숫자 n과 해당 n의 갯수만큼 숫자가 주어진다. 해당 숫자들을 오름차순으로 정렬해서 출력하..
문제 : 첫 줄에 입력된 영어 대문자가 두 번째 줄에 입력된 영어 대문자 순서대로 포함되어 있으면 YES, 아니면 NO 입력예제 CBA CBDAGE 출력예제 YES import java.io.BufferedReader; import java.io.InputStreamReader; import java.io.BufferedWriter; import java.io.OutputStreamWriter; import java.io.IOException; import java.util.LinkedList; import java.util.Queue; class Main { public String solution(String e, String n) { String answer = "YES"; Queue Q = new..
https://www.inflearn.com/course/%EC%9E%90%EB%B0%94-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EB%AC%B8%EC%A0%9C%ED%92%80%EC%9D%B4-%EC%BD%94%ED%85%8C%EB%8C%80%EB%B9%84/dashboard 자바(Java) 알고리즘 문제풀이 : 코딩테스트 대비 - 인프런 | 강의 자바(Java)로 코딩테스트를 준비하시는 분을 위한 강좌입니다. 코딩테스트에서 가장 많이 출제되는 Top 10 Topic을 다루고 있습니다. 주제와 연동하여 기초문제부터 중급문제까지 단계적으로 구성 www.inflearn.com Queue 줄을 지어 순서대로 처리된다. FIFO의 형태를 가진다. import java.util.Li..
