우유

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

카카오 기출에서 단순 구현문제가 많은 것 같다. 문제만 잘 읽고 이해하면 구현하는 것은 어렵지 않지만 문제 읽고 이해하는거 자체가 어려운 편이다.. (개인적인 생각) 이번 문제도 마찬가지로 재귀를 이용한 구현문제이다.

문제 포인트

문제 그대로 u와 v를 분리하여 그대로 수행해주면 된다.
필자는 처음에 분리를 해야된다는 단순한 생각때문에 함수 자체에서 String[] 로 나누어서 구분해야되나 생각했었는데, 그럴 필요가 전혀 없이 DFS 함수에서 return 할 때 각 if문에 들어가는 조건대로 String으로 return 해주면 되는 방법이 있었다..

import java.util.*;

class Solution {
    public String solution(String p) {
        String answer = "";

        answer = DFS(p);
        
        return answer;
    }

    // u, v를 분리하는 함수
    public String DFS(String str) {

        if (str.equals(""))
            return "";

        String u = "";
        String v = "";

        int cnt = 0;

        for (int i = 0; i < str.length(); i++) {
            if (str.charAt(i) == '(')
                cnt++;
            else if (str.charAt(i) == ')')
                cnt--;

            u += str.charAt(i);

            if (cnt == 0) {
                v = str.substring(i + 1, str.length());
                break;
            }
        }

        if (check(u)) {
            return u += DFS(v);
        } else {
            StringBuilder sb = new StringBuilder();

            sb.append("(");
            sb.append(DFS(v));
            sb.append(")");

            u = u.substring(1, u.length() - 1);

            for (int i = 0; i < u.length(); i++) {
                if (u.charAt(i) == '(')
                    sb.append(')');
                else if (u.charAt(i) == ')')
                    sb.append('(');
            }
            return sb.toString();
        }
    }

    // 올바른 괄호 문자열인지 판단하는 함수
    public boolean check(String str) {
        Stack<Character> stack = new Stack<>();

        boolean flag = true;

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

            if (tmp == '(') {
                stack.push('(');
            } else if (tmp == ')') {
                if (stack.isEmpty()) {
                    flag = false;
                    break;
                }
                if (stack.peek() == '(')
                    stack.pop();
            }
        }

        if (!stack.isEmpty())
            flag = false;

        return flag;
    }
}

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

문제 포인트

문제가 엄청 길어서 쫄았지만, 단순한 구현 문제였다. 
1. 문자열로 주어진 시간을 분으로 환산
2. 한번에 StringBuilder 에 넣을수 있도록 음계를 C# -> c 이런식으로 모두 변환
3. sheet_music.charAt(j % sheet_music.length()) charAt의 인덱스를 저렇게 나머지를 통해 구함
4. 라디오에서 재생된 시간이 제일 긴 음악이 반환되도록 max_play_time 변수를 선언하여 최대값이 초기화 될때 answer 에 저장

class Solution {
    public String solution(String m, String[] musicinfos) {
        String answer = "(None)";

        int max_play_time = Integer.MIN_VALUE;

        for(int i = 0; i < musicinfos.length; i++){
            String tmp[] = musicinfos[i].split(",");
            StringBuilder sb = new StringBuilder();

            int start_time = cal_time(tmp[0]);
            int end_time = cal_time(tmp[1]);
            String music_title = tmp[2];
            String sheet_music = tmp[3];

            int play_time = end_time - start_time;

            // #이 붙은 음을 소문자 음으로 치환
            sheet_music = change_melody(sheet_music);

            // (재생시간 / 악보의 길이)를 나눴을 때 나오는 악보의 인덱스값을 append
            for(int j = 0; j < play_time ; j++) 
                sb = sb.append(sheet_music.charAt(j % sheet_music.length()));
            
            if(sb.toString().contains(change_melody(m))){
                // 조건이 일치하는 음악이 여러 개일 때에는 라디오에서 재생된 시간이 제일 긴 음악 제목을 반환해야 하므로 max_play_time < play_time
                if(max_play_time < play_time){
                    max_play_time = play_time;
                    answer = music_title;
                }
            }
        }
        return answer;
    }

    public int cal_time(String time){
        String tmp[] = time.split(":");

        return Integer.parseInt(tmp[0]) * 60 + Integer.parseInt(tmp[1]);
    }

    public String change_melody(String str){
        str = str.replaceAll("A#","a");
        str = str.replaceAll("C#","c");
        str = str.replaceAll("D#","d");
        str = str.replaceAll("F#","f");
        str = str.replaceAll("G#","g");

        return str;
    }
}

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

