[항해99 취업 리부트 코스 학습일지] 2024.04.04(목)

시간이 엄청 빠르게 가는게 느껴진다

오늘 우선순위 큐라는 걸 처음 써봤다. 자동 정렬이 되는데도 불구하고 시간복잡도가 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]