우유

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

코드 설명

정점, 간선이 주어진 입력 배열에서 인접리스트를 만들어서
BFS 로 가장 먼 거리를 구했다.DFS와 BFS는 많이 풀면 풀수록 다양한 개념들이 많이 나온다.
다 이해했다고 생각하지말고 계속 여러번 반복해서 풀어봐야겠다.

import java.util.*;

class Solution {
    
    static int[] visited;
    static ArrayList<ArrayList<Integer>> al;
    
    public int solution(int n, int[][] edge) {
        int answer = 0;
        
        al = new ArrayList<>();
        visited = new int[n + 1];
        
        // 정점이 6개까지 있으므로 0~6으로 선언해야되는거 주의
        for(int i = 0; i <= n; i++)
            al.add(new ArrayList<Integer>());
        
        for(int i = 0; i < edge.length; i++){
            al.get(edge[i][0]).add(edge[i][1]);
            al.get(edge[i][1]).add(edge[i][0]);
        }
        
        BFS(1);
        
        Arrays.sort(visited);
        
        int max = visited[n];
        
        for(int i = 0; i <= n; i++){
            if(max == visited[i])
                answer++;
        }
        
        return answer;
    }
    
    public static void BFS(int V){
        Queue<Integer> qu = new LinkedList<>();
        
        qu.add(1);
        visited[1] = 1;
        
        while(!qu.isEmpty()){
            int cur = qu.poll();
            
            for(int next : al.get(cur)) {
                
                if(visited[next] == 0){
                    visited[next] = visited[cur] + 1;
                    qu.add(next);
                }
            }
        }
    }
}

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

코드 설명

최솟값을 만들기 위해서는 가장 큰수와 작은수를 곱해주어야 하기 때문에
문자열 A와 문자열 B를 오름차순, 내림차순으로 각각 정렬해서
같은 인덱스끼리 곱해주려고 했으나,,
Arrays.sort 함수의 내림차순 정렬이 기억이 나지않아서
편법으로 저렇게 처리했다.

자바 Int 내림차순 정렬은 이렇게 활용하면 된다. 기억하자.. ★

Integer[] arr3 = Arrays.stream(arr).boxed().toArray(Integer[]::new);
Arrays.sort(arr3, Collections.reverseOrder());

import java.util.*;

class Solution {
    public int solution(int[] A, int[] B) {
        int answer = 0;

        Arrays.sort(A);
        Arrays.sort(B);

        for (int i = 0; i < A.length; i++) {
            answer += A[i] * B[B.length - i - 1];
        }

        return answer;
    }
}

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

코드 설명

1. 문자열을 split 함수로 분리
2. String 배열을 Integer 형 배열로 바꿔서 ArrayList에 추가
3. Collections.sort 함수를 활용해서 오름차순으로 정렬
4. ArrayList에서 첫번째 인덱스(최소값) , 마지막 인덱스(최대값)을 꺼내 StringBuilder에 append

import java.util.*;

class Solution {
    public String solution(String s) {
        ArrayList<Integer> al = new ArrayList<>();
        StringBuilder sb = new StringBuilder();
        
        String arr[] = s.split(" ");
        
        for(int i = 0; i < arr.length; i++){
            al.add(Integer.parseInt(arr[i]));
        }
        
        Collections.sort(al);
        
        sb = sb.append(al.get(0) + " ");
        sb = sb.append(al.get(al.size()-1));
        
        return sb.toString();
    }
}

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

코드 설명

끝말잇기 규칙을 체크해야 되는 로직을 구현해야한다.
1. 마지막 사람이 말한 단어에서 마지막 문자와 현재 사람이 말한 단어의 첫번째 문자가 일치하는지 (startsWith 함수,
마지막 단어를 순서대로 꺼내기 위해서 Stack을 활용)
2. 현재 말한 사람의 단어가 이전에 중복된 적이 있는지 (HashMap)
각각의 조건을 체크해 준 후 이상이 없으면 stack과 map에 각각 push, put 해주었고,
조건이 거짓 판별이 나면 몇번 째 사람인지와 몇바퀴 돌았는지 체크해서 각각 answer 배열에 넣어주었다.

