| 문제번호 | 제목 | 난이도 |
|---|---|---|
| 1715 | 카드 정렬하기 | 골드 4 |
| 2075 | N번째 큰 수 | 실버 2 |
| 1655 | 파일 합치기 3 | 골드 2 |
| 1781 | 가운데를 말해요 | 골드 2 |
1715번 카드 정렬하기
해결 코드:
import java.io.*;
import java.util.*;
/**
* 풀이 과정:
*
* - 문제 해결:
*
* 시간복잡도: O()
* 공간복잡도: O()
*
*/
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
int n = Integer.parseInt(br.readLine());
PriorityQueue<Integer> pq = new PriorityQueue<>();
for (int i = 0; i < n; i++) {
int input = Integer.parseInt(br.readLine());
pq.add(input);
}
int ans = 0;
while(pq.size() > 1){
int first = pq.poll();
int second = pq.poll();
int sum = first + second;
ans += sum;
pq.add(sum);
}
bw.write(ans+"");
br.close();
bw.close();
}
}
학습 정리:
- 내림차순, 오름차순을 지속적으로 해야하고, 두 수의 합을 더해서 다시 저장하고 비교하는 형태의 문제라면 우선순위 큐를 사용하자
2075번 N번째 큰 수
해결 코드:
import java.io.*;
import java.util.*;
/**
* 풀이 과정:
*
* - 문제 해결:
*
* 시간복잡도: O()
* 공간복잡도: O()
*
*/
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
int n = Integer.parseInt(br.readLine());
PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());
for (int i = 0; i < n; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
for (int j = 0; j < n; j++) {
pq.add(Integer.parseInt(st.nextToken()));
}
}
int ans = 0;
for (int i = 0; i < n; i++) {
ans = pq.poll();
}
bw.write(ans+"");
br.close();
bw.close();
}
}
학습 정리:
- 메모리 사용량이 극도로 작다면 배열보다는 우선순위 큐를 사용하자 공간복잡도를 N^2에서 n으로 줄일 수 있다
1655번 가운데를 말해요
해결 코드:
import java.io.*;
import java.util.*;
/**
* 풀이 과정:
*
*
* - 문제 해결:
*
* 시간복잡도: O()
* 공간복잡도: O()
*
*/
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
int n = Integer.parseInt(br.readLine());
PriorityQueue<Integer> pq = new PriorityQueue<>(Comparator.reverseOrder());
PriorityQueue<Integer> qp = new PriorityQueue<>();
for (int i = 0; i < n; i++) {
int input = Integer.parseInt(br.readLine());
if(pq.size() == qp.size()){
pq.add(input);
}else{
qp.add(input);
}
if(!pq.isEmpty() && ! qp.isEmpty()){
if(pq.peek() > qp.peek()){
int tmp = pq.poll();
pq.add(qp.poll());
qp.add(tmp);
}
}
bw.write(pq.peek()+"\n");
}
br.close();
bw.close();
}
}
학습 정리:
- 해당 문제는 두 우선순위큐를 활용하는 문제였다. 하나는 내림차순 정렬로 왼쪽에 두고 하나는 오름차순 정렬해서 오른쪽에 둬서 한줄로 양옆에 두 우선순위 큐를 둔 형태의 문제였다
- 둘의 크기가 같으면 왼쪽에 넣고 아니면 오른쪽에 넣는다
- 그리고 둘다 비어있지 않으면 이제 두 우선순위 큐의 peek값을 비교해서 왼쪽이 더 크면 스왑한다
- 이 문제는 우선순위 큐를 활용한 아이디어 문제였다.
- 한가지 자료구조만 사용하는 경우를 고려하는 것도 좋지만 여러 자료구조를 활용하고, 어떤 자료구조를 활용해야할지 고민하는 연습을 어려운 문제를 더 풀면서 학습해야겠다.
1781번 컵라면
해결 코드:
import java.io.*;
import java.util.*;
/**
* 풀이 과정:
* - 고민 및 풀이:
* 1. 처음 생각한 정렬 방법은 데드라인 오름차순 정렬 + 같을 경우 컵라면 수 내림차순 정렬이었다.
* => 틀린 풀이, 데드라인이 작은 애들의 컵라면 받을 수 있는 수가 극단적으로 작을 경우 그닥 의미가 없다..
* 2. 그럼 두번째는 컵라면 수 내림차순 정렬 + 같을 경우 데드라인 오름차순 정렬
* => 이것도 틀린 풀이이다.
* 3. 이 문제의 핵심은 위 1번 정렬을 하면서 컵라면을 최대로 받을 수 있는 경우를 찾아한다. 데드라인이 작은 것들을 아예 선택 안하고 컵라면 수가 많은 것들만 선택해도 되기때문에
* 문제 접근을 다시 생각해야 한다.
*
* - 문제 해결:
* 1. 힌트를 참고했는데, 나와 같은 생각을 하고 접근했다가 틀린 사람이 많았다
* 2. 입력을 리스트로 받거나 배열로 받아 위 정렬을 진행하고 이후에 한가지 더 만족시켜야 하는 컵라면을 최대로 받을 수 있는 경우를 찾는 행위를 위해 우선순위 큐를 사용해야한다
* 3. 우선순위 큐의 크기를 데드라인으로 생각하면 된다. 만약 배열의 시간이 데드라인보다 크기보다 크면 데드라인의 값을 하나 poll하면 된다
* 4. 그리고 우선순위 큐에는 컵라면 개수를 넣어준다. 오름차순 정렬이기에 작은 값은 앞으로 가게 되어 위 3번 진행 시에 제일 먼저 빠지게 된다
* 5. 이 과정을 진행하면 받을 수 있는 최대의 컵라면 개수를 얻을 수 있게 되고, 순회해서 모든 값을 더해주면 정답이 된다.
*
*
*
* 시간복잡도: O()
* 공간복잡도: O()
*
*/
class Problem{
int time;
int count;
public Problem(int time, int count) {
this.time = time;
this.count = count;
}
}
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
int n = Integer.parseInt(br.readLine());
PriorityQueue<Integer> pq = new PriorityQueue<>();
List<Problem> lists = new ArrayList();
for (int i = 0; i < n; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
int time = Integer.parseInt(st.nextToken());
int count = Integer.parseInt(st.nextToken());
Problem problem = new Problem(time, count);
lists.add(problem);
}
Collections.sort(lists, ((o1, o2) -> {
return o1.time==o2.time ? o2.count - o1.count : o1.time - o2.time;
}));
int now = 1;
int ans = 0;
for (int i = 0; i < n; i++) {
if(pq.isEmpty()){
pq.add(lists.get(i).count);
continue;
}
pq.add(lists.get(i).count);
if(lists.get(i).time < pq.size()){
pq.poll();
}
}
for (Integer i : pq) {
ans += i;
}
bw.write(ans+"");
br.close();
bw.close();
}
}
학습 정리:
- 우선순위 큐를 서브로 활용하는 문제였다.
- 이 문제를 풀면서 난관은 우선순위 큐에 문제 해결을 위한 클래스 타입으로 지정해서 우선순위 큐만을 활용해서 풀렸고 했던 것이었다
- 조건 하나 때문에 위 난관을 겪었다. 정해진 정렬을 진행 한 후, 한가지 조건을 더 만족시키기 위해서는 리스트로 먼저 정렬한 뒤, 다시 우선순위 큐를 사용해야하는 문제였었다.
- 문제를 읽으면서 조건을 하나씩 뽑아내고, 그 조건에 맞는 해결법을 고안하는 것을 먼저 진행하자.
- 그리고 순차적으로 조건을 해결하면서, 한가지 자료구조로만 해결하려 하지 말고 여러 자료구조를 사용해서 해결하려는 방법과 순차적으로 자료구조를 이어서 사용하려고 하는 연습도 계속된 문제 풀이를 통해 학습하자
Software Developer