프로그래머스LV2_17

스킬 트리

접근 과정

1. 스킬 트리가 앞부터 배워야 하므로 큐를 활용을 생각
2. 스킬 트리 배열의 현재 스킬이 스킬 트리 목록에 포함된다면 큐의 앞과 비교
3. 앞과 다르면 안된다고 체크하여 break
4. 스킬 트리가 된다면 answer을 1 늘림

시행착오

• 시행착오 없이 해결

해결 코드

• 접근 과정대로 구현하여 해결

import java.util.*;

class Solution {
    public int solution(String skill, String[] skill_trees) {
        int answer = 0;
        for(String st : skill_trees){
            Queue<Character> q = new LinkedList<>();
            for(char c : skill.toCharArray()){
                q.add(c);
            }
            boolean check = true;
            for(char c : st.toCharArray()){
                if(skill.indexOf(c) != -1){
                    if(q.peek() == c) q.poll();
                    else{
                        check = false;
                        break;
                    }
                }
            }
            if(check) answer++;
        }
        return answer;
    }
}

시간 및 공간 복잡도

• 시간 복잡도(선행 스킬 문자열의 길이를 L, skill_trees 배열의 길이를 N, 각 스킬트리 문자열의 최대 길이를 M)

• 공간 복잡도

주차 요금 계산

접근 과정

1. 입차할 시 들어온 번호와 시간을 추가
2. 출차 시 누적 시간을 입차 시간과 계산하여 추가
3. 출차 못한 차가 있으면 23:59 출차로 계산하여 누적 시간 추가
4. 번호 순으로 키를 정렬하여 전체를 돌면서 비용을 계산

시행착오

• 시행착오 없이 해결

해결 코드

• 접근 과정대로 구현하여 해결

import java.util.*;

class Solution {
    public int[] solution(int[] fees, String[] records) {
        List<Integer> answer = new ArrayList<>();
        Map<String, Integer> map = new HashMap<>();
        Map<String, Integer> time = new HashMap<>();
        for(String r : records){
            String[] sp_r = r.split(" ");
            if(sp_r[2].equals("IN")){
                String num = sp_r[1];
                int in = timeToInt(sp_r[0]);
                map.put(num, in);
            }
            else{
                String num = sp_r[1];
                int stay = timeToInt(sp_r[0]) - map.get(num);
                map.remove(num);
                time.put(num, time.getOrDefault(num, 0) + stay);
            }
        }
        if(map.size() > 0){
            Set<String> set = map.keySet();
            for(String s : set){
                int stay = timeToInt("23:59") - map.get(s);
                time.put(s, time.getOrDefault(s, 0) + stay);
            }
        }
        Set<String> set = time.keySet();
        List<String> cars = new ArrayList<>(time.keySet());
        Collections.sort(cars);
        for(String car : cars){
            int t = time.get(car);
            answer.add(fee(t, fees));
        }
        return answer.stream().mapToInt(i -> i).toArray();
    }
    
    private int timeToInt(String time){
        String[] t = time.split(":");
        return Integer.parseInt(t[0]) * 60 + Integer.parseInt(t[1]);
    }
    
    private int fee(int stay, int[] fees){
        if(stay <= fees[0]){
            return fees[1];
        }
        int left = stay - fees[0];
        return (left % fees[2] == 0)?
            fees[1] + left / fees[2] * fees[3] :
            fees[1] + (left / fees[2] + 1) * fees[3];
    }
}

시간 및 공간 복잡도

• 시간 복잡도(records 배열의 길이를 N, 입차된 차량의 총 종류를 K)

• 공간 복잡도

개선

• 맵을 해시맵이 아닌 트리맵을 사용하면 넣을 때 키 값이 자동 정렬이 되어 좀 더 코드가 짧아지고 간단해져서 개선해보았다.

import java.util.*;

class Solution {
    public int[] solution(int[] fees, String[] records) {
        List<Integer> answer = new ArrayList<>();
        Map<String, Integer> map = new HashMap<>();
        Map<String, Integer> time = new TreeMap<>();
        for(String r : records){
            String[] sp_r = r.split(" ");
            if(sp_r[2].equals("IN")){
                String num = sp_r[1];
                int in = timeToInt(sp_r[0]);
                map.put(num, in);
            }
            else{
                String num = sp_r[1];
                int stay = timeToInt(sp_r[0]) - map.get(num);
                map.remove(num);
                time.put(num, time.getOrDefault(num, 0) + stay);
            }
        }
        if(map.size() > 0){
            Set<String> set = map.keySet();
            for(String s : set){
                int stay = timeToInt("23:59") - map.get(s);
                time.put(s, time.getOrDefault(s, 0) + stay);
            }
        }
        Set<String> set = time.keySet();
        for(String car : set){
            int t = time.get(car);
            answer.add(fee(t, fees));
        }
        return answer.stream().mapToInt(i -> i).toArray();
    }
    
    private int timeToInt(String time){
        String[] t = time.split(":");
        return Integer.parseInt(t[0]) * 60 + Integer.parseInt(t[1]);
    }
    