import java.util.*;
class Solution {
    public int[] solution(int n, String[] words) {
        int[] answer = new int[2];

        HashMap<String, Integer> map = new HashMap<>();
        Stack<String> stack = new Stack<>();

        for (int i = 0; i < words.length; i++) {

            if (!stack.isEmpty()) {
                String last_word = stack.peek();
                if (words[i].startsWith(last_word.substring(last_word.length() - 1, last_word.length())) 
                        && !map.containsKey(words[i])) {
                    stack.push(words[i]);
                    map.put(words[i], i % n);
                } else {
                    answer[0] = i % n + 1;
                    answer[1] = i / n + 1;
                    break;
                }
            } else {
                stack.push(words[i]);
                map.put(words[i], i % n);
            }
        }
        
        return answer;
    }
}

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

코드 설명

Stack 을 활용할 수 있는 문제였다.
stack이 비어있는 것을 체크하고
')' 가 들어올때 '(' 가 없으면 break를 걸어
false 를 return 했다.

import java.util.*;

class Solution {
    boolean solution(String s) {
        boolean answer = true;

        Stack<Character> stack = new Stack<>();
        
        for(int i = 0; i < s.length(); i++){
            char ch = s.charAt(i);
            
            if(ch == '(') {
                stack.push('(');
            }
            else if(ch == ')'){
                if(!stack.isEmpty()){
                    if(stack.peek() == '('){
                        stack.pop();
                    }
                }
                else {
                    answer = false;
                    break;
                }                
            }
        }
        
        if(!stack.isEmpty())
            answer = false;
        
        return answer;
    }
}

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

코드 설명

문자열에서 첫번째 문자는 항상 대문자
두번째 문자는 항상 소문자
마지막은 공백 추가
이 로직 대로 StringBuilder 에 append 해주었고,

시간을 생각보다 소비했던건 테스트케이스 8번에서 "3people unFollowed me " 이런식으로
입력값 s 문자열에도 마지막 공백이 추가되어서 이런 경우를 따로 if문 처리해서 따로 sb.append(" ")
처리를 해주어야 했다.

class Solution {
    public String solution(String s) {
        String[] arr = s.split(" ");
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < arr.length; i++) {
            if (arr[i].length() == 0) {
                sb.append(" ");
            } else {
                sb = sb.append(arr[i].substring(0, 1).toUpperCase());
                sb = sb.append(arr[i].substring(1, arr[i].length()).toLowerCase());
                sb = sb.append(" ");
            }
        }

        sb.delete(sb.length() - 1, sb.length());

        if (s.substring(s.length() - 1, s.length()).equals(" ")) {
            sb.append(" ");
        }
        
        return sb.toString();
    }
}

코드 설명

문제 포인트는
1. 3개의 벽을 세울 수 있는 모든 경우의 수를 구해서 새롭게 복사한 COPY_MAP을 각각 만드는 것
여기서 세울 수 있는 경우의 수가 엄청 많은데 이를 하나하나 다 BFS를 돌려봐야 한다.
2. 1번에서 새운 MAP 에서 BFS 돌려서 안전거리의 영역을 카운트해서 그 안전거리의 최대값을 출력

