CODEKATA : 96 ~ 98

96번 주차 요금 계산

/*
문제 분석
1. 정보
    - 요금표는 다음과 같음
        기본시간(분) | 기본 요금(원) | 단위 시간(분) | 단위 요금(원)
        180        | 5000        | 10          | 600
    - 어떤 차량이 입차된 후에 출차된 내역이 없다면, 23:59에 출차된 것으로 간주
    - 00:00 부터 23:59까지의 입/출차 내역을 바탕으로 차랑별 누적 주차 시간을 계산하여 요금을 일괄로 정산
    - 누적 주차 시간이 기본 시간 이하라면, 기본 요금을 청구
    - 누적 주차 시간이 기본 시간을 초과하면, 기본 요금에 더해서 초과한 시간에 대해 단위 시간 마다 단위 요금을 청구
        - 초과한 시간이 단위 시간으로 나누어 떨어지지 않으면, 올림
    
2. 목표
    - 주차 요금을 나타내는 정수 배열 fees, 자동차의 입/출차 내역을 나타내는 문자열 배열 records가 주어질 때, 차량 번호가 작은 자동차부터 청구할 주차 요금을 차례대로 정수 배열에 담아 return
    
3. 제약 조건
    - fees의 길이 = 4
        - fees[0] = 기본 시간
            - 1 <= fees[0] <= 1439
        - fees[1] = 기본 요금
            - 0 <= fees[1] <= 100000
        - fees[2] = 단위 시간
            - 0 <= fees[2] <= 1439
        - fees[3] = 단위 요금
            - 0 <= fees[3] <= 100000
    - 1 <= records의 길이 <= 1000
        - 각 원소는 시각, 차량번호, 내역이 공백으로 구분되어 들어옴
        - 시각은 입차 or 출차 시각
        - 차랑 변호는 0 ~ 9로 구성된 길이 4인 문자열
        - 내역 IN 또는 OUT임.
        - 시각을 기준으로 오름차순으로 정렬되어 주어짐

풀이
1. 아이디어
    - LocalTime 형식의 배열을 만들어 입차시간, 출차시간을 저장\
        - Car : number, in, out 을 저장
    - List<Car>를 저장해 각 차량 번호의 입차, 출차시간을 저장
        - IN일 경우, add
        - OUT일 경우 입차한 기록을 찾아 해당 기록에 OUT 업데이트
    - 이후 Car의 number를 기준으로 모든 시간 합산
        - Map<Integer, Integer>를 통해 total time 계산
            - 해당 값을 TreeMap을 통해 차량번호 오름차순으로 정렬
    - 합산한 시간을 사용하여 가격 계산
        - 만약 주차 시간이 기본 시간보다 작으면 기본 요금만 저장
        - 기본 시간보다 크다면, 기본 요금 + (주차 시간 - 기본 시간) / 단위시간 * 단위 요금
    - 계산한 가격을 answer에 차례대로 저장
*/

import java.time.*;
import java.util.*;

class Solution {

        class Car{
            int number;
            LocalTime in;
            LocalTime out;

            public Car(int number, LocalTime in, LocalTime out) {
                this.number = number;
                this.in = in;
                this.out = out;
            }
        }