    private int fee(int stay, int[] fees){
        if(stay <= fees[0]){
            return fees[1];
        }
        int left = stay - fees[0];
        return (left % fees[2] == 0)?
            fees[1] + left / fees[2] * fees[3] :
            fees[1] + (left / fees[2] + 1) * fees[3];
    }
}

2 x n 타일링

접근 과정

1. 규칙을 찾아보니 현재 경우의 수는 이전 값과 그 이전 값을 합이란 것을 파악(피보나치 느낌)
2. 규칙을 이용하기 위해 dp 방식으로 구현
3. 매 수행마다 mod를 수행하여 int 범위를 넘지 않도록 유지

시행착오

• 시행착오 없이 구현

해결 코드

• 접근 과정대로 구현하여 해결

class Solution {
    public int solution(int n) {
        int[] dp = new int[n + 1];
        int mod = 1000000007;
        dp[1] = 1;
        dp[2] = 2;
        for(int i = 3; i <= n; i++){
            dp[i] = (dp[i - 1] + dp[i - 2]) % mod;
        }
        return dp[n];
    }
}

시간 및 공간 복잡도

• 시간 복잡도(타일의 가로 길이를 n)

• 공간 복잡도

개선

• 굳이 배열을 선언하지 않아도 가능하여 공간 복잡도를 줄여보았다.

class Solution {
    public int solution(int n) {
        if (n == 1) return 1;
        if (n == 2) return 2;
        int mod = 1000000007;
        int prev2 = 1;
        int prev1 = 2;
        int current = 0;
        for (int i = 3; i <= n; i++) {
            current = (prev1 + prev2) % mod;
            prev2 = prev1;
            prev1 = current;
        }
        return current;
    }
}

파일명 정렬

접근 과정

1. 파일의 문자열을 head, number, tail로 분리
2. 다음 인덱스의 문자열의 head와 비교하여 사전 순 정렬
3. 만약 head가 같다면 2번째의 number를 비교
4. 자바의 Arrays.sort는이미 stable sort이므로 들어온 순서는 비교할 필요가 없다.

시행착오

• 문자열을 분리할 때 number의 시작과 끝의 인덱스를 찾았는데 substring에서 인덱스를 잘못 넣었으며 문자열을 비교하는 방법을 몰라 찾아보았다.

해결 코드

• 접근 과정대로 구현하였으며 문자열 비교 함수인 compareTo 함수를 알게 되었다.
• compareTo(): 결과값에 따라 순서를 알 수 있다.
  • 0: 두 문자열이 같음
  • 음수: 대상 문자열이 사전적으로 더 앞섬
  • 양수: 대상 문자열이 사전적으로 더 뒤에 위치함

import java.util.*;

class Solution {
    public String[] solution(String[] files) {
        Arrays.sort(files, (a, b) -> {
            String[] s1 = splitStr(a);
            String[] s2 = splitStr(b);
            int headCompare = s1[0].compareTo(s2[0]);
            if (headCompare != 0) {
                return headCompare;
            }
            int num1 = Integer.parseInt(s1[1]);
            int num2 = Integer.parseInt(s2[1]);
            return num1 - num2;
        });
        return files;
    }
    
    private String[] splitStr(String str){
        int first = -1;
        int last = str.length();
        for(int i = 0; i < str.length(); i++){
            if(Character.isDigit(str.charAt(i))){
                if(first == -1) first = i;
            }
            else{
                if(first != -1){
                    last = i;
                    break;
                }
            }
        }
        String head = str.substring(0, first).toLowerCase();
        String number = str.substring(first, last);
        String tail = str.substring(last);
        return new String[]{head, number, tail};
    }
}

시간 및 공간 복잡도

• 시간 복잡도(파일 배열의 길이를 N, 파일명의 최대 길이를 L)

• 공간 복잡도

오픈채팅방

접근 과정

1. 마지막 닉네임으로 변경되는 것을 파악하여 id 별 마지막 닉네임을 맵에 저장
2. 다시 돌면서 들어온 것과 나가는 것을 마지막 닉네임으로 설정하여 배열에 저장하여 해결

시행착오

• 시행착오 없이 해결

해결 코드

• 접근 과정대로 구현하여 해결

import java.util.*;

class Solution {
    public String[] solution(String[] record) {
        List<String> answer = new ArrayList<>();
        Map<String, String> map = new HashMap<>();
        for(String r : record){
            String[] splitR = r.split(" ");
            String command = splitR[0];
            if(command.equals("Enter") || command.equals("Change")){
                map.put(splitR[1], splitR[2]);
            }
        }
        for(String r : record){
            String[] splitR = r.split(" ");
            String command = splitR[0];
            String id = splitR[1];
            if(command.equals("Enter")){
                answer.add(map.get(id) + "님이 들어왔습니다.");
            }
            else if(command.equals("Leave")){
                answer.add(map.get(id) + "님이 나갔습니다.");
            }
        }
        return answer.toArray(String[]::new);
    }
}

시간 및 공간 복잡도

• 시간 복잡도(record 배열의 길이를 N)

• 공간 복잡도