PS
BOJ 11004 K번째 수 [Java]
BOJ 11004 K번째 수 - 문제 링크 https://www.acmicpc.net/problem/11004 - 문제 해설 메모리와 시간 제한이 여유로워서 sort 메소드를 이용하여 쉽게 풀 수 있는 문제이다. sort 메소드말고 다른 방식으로 풀 경우 quick sort를 이용해서 풀 수도 있을 것 같다. 이 문제를 풀면서 처음에 한 가지 간과한게 있다면, BufferedReader와 StringTokenizer를 이용하여 한 줄씩 입력 받아 토큰으로 만들었기때문에, 18줄의 코드처럼 StringTokenizer를 한 줄마다 다시 만들어줄 필요가 있다. - 코드 보기 import java.io.*; import java.util.*; public class Main { static int n; sta..
BOJ 10989 수 정렬하기 3 [Java]
BOJ 10989 수 정렬하기 3 - 문제 링크 https://www.acmicpc.net/problem/10989 - 문제 해설 N이 10,000,000 이하의 자연수이기 때문에 sort를 쓰면 메모리 초과가 난다는 사실을 인지해야한다. 정렬해야하는 숫자들이 10,000 이하라는 사실에서 counting sort를 쓰면 되겠다는 힌트를 얻었다. cnt[i]를 1-10000 범위의 자연수 i가 입력된 횟수라고 설정하고 구현해주면 된다. 출력할 때는 cnt[i] > 0 이 아닌 경우에는 i가 입력되지 않은 경우이니 제외한다. - 코드 보기 import java.io.*; public class Main { static int n; public static void main(String[] args) thr..
BOJ 10825 국영수 [Java]
BOJ 10825 국영수 - 문제 링크 https://www.acmicpc.net/problem/10825 - 문제 해설 문제에서 주어진 조건대로 정렬해주는 compare 메소드를 재정의해주는 방식으로 풀었다. return 값에 따라 어떻게 정렬되는지를 신경써주면 쉽게 해결할 수 있는 문제이다. - String 클래스의 compareTo와 Integer.compare()는 왼쪽에 오는 것이 작으면 -1을, 같으면 0을, 왼쪽의 것이 더 크면 1을 리턴한다. - Comparator의 compare 메소드의 경우에는 만약 인자로 a, b를 받았다고 하자. 음수를 리턴할 경우 a가 b보다 왼쪽에, 양수를 리턴 받을 경우 b가 a 왼쪽에 위치하게 된다. 0인 경우는 a와 b가 같은 경우이다. 위 내용을 바탕으로..
BOJ 10814 나이순 정렬
BOJ 10814 나이순 정렬 자바를 이용하여 처음으로 코딩테스트 문제를 풀어보았다. - 문제 링크 https://www.acmicpc.net/problem/10814 - 문제 해설 정렬 알고리즘을 이용한 간단한 문제이다. 해결해야 하는 점은 나이가 같을 시에 순서가 뒤바뀌지 않도록 해야하는 것이다. compare 메소드를 재정의하여 풀었는데, 나이끼리만 비교하여 나이가 같을 시에 입력된 순서대로 정렬되도록 하였다. - 코드 보기 import java.io.*; import java.util.*; public class Main { static int n; public static void main(String[] args) throws IOException { BufferedReader br = new..
BOJ 11052 카드 구매하기
boj 11052 카드 구매하기 - 문제 링크 https://www.acmicpc.net/problem/11052 - 문제 해설 DP가 작은 문제부터 쌓아나가서 구하고자 하는 값을 구하는 알고리즘임을 생각하면 쉽게 접근 방법을 찾을 수 있다. 나는 보통 DP로 문제를 풀 때 D[i]를 어떻게 나눌지를 생각하는 편이다. D[i]를 i개의 카드를 사는 금액의 최댓값이라고 지정하자. 그러면 아래와 같이 쪼갤 수 있다. D[i-1] + P[1] : 카드 1개가 들어있는 팩의 구매 값 + i-1개의 카드를 구매한 최댓값 D[i-2] + P[2] : 카드 2개가 들어있는 팩의 구매 값 + i-2개의 카드를 구매한 최댓값 . . . D[0] + P[i] : 카드 i개가 들어있는 팩의 구매 값 + 0개의 카드를 구매한..