문제 포인트

DFS를 사용해서 몇번 순환 하는지 체크하는 어렵지 않은 문제였다. computers 배열에서 computers[i][i] 인 경우 1로 초기화가 되있기 때문에 모두 0으로 바꾸어 주고, 1이거나 방문하지 않았던 컴퓨터를 계속 DFS로 방문하여 몇번 싸이클이 도는지 answer 변수에 추가해주면 되는 단순한 DFS 문제였다.

DFS 함수안에서 
if(visited[i])
    return;
하는 경우와 (보통 백트래킹)
visited[i] = true;
이런 경우를 잘 구분해서 사용해야 할 것 같다.

class Solution {

    static int N;
    static boolean[] visited;

    public int solution(int n, int[][] computers) {
        int answer = 0;

        N = n;
        visited = new boolean[N];

        for (int i = 0; i < N; i++)
            computers[i][i] = 0;

        for (int i = 0; i < N; i++) {
            if (!visited[i]) {
                DFS(i, computers);
                answer++;
            }
        }
        
        return answer;
    }

    public void DFS(int n, int[][] computers) {

        visited[n] = true;

        for (int i = 0; i < N; i++) {
            if (!visited[i] && computers[n][i] == 1) {
                DFS(i, computers);
            }
        }
    }
}

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

문제 푸는 방식을 찾아내는 것이 핵심이었던 문제였다. 구현하는 시간보다 문제를 어떻게 풀어야될지에 대한 생각을 하는데 시간을 더 많이 소요 했던거 같다. 

이번 문제의 핵심은 백트레킹 (BackTraking) 을 사용하여 가능할 수 있는 모든 경로를 ArrayList<String> 에 저장하는 것

- 가능한 경로가 2개 이상일 경우 알파벳 순서가 앞서가는 경로를 return 해줘야 하기 때문에 Collections.sort(list)를
사용해서 ArrayList 에 추가된 String 값을 알파벳 순서로 재배열 한뒤 첫번째 인덱스에 저장된 String 값 return
- visited[i] = true 로 방문체크를 하고 DFS 함수를 빠져나오면서 다시 visited[i] = false 를 해주기 때문에 같은 출발지에서 여러 도착지로, 즉 중복된 출발지에서 도착지가 달라도 모든 경로를 탐색할 수 있게 한다.

import java.util.*;

class Solution {

    static boolean visited[];
    static ArrayList<String> list = new ArrayList<String>();

    public String[] solution(String[][] tickets) {
        String[] answer = {};
        visited = new boolean[tickets.length+1];

        DFS("ICN", "ICN", 0, tickets);

        Collections.sort(list);

        return list.get(0).split(" ");
    }

    public void DFS(String start, String path, int depth, String tickets[][]) {
        if (depth == tickets.length){
            list.add(path);
            return;
        }

        for (int i = 0; i < tickets.length; i++) {
            if (tickets[i][0].equals(start) && !visited[i]) {
                visited[i] = true;
                DFS(tickets[i][1], path + " " + tickets[i][1], depth + 1, tickets);
                visited[i] = false;
            }
        }
    }
}

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

어렵지 않았지만, 배열 인덱스 범위를 잘못 지정해줘서 생각보다 오래걸렸던 문제다. 백준에도 비슷한 문제가 있었는데 다시 풀어봐도 헷갈렸던 문제..

triangle 2차원 배열의 인덱스를 초과 하지 않게 하기 위해서 왼쪽 가장자리와, 오른쪽 가장자리를 따로 초기화 해준다
DP[i][0] = DP[i - 1][0] + triangle[i][0];    // 왼쪽
DP[i][i] = DP[i - 1][i - 1] + triangle[i][i]; // 오른쪽

가운데가 핵심인데

이런 식으로 현재 위치에서 왼쪽 위에서 누적된 합과 오른쪽 위에서 누적된 합 중에 더 큰 값을 현재 값과 더해준다
DP[i][j] = Math.max(DP[i - 1][j], DP[i - 1][j - 1]) + triangle[i][j];

import java.util.*;

class Solution {

    public int solution(int[][] triangle) {
        int answer = 0;

        int len = triangle.length;

        int[][] DP = new int[len + 1][len + 1];

        DP[0][0] = triangle[0][0];

        for (int i = 1; i < len; i++) {
            // 맨 왼쪽
            DP[i][0] = DP[i - 1][0] + triangle[i][0];

            // 가운데
            for (int j = 1; j < i; j++)
                DP[i][j] = Math.max(DP[i - 1][j], DP[i - 1][j - 1]) + triangle[i][j];

            // 맨 오른쪽
            DP[i][i] = DP[i - 1][i - 1] + triangle[i][i];
        }

        for (int i = 0; i < len; i++)
            answer = Math.max(DP[len - 1][i], answer);

        return answer;
    }
}