DFS와 BFS 를 동시에 연습할수 있는 아주 좋은 문제였다.
 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {

    static int N, M;
    static int[][] map;
    static int[] dy = {1, 0, -1, 0};
    static int[] dx = {0, 1, 0, -1};
    static int ans = Integer.MIN_VALUE;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        map = new int[N][M];

        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < M; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        DFS(0);

        System.out.println(ans);
    }

    public static void DFS(int cnt) {
        if (cnt == 3) {
            BFS();
            return;
        }

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (map[i][j] == 0) {
                    map[i][j] = 1;
                    DFS(cnt + 1);
                    map[i][j] = 0;
                }
            }
        }
    }

    public static void BFS() {
        // 벽을 새로 새울떄마다 배열 초기화
        int[][] copy_map = new int[N][M];

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                copy_map[i][j] = map[i][j];
            }
        }
        Queue<Node> qu = new LinkedList<>();

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (copy_map[i][j] == 2) {
                    qu.add(new Node(i, j));
                }
            }
        }

        while (!qu.isEmpty()) {
            Node curNode = qu.poll();

            for (int i = 0; i < 4; i++) {
                int ny = curNode.y + dy[i];
                int nx = curNode.x + dx[i];

                if (ny < 0 || nx < 0 || N <= ny || M <= nx) continue;

                if (copy_map[ny][nx] == 0) {
                    copy_map[ny][nx] = 2;
                    qu.add(new Node(ny, nx));
                }


            }

        }
        int cnt = 0;

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (copy_map[i][j] == 0) {
                    cnt++;
                }
            }
        }
        ans = Math.max(cnt, ans);
    }


    public static class Node {
        int y;
        int x;

        public Node(int y, int x) {
            this.y = y;
            this.x = x;
        }
    }

}

https://www.acmicpc.net/problem/14500

코드 설명

테트리스의 모양처럼 생긴 블록들이 알고보면 DFS의 방향대로 탐색할때의 모양이라는 것을 알아낼 수 있었다.
DFS를 visited배열을 true 해주면서 depth가 4일때까지 돌리고 빠져나오면서 visited 배열을 false 해주는 백트래킹 방식으로 구현하였다.

여기서 핵심인 부분은 'ㅏ,ㅗ,ㅜ,ㅓ' 에 대한 블록을 어떻게 처리해줄까였는데
나는 cnt == 2 일때 arr[ny][nx] 의 값을 더해준 뒤 다른 ny,nx가 아닌 다른 방향으로 DFS를 한번 더 돌려서
sum 값을 계산하였다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {

    static int N, M;
    static int[][] arr;
    static boolean[][] visited;
    static int[] dy = {1, -1, 0, 0};
    static int[] dx = {0, 0, 1, -1};
    static int ans = Integer.MIN_VALUE;

    public static void main(String[] agrs) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        arr = new int[N][M];
        visited = new boolean[N][M];

        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < M; j++) {
                arr[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                visited[i][j] = true;
                DFS(i, j, 0, 0);
                visited[i][j] = false;
            }
        }
        System.out.println(ans);
    }

    public static void DFS(int y, int x, int sum, int cnt) {
        if (cnt == 4) {
            ans = Math.max(sum, ans);
            return;
        }

        for (int i = 0; i < 4; i++) {
            int ny = y + dy[i];
            int nx = x + dx[i];

            if (ny < 0 || nx < 0 || N <= ny || M <= nx)
                continue;

            if (visited[ny][nx])
                continue;

            if (cnt == 2) {
                visited[ny][nx] = true;
                DFS(y, x, sum + arr[ny][nx], cnt + 1);
                visited[ny][nx] = false;
            }

            visited[ny][nx] = true;
            DFS(ny, nx, sum + arr[ny][nx], cnt + 1);
            visited[ny][nx] = false;
        }

    }
}

https://www.acmicpc.net/problem/15686

코드 설명

