두부의 코딩일기

2075번: N번째 큰 수 (acmicpc.net) 2075번: N번째 큰 수 첫째 줄에 N(1 ≤ N ≤ 1,500)이 주어진다. 다음 N개의 줄에는 각 줄마다 N개의 수가 주어진다. 표에 적힌 수는 -10억보다 크거나 같고, 10억보다 작거나 같은 정수이다. www.acmicpc.net 풀이 N*N 크기의 2차원 배열에서 N번째 큰 수를 찾으면 된다. 우선순위 큐를 사용하면 쉽게 해결할 수 있다. 기본적으로 오름차순으로 정렬되기 때문에 N번째 큰 수를 찾기 위해서는 정렬을 재정의해주어야 한다. 단순 integer형 큐이기 때문에 Collections.reverseOrder() 를 사용해서 역순으로 정렬해 주었다. 이후에 N-1번째까지 pq.poll()을 해주고, pq.poll()을 한 번 더 사용해서..

https://www.acmicpc.net/problem/10800 10800번: 컬러볼 첫 줄에는 공의 개수를 나타내는 자연수 N이 주어진다(1 ≤ N ≤ 200,000). 다음 N개의 줄 중 i번째 줄에는 i번째 공의 색을 나타내는 자연수 Ci와 그 크기를 나타내는 자연수 Si가 주어진다(1 ≤ Ci ≤ N www.acmicpc.net 풀이 공의 색깔과 크기를 비교해서 i번째 공으로 잡아먹을 수 있는 공들의 크기 합을 구하는 문제이다. 완전 탐색으로 접근하면 공의 개수가 200,000까지의 크기를 가지므로 시간 초과가 발생할 것이다. 따라서 위 문제는 누적합과 정렬을 이용해서 해결해야한다. 누적합을 사용하기 위해서는 공의 크기가 작은 순으로 정렬을 해주어야한다. public static class B..

https://www.acmicpc.net/problem/10814 10814번: 나이순 정렬 온라인 저지에 가입한 사람들의 나이와 이름이 가입한 순서대로 주어진다. 이때, 회원들을 나이가 증가하는 순으로, 나이가 같으면 먼저 가입한 사람이 앞에 오는 순서로 정렬하는 프로그램을 www.acmicpc.net 풀이 단순한 정렬 문제로 여러 가지 방법으로 해결할 수 있다. 필자는 배열을 이용하지않고 클래스 객체를 만들어서 해결했다. public static class Person implements Comparable { int age; String name; public Person (int age, String name) { this.age = age; this.name = name; } public in..

https://www.acmicpc.net/problem/1181 1181번: 단어 정렬 첫째 줄에 단어의 개수 N이 주어진다. (1 ≤ N ≤ 20,000) 둘째 줄부터 N개의 줄에 걸쳐 알파벳 소문자로 이루어진 단어가 한 줄에 하나씩 주어진다. 주어지는 문자열의 길이는 50을 넘지 않는다. www.acmicpc.net 풀이 이번 문제는 기본적인 오름차순 정렬로는 해결할 수 없기 때문에 Arrays.sort() 메서드에서 Comparator를 구현해야한다. https://sookr5416.tistory.com/151 [백준]JAVA - 1931번: 회의실배정 https://www.acmicpc.net/problem/1931 1931번: 회의실 배정 (1,4), (5,7), (8,11), (12,14) ..

https://www.acmicpc.net/problem/10815 10815번: 숫자 카드 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10, www.acmicpc.net 풀이 카운팅 정렬 형식으로 문제를 해결할 수 있지만 이분 탐색으로 분류되어 있기 때문에 이분 탐색을 이용해서 풀어보려고한다. 이분 탐색은 중간 위치 값과 목표 위치 값을 비교하면서 반으로 줄여나가는 방식인데 자바에서는 메서드 하나로 귀찮은 이분 탐색 코드를 안할 수 있다. 바로 Arrays.binarySearch() 메서드인데 이분 탐색의 기본 조건과 같이 배열을 오..