성공적으로 통과!

| 자바 toCharArray 활용법

프로그래머스를 풀다가 자주 사용하게 될 것 같은 함수를 발견하여 정리해둡니다. 

class Main {

    public static void main(String[] args) {
        String s = "Hello World";

        char[] arr = s.toCharArray();

        for(char ch : arr)
            System.out.print(ch+" ");
    }
}

문자열 "Hello World"를 char 배열에 각각 담을 수 있는 함수!
String (문자열) 을 Char형 배열로 바꿔줍니다

결과값

Hello World 가 각각 char 배열에 정상적으로 담긴 것을 확인 할 수 있습니다.

https://school.programmers.co.kr/learn/courses/30/lessons/17680?language=java 

LRU에 대한 개념이 기억이 안나서 찾아보면서 풀어봤던 문제이다.
해야할 작업이 캐시에 있는 상태인지, 없는 상태인지 나눠서 처리해줘야하고
캐시크기가 0인 경우 예외 처리를 해주면 어렵지 않게 풀 수 있는 문제다

import java.util.*;

class Solution {
    public int solution(int cacheSize, String[] cities) {
        int answer = 0;

        /*
        LRU => 가장 오래 참조되지 않은 페이지 교체
        (시간을 기록해야한다는 단점이 있어서 오버헤드)

        cache hit : 해야할 작업이 캐시에 있는 상태
        cache miss : 해야할 작업이 캐시에 없는 상태
        */

        LinkedList<String> list = new LinkedList<>();

        if (cacheSize == 0) 
            return cities.length * 5;
        
        for (int i = 0; i < cities.length; i++) {

            String target = cities[i].toLowerCase();
            // 해야할 작업이 캐시에 있는지 없는지 확인
            boolean flag = false;
            int idx = 0;

            for (int j = 0; j < list.size(); j++) {
                // 있으면
                if (list.get(j).equals(target)) {
                    flag = true;
                    idx = j;
                }
            }

            // cache hit
            if (flag) {
                list.add(list.remove(idx));
                answer++;
            }
            // cache miss
            else {
                if (list.size() >= cacheSize) 
                    list.removeFirst();
                
                list.add(target);
                answer += 5;
            }
        }

        return answer;
    }
}

    List<String> sortedList = new ArrayList<>(importand_document_entities);

    Comparator<String> c = new Comparator<String>() {
        public int compare(String s1, String s2) {
            return Integer.compare(s2.length(), s1.length());
        }
    };

    Collections.sort(sortedList, c);

    // 배열 길이순으로 정
    Arrays.sort(tmp,new Comparator<String>(){
        public int compare(String o1, String o2){

            return Integer.compare(o1.length(), o2.length());
        }
    });

반대순으로 정렬은 compare 내부의 o1,o2끼리 위치만 바꿔주면 된다!

Map에 값을 전체 출력하기 위해서는 entrySet(), keySet() 메소드를 사용하면 되는데 entrySet() 메서드는 key와 value의 값이 모두 필요한 경우 사용하고, keySet() 메서드는 key의 값만 필요한 경우 사용합니다.

방법 01 : entrySet()

Map<String, String> map = new HashMap<String, String>();
map.put("key01", "value01");
map.put("key02", "value02");
map.put("key03", "value03");
map.put("key04", "value04");
map.put("key05", "value05");

// 방법 01 : entrySet()
for (Map.Entry<String, String> entry : map.entrySet()) {
	System.out.println("[key]:" + entry.getKey() + ", [value]:" + entry.getValue());
}

방법 02 : keySet()

Map<String, String> map = new HashMap<String, String>();
map.put("key01", "value01");
map.put("key02", "value02");
map.put("key03", "value03");
map.put("key04", "value04");
map.put("key05", "value05");
        
// 방법 02 : keySet()
for (String key : map.keySet()) {
	String value = map.get(key);
    System.out.println("[key]:" + key + ", [value]:" + value);
}    

Iterator 인터페이스를 사용할 수 없는 컬렉션인 Map에서 Iterator 인터페이스를 사용하기 위해서는 Map에 entrySet(), keySet() 메소드를 사용하여 Set 객체를 반환받은 후 Iterator 인터페이스를 사용하시면 됩니다.