BFS로 모든 경로를 다 찾으려고 하면 당연히 시간초과가 나버린다.
집에서 치킨집의 조합의 경우의 수 만큼 거리를 백트래킹으로 구하여 그것의 최소값을 구하면 된다.
(이 아이디어를 생각해내는데 꽤 오래걸렸다..)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class Main {
    static int N, M;
    static int[][] arr;
    static boolean[] visited;
    static ArrayList<Node> chickenList = new ArrayList<>();
    static ArrayList<Node> houseList = new ArrayList<>();
    static int answer = Integer.MAX_VALUE;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        arr = new int[N + 1][N + 1];


        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());

            for (int j = 0; j < N; j++) {
                arr[i][j] = Integer.parseInt(st.nextToken());

                if (arr[i][j] == 1)
                    houseList.add(new Node(i, j));

                if (arr[i][j] == 2)
                    chickenList.add(new Node(i, j));
            }
        }

        visited = new boolean[chickenList.size()];

        DFS(0, 0);
        System.out.println(answer);
    }

    public static void DFS(int idx, int cnt) {
        if (cnt == M) {

            int res = 0;

            for (int i = 0; i < houseList.size(); i++) {
                int sum = Integer.MAX_VALUE;
                for (int j = 0; j < chickenList.size(); j++) {
                    if (visited[j]) {
                        // 각 치킨집에서 집까지의 거리의 최소값
                        int distance = Math.abs(chickenList.get(j).y - houseList.get(i).y) + Math.abs(chickenList.get(j).x - houseList.get(i).x);
                        sum = Math.min(sum, distance);
                    }
                }
                res += sum;
            }
            answer = Math.min(answer, res);
            return;
        }

        for (int i = idx; i < chickenList.size(); i++) {
            visited[i] = true;
            DFS(i + 1, cnt + 1);
            visited[i] = false;
        }
    }

    public static class Node {
        int x;
        int y;

        public Node(int y, int x) {
            this.x = x;
            this.y = y;

        }
    }
}

https://www.acmicpc.net/problem/3190

코드 설명

이중 for문에서 빼낼려고 이상한 짓 하다가 시간을 많이 잡아먹었던 문제였다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {

    static Deque<int[]> qu = new LinkedList<>();
    static HashMap<Integer, String> map = new HashMap<>();
    static boolean[][] apple;
    static int[] dy = {0, 1, 0, -1};
    static int[] dx = {1, 0, -1, 0};
    static int N, K, L;
    static int direction = 0;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        N = Integer.parseInt(br.readLine());
        K = Integer.parseInt(br.readLine());

        apple = new boolean[101][101];

        // 사과 맵
        for (int i = 0; i < K; i++) {
            st = new StringTokenizer(br.readLine());

            int y = Integer.parseInt(st.nextToken());
            int x = Integer.parseInt(st.nextToken());

            apple[y][x] = true;
        }

        L = Integer.parseInt(br.readLine());

        //
        for (int i = 0; i < L; i++) {
            st = new StringTokenizer(br.readLine());

            int X = Integer.parseInt(st.nextToken());
            String C = st.nextToken();
            map.put(X, C);
        }

        // 이중 포문 break를 사용하지 않기 위한?
        solve();
    }

    private static void solve() {
        int time = 0;

        int curY = 1;
        int curX = 1;

        qu.add(new int[]{1, 1});

        while (true) {
            int ny = curY + dy[direction];
            int nx = curX + dx[direction];

            // 맵 범위에 있는지, 몸통이랑 부딪혔는지 확인
            if (GameoverCheck(ny, nx))
                break;

            time++;

            qu.add(new int[]{ny, nx});

            // 사과가 있으면
            if (apple[ny][nx])
                apple[ny][nx] = false;
                // 사과가 없으면
            else {
                qu.poll();
            }

            if (map.containsKey(time)) {

                if (map.get(time).equals("D")) {
                    direction++;
                    if(direction == 4)
                        direction = 0;
                } else {
                    direction--;
                    if(direction == -1)
                        direction = 3;
                }
            }

            curY = ny;
            curX = nx;
        }
        System.out.println(time + 1);
    }

    private static boolean GameoverCheck(int ny, int nx) {
        boolean flag = false;

        // 범위에 벗어나면
        if (ny < 1 || nx < 1 || N < ny || N < nx)
            flag = true;

        // 몸통에 부딪히면
        for (int[] arr : qu) {

            if (arr[0] == ny && arr[1] == nx) {

                flag = true;
                break;
            }
        }

        return flag;
    }
}