시간이 엄청 빠르게 가는게 느껴진다
오늘 우선순위 큐라는 걸 처음 써봤다. 자동 정렬이 되는데도 불구하고 시간복잡도가 O(logN)인게 너무 신기하다.
뭔가 정렬을 할게 있을 때 사용해보면 좋을 것 같다.
사실 지난주에 풀었던 문제들도 우선순위큐로 풀 수 있었지 않을까? 하는 마음에 풀어보다가 늦게잔건 TMI
약간 항해하면서 시간이 엄청 빨리간다..
[01. 람다를 이용한 Comparator]
어제 연습했던 것 처럼 people을 클래스로 만들어 사용할 수 있습니다.
import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
public class ComparatorExample {
public static void main(String[] args) {
// Person 객체를 담을 리스트 생성
List<Person> people = new ArrayList<>();
people.add(new Person("김일번", 25));
people.add(new Person("박이번", 20));
people.add(new Person("최삼번", 30));
// 나이를 기준으로 오름차순 정렬 (람다식 사용)
people.sort((Person p1, Person p2) -> p1.getAge() - p2.getAge());
// 정렬된 리스트 출력
for (Person p : people) {
System.out.println(p.getName() + " : " + p.getAge());
}
// 출력 : 박이번 : 20
// 김일번 : 25
// 최삼번 : 30
// 내림차순 정렬
people.sort(Comparator.comparingInt(Person::getAge).reversed());
// 정렬된 리스트 출력
System.out.println("정렬2 :");
for (Person p : people) {
System.out.println(p.getName() + " : " + p.getAge());
}
// 출력:
// 정렬2 :
// 최삼번 : 30
// 김일번 : 25
// 박이번 : 20
}
static class Person {
private String name;
private int age;
public Person(String name, int age) {
this.name = name;
this.age = age;
}
public String getName() {
return name;
}
public int getAge() {
return age;
}
}
}
람다식 people.sort((Person p1, Person p2) -> p1.getAge() - p2.getAge()); 는 들어온 순서대로 두 객체를 매개변수로 받아 첫번째
객체(p1) 에서 두번째 객체(p2)의 나이를 뺀 결과를 반환하는데!!
1) 양수 반환 : p1이 p2 보다 크다는 의미 -> 오름차순 기준으로 정렬 상 뒤에 위치해야 한다
2) 0 반환 : 두 객체의 나이가 같다는 의미, 순서 변경 하지 않고 그냥 두기
3) 음수 반환 : 결과가 음수라면 p2 가 더 크다는 의미, 그럼 p1은 앞에 있어야 한다
이걸 반영해 재정렬 해주는 것! !
[02. 우선순위 큐]
- 힙 이라는 자료구조를 이해하여야 한다.
- 자바에서는 PriorotyQueue 클래스를 사용하여 힙을 구현할 수 있다.
- queue와 선입선출은 같지만, 데이터가 입, 출력 될 때 자동으로 정렬이 된다고 합니다. 동작 원리는 조금 더 공부해 보는 걸로..
예) N번째 큰 수 찾기
ㅋㅋㅋ 오늘 이 문제 풀다가 ㅋㅋㅋㅋㅋ 나만 시간이 엄청 느리게 나왔길래 뭐가 문제일까 보다가.. ㅋㅋㅋㅋ
'큰 수' 찾는거면 내림차순 정렬 하고 풀었어야 하는데 나만 앞에서부터 값 비교해가면서 푼 것이여...ㅋㅋㅋㅋ
대신 접근방식 자체는 좋았다!
package src.com.company.week2.day2;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.PriorityQueue;
import java.util.StringTokenizer;
public class BJ_2075_N번째큰수 {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
// 일단 선언만
StringTokenizer st;
PriorityQueue<Integer> priorityQueue = new PriorityQueue<>();
int N = Integer.parseInt(br.readLine());
for (int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine());
// 토큰이 없을 때 까지
while (st.hasMoreTokens()) {
int numberElement = Integer.parseInt(st.nextToken());
// 우선순위 큐에 한줄씩(자동 오름차순) 쌓는다
priorityQueue.add(numberElement);
if (priorityQueue.size() > N) {
// 가장 작은 값이 위로 가 있을 것이기 때문에, 끝까지 남은건 35,41,48,49,52
priorityQueue.poll(); // 우선순위 큐 크기를 N으로 유지
}
}
}
System.out.println(priorityQueue.peek());
}
}
[수정한 코드 넣기] 2024.04.05]
'항해99 취업 리부트 코스 학습일지' 카테고리의 다른 글
[항해99 취업 리부트 코스 학습일지] 2024.04.08(월) (0) | 2024.04.09 |
---|---|
[항해99 취업 리부트 코스 학습일지] 2024.04.06(토) (0) | 2024.04.08 |
[항해99 취업 리부트 코스 학습일지] 2024.04.03(수) (0) | 2024.04.04 |
[항해99 취업 리부트 코스 학습일지] 2024.04.01.(월) (0) | 2024.04.01 |
[항해99 취업 리부트 코스 학습일지] 2024.03.30.(토) (0) | 2024.03.31 |