        public int[] solution(int[] fees, String[] records) {
            List<Car> cars = new ArrayList<>();

            for (String record : records) {
                String[] split = record.split(" ");
                int number = Integer.parseInt(split[1]);
                LocalTime time = LocalTime.parse(split[0]);
                if ("IN".equals(split[2])) {
                    cars.add(new Car(number, time, LocalTime.parse("23:59")));
                }else{
                    for (int i = cars.size() - 1; i >= 0; i--) {
                        if (cars.get(i).number == number) {
                            cars.get(i).out = time;
                            break;
                        }
                    }
                }
            }

            Map<Integer, Integer> totalTime = new HashMap<>();

            for (Car car : cars) {
                if (totalTime.containsKey(car.number)) {
                    int time = totalTime.get(car.number);
                    time += (int) Duration.between(car.in, car.out).toMinutes();
                    totalTime.put(car.number, time);
                }else{
                    int time = (int) Duration.between(car.in, car.out).toMinutes();
                    totalTime.put(car.number, time);
                }
            }

            Map<Integer, Integer> sortedMap = new TreeMap<>(totalTime);

            int[] answer = new int[totalTime.size()];
            int idx = 0;

            for (Integer number : sortedMap.keySet()) {

                int time = sortedMap.get(number);
                int price = fees[1];
                if (time > fees[0]) {
                    price += (int)Math.ceil((double) (time - fees[0]) / fees[2]) * fees[3];
                }
                answer[idx++] = price;
            }

            return answer;
        }
    }

97번 모음사전

/*
문제 분석
1. 정보
    - 사전에 알파벳 모음 A, E, I, O, U 만을 사용하여 만들 수 있는 , 길이 5 이하의 모든 단어가 수록되어 있음
    - 사전에서 첫 번째 단어는 A 이고, 그 다음은 AA 이며, 마지막 단어는 UUUUU 임

2. 목표
    - 단어 하나가 주어질 때, 해당 단어가 사전에서 몇 번째 단어인지 return
    
3. 제약 조건
    - 1 <= 단어의 길이 <= 5
    - 단어는 알파벳 대문자 A, E, I, O, U로 이루어짐

풀이
1. 아이디어
    - DFS? 백트래킹? 사용
        - 전역 변수로 순서 값을 저장
        - A 부터 U 까지 시작점으로 정하고, 메서드를 통해 다음 모음을 정함
        - 만약 해당 단어가 주어진 단어와 같다면, 해당 순번을 return한다.  
*/

class Solution {

        int answer = -1;
        int result = 0;
        char[] vowels = {'A', 'E', 'I', 'O', 'U'};

        public int solution(String word) {
            StringBuilder words = new StringBuilder();
            compute(0, word, words);
            return answer;
        }

        private void compute(int idx, String word, StringBuilder words) {
            result++;
            if (word.contentEquals(words)) {
                answer = result - 1;
                return;
            }

            if (idx == 5 || answer != -1) {
                return;
            }

            for (int i = 0; i < vowels.length; i++) {
                words.append(vowels[i]);
                compute(idx + 1, word, words);
                words.deleteCharAt(words.length() - 1);
            }
        }
    }

98번 뒤에 있는 큰 수 찾기

/*
문제 분석
1. 정보
    - 정수로 이루어진 배열 numbers가 존재
    - 배열의 각 원소들에 대하여 자신보다 뒤에 있는 숫자 중에서 자신보다 크면서 가장 가까이 있는 수를 뒷 큰수라 함

2. 목표
    - 정수 배열 numbers가 주어질 때, 모든 원소에 대한 뒷 큰수들을 차례로 담은 배열을 return

3. 제약 조건
     - 4 <= numbers 길이 <= 1000000
        - 1 <= numbers[i] <= 1000000

풀이
1. 아이디어
    - Stack 활용
        - numbers의 값을 뒤에서 부터 차례대로 하나씩 stack에 집어 넣음
            - 만약 스택에서 현재 숫자보다 크거나 같은 숫자가 있으면 해당 숫자를 제거
            - 스택이 비어있다면 뒷 큰수가 없으므로 -1 저장
            - 비어있지 않다면 peek()를 통해 뒷 큰수를 뽑아 저장
*/

import java.util.*;

class Solution {
        public int[] solution(int[] numbers) {
            Stack<Integer> s = new Stack<>();
            int[] answer = new int[numbers.length];

            for (int i = numbers.length - 1; i >= 0; i--) {

                while (!s.isEmpty() && s.peek() <= numbers[i]) {
                    s.pop();
                }

                answer[i] = s.isEmpty() ? -1 : s.peek();

                s.push(numbers[i]);
            }

            return answer;
        }
    }