우유

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;
    }
}

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

문제 설명

ROR 게임은 두 팀으로 나누어서 진행하며, 상대 팀 진영을 먼저 파괴하면 이기는 게임입니다. 따라서, 각 팀은 상대 팀 진영에 최대한 빨리 도착하는 것이 유리합니다.

지금부터 당신은 한 팀의 팀원이 되어 게임을 진행하려고 합니다. 다음은 5 x 5 크기의 맵에, 당신의 캐릭터가 (행: 1, 열: 1) 위치에 있고, 상대 팀 진영은 (행: 5, 열: 5) 위치에 있는 경우의 예시입니다.

위 그림에서 검은색 부분은 벽으로 막혀있어 갈 수 없는 길이며, 흰색 부분은 갈 수 있는 길입니다. 캐릭터가 움직일 때는 동, 서, 남, 북 방향으로 한 칸씩 이동하며, 게임 맵을 벗어난 길은 갈 수 없습니다.
아래 예시는 캐릭터가 상대 팀 진영으로 가는 두 가지 방법을 나타내고 있습니다.

• 첫 번째 방법은 11개의 칸을 지나서 상대 팀 진영에 도착했습니다.

• 두 번째 방법은 15개의 칸을 지나서 상대팀 진영에 도착했습니다.

위 예시에서는 첫 번째 방법보다 더 빠르게 상대팀 진영에 도착하는 방법은 없으므로, 이 방법이 상대 팀 진영으로 가는 가장 빠른 방법입니다.

만약, 상대 팀이 자신의 팀 진영 주위에 벽을 세워두었다면 상대 팀 진영에 도착하지 못할 수도 있습니다. 예를 들어, 다음과 같은 경우에 당신의 캐릭터는 상대 팀 진영에 도착할 수 없습니다.

게임 맵의 상태 maps가 매개변수로 주어질 때, 캐릭터가 상대 팀 진영에 도착하기 위해서 지나가야 하는 칸의 개수의 최솟값을 return 하도록 solution 함수를 완성해주세요. 단, 상대 팀 진영에 도착할 수 없을 때는 -1을 return 해주세요.

제한사항

• maps는 n x m 크기의 게임 맵의 상태가 들어있는 2차원 배열로, n과 m은 각각 1 이상 100 이하의 자연수입니다.
  • n과 m은 서로 같을 수도, 다를 수도 있지만, n과 m이 모두 1인 경우는 입력으로 주어지지 않습니다.
• maps는 0과 1로만 이루어져 있으며, 0은 벽이 있는 자리, 1은 벽이 없는 자리를 나타냅니다.
• 처음에 캐릭터는 게임 맵의 좌측 상단인 (1, 1) 위치에 있으며, 상대방 진영은 게임 맵의 우측 하단인 (n, m) 위치에 있습니다.

---

 

입출력 예

maps	answer
[[1,0,1,1,1],[1,0,1,0,1],[1,0,1,1,1],[1,1,1,0,1],[0,0,0,0,1]]	11
[[1,0,1,1,1],[1,0,1,0,1],[1,0,1,1,1],[1,1,1,0,0],[0,0,0,0,1]]	-1

입출력 예 설명

입출력 예 #1
주어진 데이터는 다음과 같습니다.

캐릭터가 적 팀의 진영까지 이동하는 가장 빠른 길은 다음 그림과 같습니다.

따라서 총 11칸을 캐릭터가 지나갔으므로 11을 return 하면 됩니다.

입출력 예 #2
문제의 예시와 같으며, 상대 팀 진영에 도달할 방법이 없습니다. 따라서 -1을 return 합니다.

전형적인 BFS 문제다. N X N 에서 최단거리를 구할떄는 BFS! 이건 그냥 공식처럼 외워두자
BFS 를 돌려서 maps[N-1][M-1] 에 최종으로 도달했을때 저장되있는 값을 리턴, maps[N-1][M-1]에 방문한 적이 없으면
-1을 리턴!

import java.util.*;

class Solution {
    
    static boolean[][] visited; // 방문여부체크배열
    
    static int[] dy = {1, 0, -1, 0};
    static int[] dx = {0, 1, 0, -1};
    
    static int N,M;       // 행, 열
    
    public int solution(int[][] maps) {
        int answer = 0;
        
        N = maps.length; // 열 (가로) -> x
        M = maps[0].length;    // 행 (세로) -> y
        
        visited = new boolean[N+1][M+1];
        
        BFS(0 ,0, maps); // BFS 시작
        
        if(visited[N-1][M-1])
            return maps[N-1][M-1];   
        else
            return -1;
    }
    public static void BFS(int y ,int x, int[][] maps){
        
        Queue<int[]> qu = new LinkedList<int[]>();
        
        qu.offer(new int[] {y, x});
        
        visited[y][x] = true;
        
        while(!qu.isEmpty()){
            int curY = qu.peek()[0];
            int curX = qu.peek()[1];
            
            qu.poll();
            
            for(int i =0; i<4; i++){
                int ny = curY + dy[i];
                int nx = curX + dx[i];
                
                //지도 범위내에서 벗어나면
                if(0 <= nx && 0 <= ny && nx < M && ny < N){
                    if(!visited[ny][nx] && maps[ny][nx] !=0){
                        qu.offer(new int[] {ny,nx});
                
                         maps[ny][nx] = maps[curY][curX] + 1;

                        visited[ny][nx] = true;
                    }           
                }
            }
        }
    }
}