방법 03 : entrySet().iterator()

Map<String, String> map = new HashMap<String, String>();
map.put("key01", "value01");
map.put("key02", "value02");
map.put("key03", "value03");
map.put("key04", "value04");
map.put("key05", "value05");
    
// 방법 03 : entrySet().iterator()
Iterator<Map.Entry<String, String>> iteratorE = map.entrySet().iterator();
while (iteratorE.hasNext()) {
	Map.Entry<String, String> entry = (Map.Entry<String, String>) iteratorE.next();
   	String key = entry.getKey();
   	String value = entry.getValue();
   	System.out.println("[key]:" + key + ", [value]:" + value);
}

방법 04 : keySet().iterator()

Map<String, String> map = new HashMap<String, String>();
map.put("key01", "value01");
map.put("key02", "value02");
map.put("key03", "value03");
map.put("key04", "value04");
map.put("key05", "value05");

// 방법 04 : keySet().iterator()
Iterator<String> iteratorK = map.keySet().iterator();
	while (iteratorK.hasNext()) {
	String key = iteratorK.next();
	String value = map.get(key);
	System.out.println("[key]:" + key + ", [value]:" + value);
}

방법 05 : Lambda 사용

Map<String, String> map = new HashMap<String, String>();
map.put("key01", "value01");
map.put("key02", "value02");
map.put("key03", "value03");
map.put("key04", "value04");
map.put("key05", "value05");

// 방법 05 : Lambda 사용
map.entrySet().stream().forEach(entry-> {
	System.out.println("[key]:" + entry.getKey() + ", [value]:"+entry.getValue());
});

방법 06 : Stream 사용

Map<String, String> map = new HashMap<String, String>();
map.put("key01", "value01");
map.put("key02", "value02");
map.put("key03", "value03");
map.put("key04", "value04");
map.put("key05", "value05");

// 방법 06 : Stream 사용
map.entrySet().stream().forEach(entry-> {
	System.out.println("[key]:" + entry.getKey() + ", [value]:"+entry.getValue());
});
	        
// Stream 사용 - 내림차순
map.entrySet().stream().sorted(Map.Entry.comparingByKey()).forEach(entry-> {
	System.out.println("[key]:" + entry.getKey() + ", [value]:"+entry.getValue());
});

// Stream 사용 - 오름차순
map.entrySet().stream().sorted(Map.Entry.comparingByKey(Comparator.reverseOrder())).forEach(entry-> {
	System.out.println("[key]:" + entry.getKey() + ", [value]:"+entry.getValue());
});

출처: https://tychejin.tistory.com/31 [너나들이 개발 이야기:티스토리]

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

문제 설명

문제 포인트

다리가 비어있는 경우와 비어있지 않은 경우를 크게 if문으로 나누어서 구현
다리가 비어있는 경우는 그냥 단순하게 다리(Queue)에 밀어넣어주면 되고
다리가 비어있지 않은 경우 무게를 견딜수 있으면 Queue에 넣어주고
무게를 견딜수 없으면 '0'을 밀어 넣어준다 ★ 이게 포인트
Queue의 size가 시간이 되는 개념이기때문에 다리에 트럭이 올라오지 않더라고 한칸씩 밀어주기 위해서
'0'을 Queue에 삽입!

import java.util.*;

class Solution {
    public int solution(int bridge_length, int weight, int[] truck_weights) {
        Queue<Integer> qu = new LinkedList<>();

        int current_weight = 0; // 현재무게
        int timer = 0;

        for (int i = 0; i < truck_weights.length; i++) {
            // 다리가 비어있는 경우
            if (qu.isEmpty()) {
                if (truck_weights[i] <= weight) {
                    qu.add(truck_weights[i]);
                    current_weight += truck_weights[i];
                    timer++;
                    continue;
                }
            }
            // 다리가 비어있지 않은 경우
            else {
                while(true){
                    // 다리가 꽉찬 상태면 큐 하나 밀어내기!
                    if (qu.size() >= bridge_length) 
                        current_weight -= qu.poll();
                    
                    // 다리를 건널수있는 상태면 건너기
                    if (current_weight + truck_weights[i] <= weight) {
                        qu.add(truck_weights[i]);
                        current_weight += truck_weights[i];
                        timer++;
                        break;
                    }
                    // 못건너는 상태면 '0'으로 큐를 밀어내기!
                    else {
                        qu.add(0); // 이게 ...★
                        timer++;
                    }

                }

            }
        }

        return timer + bridge_length;
    }
}