TIL (2024.06.05)

문제 1️⃣ (리트 코드_문자열 밸런싱)

https://leetcode.com/problems/split-a-string-in-balanced-strings/description/

💡 IDEA : 일일히 'R' 과 'L' 의 개수를 세서 비교하는 것이 아닌 cnt 하나의 값을 활용하여 밸런싱을 확인한다.

class Solution {
    public int balancedStringSplit(String s) {
        int answer = 0;

        int cnt = 0;
        char tmp;

        for (int i=0; i<s.length(); i++) {
            tmp = s.charAt(i);

            if (tmp == 'R') cnt++;
            else cnt--;

            if (cnt == 0) { // 'R' 과 'L' 이 균형을 이룬경우
                answer++;
                cnt = 0;
            }
        }     
        return answer;
    }
}
/*
풀이
(1) index 0 부터 s.length(), 즉 문자열 전체을 탐색
(2) charAt() 을 통해 'R' & 'L' 값을 확인하며 'R' 일 경우 cnt 값을 하나 증가 시키고 'L' 일 경우 cnt 값을 하나 감소 시킴.
(3) 반복문 끝에서 cnt 값이 0 이면 R 과 L 이 최소 단위로 조화를 이룬 것이므로 answer 값을 하나 증가시키고 cnt 값은 0으로 초기화 시킴
*/

문제 2️⃣ (프로그래머스_구명보트)

https://school.programmers.co.kr/learn/courses/30/lessons/42885

프로그래머스

💡 IDEA : 가장 무거운 사람부터 탑승한다. 이 때 가장 가벼운 사람과 갈 수 있으면 함께 간다.

import java.util.Arrays;

class Solution {
    public int solution(int[] people, int limit) {
        int answer = 0;
        
        Arrays.sort(people); // 오름차순 정렬
        
        int size = people.length;
        
        int bigIdx = people.length-1;
        int smallIdx = 0;
        
        while (size != 0) { // 모두 탑승할 때까지 반복
            if (size == 1) { // 한명 남은 경우 : 바로 탑습
                answer++; 
                break;
            }
            
            // 가장 무거운 사람 + 가장 가벼운 사람 <= 무게 제한 (limit) 인지 확인
            if (people[bigIdx] + people[smallIdx] <= limit) { // 둘 다 타는 경우
                smallIdx++;
                size-=2;
            }
            else { // 가장 무거운 사람만 타는 경우
                size-=1;
            }
            
            bigIdx--;
            answer++;
            
        }
        
        return answer;
    }
}
/*
조건
(1) 최대 2명
(2) 무게 제한 존재 (limit)
(3) 최대한 적게 사용하여 모든 사람 구출

풀이 [70, 50, 80, 50]
-> 가장 무거운 사람과 가장 가벼운 사람이 함께 할 수 있으면 best 아니면 가장 무거운 사람 혼자
(1) sort : [50, 50, 70, 80]
(2) 
*/

문제 3️⃣ (프로그래머스_단속카메라)

💡 IDEA : Car 객체를 생성하여 Car 의 종료 시점을 기준으로 오름 차순 정렬 되도록 PriorityQueue 를 생성한 뒤 Queue 가 빌 때 까지 반복문을 수행한다. 단속카메라의 지점은 무조건 car 객체의 end 지점으로 한다. 다음 차의 시작지점이 카메라의 마지막 지점보다 전이라면 특별한 작동없이 그대로 넘어가고, 마지막 지점 뒤에 있다면 해당 차량의 end 값을 단속카메라의 새로운 지점으로 설정한다.

import java.util.PriorityQueue;

class Car implements Comparable<Car> {
    int start;
    int end;
    
    public Car (int start, int end) {
        this.start = start;
        this.end = end;
    }
    
    @Override
    public int compareTo(Car other) {        
        return this.end - other.end;
    }
}

class Solution {
    public int solution(int[][] routes) {    
        PriorityQueue<Car> pq = new PriorityQueue<>();
        
        for (int[] route : routes) {
            pq.add(new Car(route[0], route[1]));
        }
        
//         // // 주의! : 이 방식은 pq 에 담겨있는 순서대로 나오지 않음
//         // for (Car car : pq) {
//         //     System.out.printf("%d / %d \n", car.start, car.end);
//         // }
        
        
//         // pq 에 담겨있는 순서대로 출력하는 방법
//         while (!pq.isEmpty()) {
//             Car car = pq.poll();  // pq에서 요소를 제거하면서 출력
//             System.out.printf("%d / %d \n", car.start, car.end);
//         }
        
        Car car = pq.poll();
        // System.out.printf("%d / %d\n", car.start, car.end);
        int answer = 1;
        
        int camIdx = car.end;
        // System.out.printf("%d 에 cctv 설치\n", camIdx);
        
        while (!pq.isEmpty()) {
            car = pq.poll();
            // System.out.printf("%d / %d\n", car.start, car.end);
            
            if (car.start <= camIdx) continue;
            
            answer++;
            camIdx = car.end;
            // System.out.printf("%d 에 cctv 설치\n", camIdx);
        }
        
        return answer;
    }
}

/*
- 조건
(1) 단속 카메라를 한 번은 만나야함
(2) 최소 카메라 개수

[[-20,-15], [-14,-5], [-18,-13], [-5,-3]]
A : [-20,-15]
B : [-14,-5]
C : [-18,-13]
D : [-5,-3]]

A C A* B C* D&B* D*

- 풀이
(1) 나가는 것이 중요하므로 종료가 빠른 순
(2) PriorityQueue 에 담기
(3) 차가 모두 지나갈 때 까지 마지막 cctv 의 지점을 저장하면서 진행
    -> 무조건 차의 맨 끝을 cctv 지점으로 설정
        -> 다음 차의 시작이 cctv 지점 전이면 다음 차를 확인
        -> 다음 차의 시작이 cctv 지점 다음이면 해당 차량의 마지막을 새로운 cctv 지점으로 설정

*/

참고 🔗 : Comparable 과 Comparator 의 차이 (https://st-lab.tistory.com/243)

자바 [JAVA] - Comparable 과 Comparator의 이해

주의 ⚠️ : PriorityQueue 의 순서를 확인하고 싶을 때는 향상된 for 문이 아닌, poll 을 통해 확인하는 방식으로 진행해야한다.