BLOG :||

import java.util.*;
public class main {
    public static void main(String[] args) {
    Solution s = new Solution();
    System.out.println(Arrays.toString(s.Chap09DijkstraGuide(6, 11, 1
            , new int[][]{{1,2,2}
                         ,{1,3,5}
                         ,{1,4,1}
                         ,{2,3,3}
                         ,{2,4,2}
                         ,{3,2,3}
                         ,{3,6,5}
                         ,{4,3,3}
                         ,{4,5,1}
                         ,{5,3,1}
                         ,{5,6,2}})));
    System.out.println(Arrays.deepToString(s.Chap09FloydWarshallGuide(4,7, new int[][]{{1,2,4}
                                                                                             ,{1,4,6}
                                                                                             , {2,1,3},{2,3,7},{3,1,5},{3,4,4},{4,3,2}})));
    }
}
class Solution {

    public int[] Chap09DijkstraGuide(int n, int m, int start, int[][] costs) {
        int[] answer = new int[n];
        Arrays.fill(answer, Integer.MAX_VALUE);

        boolean[] visited = new boolean[n];

        List<Edge>[] list = new ArrayList[m];//꼭 기억해두자.
        for(int i = 0; i<n;++i)
            list[i] = new ArrayList<>();

        for(int i = 0; i<m;++i) {
            list[costs[i][0]-1].add(new Edge(costs[i][1]-1, costs[i][2]));
        }

        Queue<Edge> queue = new PriorityQueue<Edge>();
        queue.add(new Edge(start-1, 0));

        while(!queue.isEmpty()) {
            Edge q = queue.poll();

            if(answer[q.node] > q.cost) {
                answer[q.node] = q.cost;
                visited[q.node] = true;
            }
            for(Edge edge : list[q.node]) {
                if(!visited[edge.node]) {
                    if(answer[edge.node] > edge.cost + q.cost) {
                        queue.add(new Edge(edge.node, edge.cost+q.cost));
                    }
                }
            }
        }
        return answer;
    }
    public int[][] Chap09FloydWarshallGuide(int n, int m,int[][] costs) {
        int[][] answer = new int[n][n];
        for(int[] a : answer)
            Arrays.fill(a, Integer.MAX_VALUE); //값 초기화

        for(int i = 0; i<n;++i)
            answer[i][i] = 0;//자기 자신으로는 0

        for(int i = 0; i<m;++i) {
            answer[costs[i][0]-1][costs[i][1]-1] = costs[i][2]; //기본 costs 추가
        }
        for(int i  = 0; i<n;++i) {
            for(int j = 0; j<n;++j) {
                for(int k = 0; k<n;++k) {
                    int tmpMin = answer[j][i] + answer[i][k];// 이 부분은 까먹지 말자
                    if(tmpMin < 0)
                        tmpMin = Integer.MAX_VALUE; //MAX_VALUE 이상의 값이 되면 음수가 되므로 음수인 경우 MAX_VALUE로 초기화
                    answer[j][k] = (answer[j][k] < tmpMin) ? answer[j][k] : tmpMin;
                }
            }
        }

        return answer;
    }
}
class Edge implements Comparable<Edge> {
    int node;
    int cost;

    public Edge(int node, int cost) {
        this.node = node;
        this.cost = cost;
    }
    public int compareTo(Edge n) {
        if(cost < n.cost) {
            return -1;
        }
        else if(cost > n.cost) {
            return 1;
        }
        else if(node < n.node) {
            return -1;
        }
        else if(node > n.node) {
            return 1;
        }
        else
            return 0;
    }
}

다익스트라 알고리즘은 start node에서 각 노드 별로 갈 수 있는 최소 거리를 찾는 과정이다.

플루이드 워셜 알고리즘은 모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구해야 할 때 사용하는 알고리즘이다.

다익스트라 알고리즘은 Greedy, 플루이드 워셜 알고리즘은 DP

import java.util.*;
public class main {
    public static void main(String[] args) {
    Solution s = new Solution();
    System.out.println(s.Chap09Example01(5,7,new int[][]{{1,2},{1,3}, {1,4}, {2,4}, {3,4},{3,5}, {4,5}},4,5));
    System.out.println(s.Chap09Example01(4,2, new int[][]{{1,3},{2,4}},3,4));
    System.out.println(Arrays.toString(s.Chap09Example02(3,2,1, new int[][]{{1,2,4}, {1,3,2}})));
    }
}
class Solution {
    public int Chap09Example01(int n, int m, int[][] lines, int x, int k) {
        int answer = 0;

        int[][] distance = new int[n][n];
        for(int[] d : distance)
            Arrays.fill(d, Integer.MAX_VALUE);

        for(int i = 0; i<n;++i) {
            distance[i][i] = 0;
        }
        for(int i = 0; i<m;++i) {
            distance[lines[i][0]-1][lines[i][1]-1] = 1;
            distance[lines[i][1]-1][lines[i][0]-1] = 1;
        }
        for(int h = 0; h<n;++h) {
            for(int i = 0; i<n;++i) {
                for(int j = 0; j<n;++j) {
                    int tmpMin = distance[i][h] + distance[h][j];
                    if(tmpMin < 0)
                        tmpMin = Integer.MAX_VALUE;
                    distance[i][j] = (distance[i][j] < tmpMin) ? distance[i][j] : tmpMin;
                }
            }
        }
        if(distance[0][k-1] == Integer.MAX_VALUE)
            return -1;
        if(distance[k-1][x-1] == Integer.MAX_VALUE)
            return -1;
        answer = distance[0][k-1] + distance[k-1][x-1];
        return answer;
    }
    public int[] Chap09Example02(int n, int m, int c, int[][] costs) {
        int[] answer = new int[2];
        int[] distance = new int[n];
        boolean[] visited = new boolean[n];
        Queue<Edge> queue = new PriorityQueue<>();
        List<Edge>[] list = new ArrayList[n];
        Arrays.fill(distance, Integer.MAX_VALUE);
        for(int i = 0; i<n;++i)
            list[i] = new ArrayList<>();

        for(int i = 0; i<m;++i) {
            list[costs[i][0]-1].add(new Edge(costs[i][1]-1, costs[i][2]));
        }
        //c->start
        distance[c-1] = 0;

        queue.add(new Edge(c-1,0));

        while(!queue.isEmpty()) {
            Edge q = queue.poll();
            if(distance[q.node] > q.cost) {
                distance[q.node] = q.cost;
                visited[q.node] = true;
            }
            for(Edge edge : list[q.node]) {
                if(!visited[edge.node]) {
                    if(distance[edge.node] > edge.cost + q.cost) {
                        queue.add(new Edge(edge.node, edge.cost+q.cost));
                    }
                }
            }
        }

        for(int i = 0; i<n;++i) {
            if(visited[i]) {
                System.out.println("c");
                answer[0]++;
                answer[1] = (distance[i] > answer[1]) ? distance[i] : answer[1];
            }

        }
        return answer;
    }
}
class Edge implements Comparable<Edge> {
    int node;
    int cost;

    public Edge(int node, int cost) {
        this.node = node;
        this.cost = cost;
    }
    public int compareTo(Edge n) {
        if(cost < n.cost) {
            return -1;
        }
        else if(cost > n.cost) {
            return 1;
        }
        else if(node < n.node) {
            return -1;
        }
        else if(node > n.node) {
            return 1;
        }
        else
            return 0;
    }
}

오랜만에 보니까 엄청 어렵다. 책은 파이썬으로 되어 있어서 자바에 맞춰 이해하려고 고민 좀 했다.

import java.util.*;
public class main {
    public static void main(String[] args) {
    Solution s = new Solution();
    System.out.println(s.Chap08Example01TopDown(26));
    System.out.println(s.Chap08Example01BottomUp(26));
    System.out.println(s.Chap08Example02BottomUp(4, new int[]{1,3,1,5}));
    System.out.println(s.Chap08Example02TopDown(4, new int[]{1,3,1,5}));
    System.out.println(s.Chap08Example03BottomUp(3));
    System.out.println(s.Chap08Example03TopDown(3));
    System.out.println(s.Chap08Example04TopDown(2,15,new int[] {2,3}));
    System.out.println(s.Chap08Example04TopDown(3,4,new int[] {3,5,7}));
    System.out.println(s.Chap08Example04BottomUp_Guide(2,15,new int[] {2,3}));
    System.out.println(s.Chap08Example04BottomUp_Guide(3,4,new int[] {3,5,7}));
    }
}
class Solution {

    public int Chap08Example01TopDown(int n) {
        int[] memory = new int[n+1];

        return Example01TopDown(n, memory);
    }
    public int Chap08Example01BottomUp(int n) {
        int[] memory = new int[n+1];
        for(int i = 2; i<=n;++i) {
            int d5 = 300001;
            if(i % 5 == 0) {
                d5 = memory[i/5]+1;
            }
            int d3 = 300001;
            if(i % 3 == 0) {
                d3 = memory[i/3]+1;
            }
            int d2 = 300001;
            if(i % 2 == 0) {
                d2 = memory[i/2]+1;
            }
            int m1 = memory[i-1]+1;
            int min = (d5 < d3) ? d5 : d3;
            min = (min < d2) ? min : d2;
            min = (min < m1) ? min : m1;
            memory[i] = min;
        }
        return memory[n];
    }
    public int Example01TopDown(int n, int[] memory) {
        if(n == 1) {
            return 0;
        }
        if(memory[n] != 0) {
            return memory[n];
        }
        else {
            int d5 = 300001;
            if( n % 5 == 0) {
                d5 = Example01TopDown(n /5 , memory)+1;
            }
            int d3 = 300001;
            if(n % 3 == 0) {
                d3 = Example01TopDown(n/3, memory)+1;
            }
            int d2 = 300001;
            if(n % 2 == 0) {
                d2 = Example01TopDown(n/2, memory)+1;
            }
            int m1 = Example01TopDown(n-1, memory)+1;

            int min = (d5 < d3) ? d5 : d3;
            min = (min < d2) ? min : d2;
            min = (min < m1) ? min : m1;
            memory[n] = min;
            return memory[n];
        }
    }
    public int Chap08Example02BottomUp(int n, int[] foods) {
        int[] maxFoods = new int[n];

        maxFoods[0] = foods[0];
        maxFoods[1] = (foods[0] > foods[1]) ? foods[0] : foods[1];
        for(int i = 2; i<n;++i) {
            maxFoods[i] = (maxFoods[i-1] > maxFoods[i-2]+foods[i]) ? maxFoods[i-1] : maxFoods[i-2]+foods[i];
        }
        return maxFoods[n-1];
    }
    public int Chap08Example02TopDown(int n, int[] foods) {
        int[] memory = new int[n];
        memory[0] = foods[0];
        memory[1] = (foods[1] > foods[0]) ? foods[1] : foods[0];
        Example02TopDown(n-1, memory, foods);
        return memory[n-1];
    }
    public int Example02TopDown(int n, int[] memory, int[] foods) {
        if(memory[n] != 0) {
            return memory[n];
        }
        int n1 = Example02TopDown(n-1, memory, foods);
        int n2 = Example02TopDown(n-2, memory, foods)+foods[n];
        memory[n] = (n1 > n2) ? n1 : n2;
        return memory[n];
    }
    public int Chap08Example03BottomUp(int n) {
        int[] memory = new int[n+1];
        memory[1] = 1;
        if(n == 1)
            return memory[1];
        memory[2] = 3;
        if(n == 2)
            return memory[2];
        for(int i = 3; i<=n;++i) {
            memory[i] = memory[i-1]+ memory[i-2]*2;
        }
        return memory[n]%796796;
    }
    public int Chap08Example03TopDown(int n) {
        int[] memory = new int[n+1];
        if(n>=1) {
            memory[1] = 1;
        }
        if(n>=2) {
            memory[2] = 3;
        }
        Example03TopDown(n, memory);
        return memory[n];
    }
    public int Example03TopDown(int n, int[] memory) {
        if(memory[n] != 0)
            return memory[n];
        memory[n] = Example03TopDown(n-2, memory) *2 + Example03TopDown(n-1,memory);
        return memory[n];
    }
    public int Chap08Example04TopDown(int n, int m, int[] coins) {
        int[] memory = new int[m+1];
        for(int c : coins) {
            if(c <= m)
                memory[c] = 1;
        }
        Example04TopDown(m,coins,memory);
        if(memory[m] == 10001) {
            return -1;
        }
        return memory[m];
    }
    public int Example04TopDown(int m, int[] coins, int[] memory) {
        if(m == 0)
            return 0;
        if(memory[m] != 0) {
            return memory[m];
        }
        int min = 10001;
        int tmp = 0;
        for(int c : coins) {
            if(m-c >= 0) {
                tmp = Example04TopDown(m-c, coins, memory)+1;
                min = (min < tmp) ? min : tmp;
            }
        }
        memory[m] = min;
        return memory[m];
    }
    public int Chap08Example04BottomUp_Guide(int n, int m, int[] coins) {
        int[] memory = new int[10001];
        Arrays.fill(memory,10001);//기억해두자. for문 반복 돌리지 말고..
        memory[0] = 0;
        for(int i = 0; i < n;++i) {
            for(int j = coins[i]; j<=m;++j) {
                if(memory[j-coins[i]] != 10001) {
                    memory[j] = (memory[j] < memory[j-coins[i]] +1) ?  memory[j] : memory[j-coins[i]] + 1;
                }
            }
        }
        if(memory[m] == 10001)
            return -1;
        return memory[m];
    }
}

---

다른 챕터와 DP는 언제나 사람 머리 아프게 하는 파트다. Top-Down, Bottom-Up이 어려운 것은 아니지만 이 문제가 DP로 풀어야 하는지를 빠르게 인지를 하는 것이 중요하다. 그리고 DP로 풀었다 하더라도 정확한 공식을 찾아야 한다.

Example03 바닥 공사 문제에서 경우의 수가 어떻게 되는지 문제만 보고서는 이해가 안가서 그림을 그려보았는데도 아리까리했다.

평소에는 항상 재귀로 문제를 푸는게 습관처럼 되어있어서 Bottom-Up을 사용하는 연습을 들이고자 Top-Down, Bottom-Up을 같이 써봤다.

Example04는 Bottom-Up으로 될거라고 생각도 안했는데..

징글맞게 어렵다 진짜..

import java.util.*;
public class main {
    public static void main(String[] args) {

        Solution s = new Solution();

        boolean[] a = s.Chap07Example01(5, new int[]{8,3,7,9,2}, 3, new int[]{5,7,9});//이진탐색
        for(boolean aa : a)
            System.out.print(aa + " ");
        System.out.println();
        boolean[] b = s.Chap07Example01_Guide01(5, new int[]{8,3,7,9,2}, 3, new int[]{5,7,9});//계수정렬
        for(boolean aa : b)
            System.out.print(aa + " ");
        System.out.println();
        boolean[] c = s.Chap07Example01_Guide02(5, new int[]{8,3,7,9,2}, 3, new int[]{5,7,9});//집합자료형
        for(boolean aa : c)
            System.out.print(aa + " ");
        System.out.println();
        System.out.println(s.Chap07Exmaple02(4,6,new int[]{19,15,10,17}));
    }
}
class Solution {


    public boolean[] Chap07Example01(int n, int[] stock, int m, int[] find) {
        boolean[] answer = new boolean[m];

        Arrays.sort(stock);

        for(int i = 0; i<m;++i) {
            int start = 0;
            int mid = stock.length/2;
            int end = stock.length-1;
            while(start <= end) {
                if(stock[mid] < find[i]) {
                    start = mid+1;
                    mid = (end+start)/2;
                }
                else if(stock[mid] > find[i]) {
                    end = mid-1;
                    mid = (end+start)/2;
                }
                else {
                    answer[i] = true;
                    break;
                }
            }
        }
        return answer;
    }
    public boolean[] Chap07Example01_Guide01(int n, int[] stock, int m, int[] find) {
        boolean[] answer= new boolean[m];

        int[] stocks = new int[1000001];
        for(int s : stock)
            stocks[s] = 1;
        for(int i = 0; i<m;++i) {
            if(stocks[find[i]] == 1)
                answer[i] = true;
        }

        return answer;
    }
    public boolean[] Chap07Example01_Guide02(int n, int[] stock, int m, int[] find) {
        boolean[] answer= new boolean[m];
        Set<Integer> set = new HashSet<>();
        for(int s: stock)
            set.add(s);
        for(int i = 0; i<m;++i) {
            if(set.contains(find[i]))
                answer[i] = true;
        }
        return answer;
    }
    public int Chap07Exmaple02(int n, int m, int[] ddeok) {
        int answer = 0;

        Arrays.sort(ddeok);
        int start = 0;
        int end = ddeok[ddeok.length - 1];
        int mid = (start + end) / 2;
        while(true) {
            int tmp = 0;
            for(int d: ddeok) {
                if(d > mid) {
                    tmp += d-mid;
                }
            }
            if(tmp == m) {
                answer = mid;
                break;
            }
            else if(tmp < m) {
                end = mid-1;
                mid = (start+end)/2;
            }
            else if(tmp > m) {
                start = mid+1;
                mid = (start+end)/2;
            }
        }
        return answer;
    }
}

개념은 쉽지만 자칫 실수하면 찾기 힘들다. 개념을 맞게 다 써놨음에도 뭔가 오류가 생겼어서 뭐가 문제였지 하고 쳐다보고 있었다.

import java.util.*;
public class main {
    public static void main(String[] args) {

        Solution s = new Solution();

        System.out.println(Arrays.toString(s.Chap06Exmaple01(3, new int[] {15,27,12})));
        System.out.println(Arrays.toString(s.Chap06Example02(2, new String[]{"홍길동","이순신"}, new int[]{95,77})));
        System.out.println(s.Chap06Example03(5,3, new int[]{1,2,5,4,3}, new int[]{5,5,6,6,5}));
    }
}
class Solution {

    public int[] Chap06Exmaple01(int n, int[] arr) {

        List<Integer> list = new ArrayList<>();

        for(int a : arr)
            list.add(a);

        Collections.sort(list);
        Collections.reverse(list);

        for(int i = 0; i<arr.length;++i)
            arr[i] = (int)list.get(i);

        return arr;
    }
    public String[] Chap06Example02(int n, String[] name, int[] score) {
        String[] answer = new String[n];
        List<Score> list = new ArrayList<>();

        for(int i = 0; i<n;++i)
            list.add(new Score(name[i], score[i]));

        Collections.sort(list);

        for(int i = 0; i<n;++i)
            answer[i] = list.get(i).name;

        return answer;
    }
    public int Chap06Example03(int n, int k, int[] arrA, int[] arrB) {
        int answer = 0;

        Arrays.sort(arrA);
        Arrays.sort(arrB);
        for(int i = 0; i<k; ++i) {
            if(arrA[i] < arrB[arrB.length-i-1]) {
                arrA[i] = arrB[arrB.length-i-1];
            }
            else
                break;
        }
        for(int a : arrA)
            answer += a;
        return answer;
    }
}
class Score implements Comparable<Score> {
    public int score;
    public String name;
    public Score(String name, int score) {
        this.score = score;
        this.name = name;
    }
    @Override
    public int compareTo(Score s) {
        if(s.score < score)
            return 1;
        else if(s.score > score)
            return -1;
        else
            return 0;
    }
}

---

두 개 이상의 값을 동시에 정렬하라고 하면 클래스 만들고 Comaparable 상속 받고 하는게 내 기준에선 가장 편하다.

정렬 문제가 나올 때 라이브러리를 못쓰게 하지 않으면 라이브러리 그대로 쓰는게 제일 좋기도 하고

책도 답안을 보니 직접 구현하지 않더라...

import java.util.*;
public class main {
    public static void main(String[] args) {

        Solution s = new Solution();

        System.out.println(s.Chap05Example10(15,14,new int[][]{
                {0,0,0,0,0,1,1,1,1,0,0,0,0,0},//1
                {1,1,1,1,1,1,0,1,1,1,1,1,1,0},//2
                {1,1,0,1,1,1,0,1,1,0,1,1,1,0},//3
                {1,1,0,1,1,1,0,1,1,0,0,0,0,0},//4
                {1,1,0,1,1,1,1,1,1,1,1,1,1,1},//5
                {1,1,0,1,1,1,1,1,1,1,1,1,0,0},//6
                {1,1,0,0,0,0,0,0,0,1,1,1,1,1},//7
                {0,1,1,1,1,1,1,1,1,1,1,1,1,1},//8
                {0,0,0,0,0,0,0,0,0,1,1,1,1,1},//9
                {0,1,1,1,1,1,1,1,1,1,1,0,0,0},//10
                {0,0,0,1,1,1,1,1,1,1,1,0,0,0},//11
                {0,0,0,0,0,0,0,1,1,1,1,0,0,0},//12
                {1,1,1,1,1,1,1,1,1,1,0,0,1,1},//13
                {1,1,1,0,0,0,1,1,1,1,1,1,1,1},//14
                {1,1,1,0,0,0,1,1,1,1,1,1,1,1}//15
                }));
        System.out.println(s.Chap05Example11(5,6, new int[][]{
                {1,0,1,0,1,0},
                {1,1,1,1,1,1},
                {0,0,0,0,0,1},
                {1,1,1,1,1,1},
                {1,1,1,1,1,1}
                }));


    }
}
class Solution {
    public int Chap05Example10(int m, int n, int[][] blocks) {
        int answer = 0;
        int[][] visited = new int[m][n];

        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (visited[i][j] == 0 && blocks[i][j] == 0) {
                    Chap05Example10_DFS(i, j, blocks, visited);
                    answer++;
                }
            }
        }

        return answer;
    }

    public void Chap05Example10_DFS(int y, int x, int[][] blocks, int[][] visited) {
        int[][] move = new int[][]{{-1, 0}, {1, 0}, {0, 1}, {0, -1}};
        visited[y][x] = 1;
        int tmpY = 0;
        int tmpX = 0;
        for (int i = 0; i < move.length; ++i) {
            tmpY = y + move[i][0];
            tmpX = x + move[i][1];
            if (tmpY < blocks.length && tmpX < blocks[0].length && tmpY >= 0 && tmpX >= 0 && blocks[tmpY][tmpX] == 0 && visited[tmpY][tmpX] == 0) {
                Chap05Example10_DFS(tmpY, tmpX, blocks, visited);
            }
        }
    }

    public int Chap05Example11(int m, int n, int[][] map) {
        int[][] visited = new int[m][n];
        int[][] move = new int[][]{{-1,0}, {1,0}, {0,1}, {0,-1}};
        Queue<int[]> queue = new LinkedList<>();
        queue.add(new int[]{0, 0, 1});

        while (!queue.isEmpty()) {
            int[] tile = queue.poll();
            visited[tile[0]][tile[1]] = 1;

            if (tile[0] == m-1 && tile[1] == n-1) {
                return tile[2];
            }
            for(int i = 0; i<move.length;++i) {
                int tmpY = tile[0]+move[i][0];
                int tmpX = tile[1]+move[i][1];
                if(tmpY >= 0 && tmpX >= 0 && tmpY < m && tmpX < n && visited[tmpY][tmpX] == 0 && map[tmpY][tmpX] == 1) {
                    queue.add(new int[]{tmpY, tmpX, tile[2]+1});
                }
            }
        }
        return 0;
    }
}

---

이제는 지겹도록 본 DFS, BFS

타일에서의 (-1, 0), (1, 0), (0, 1),(0, -1) 처럼 이동과 관련된 것은 배열에 미리 담아두고 푸는게 실수를 줄일 수 있다고 해서 의식해서 써보고 있다.

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

        int x;
        int y;
        for(int i = 1; i<=yellow;++i) {
            if(yellow % i == 0) {
                x = i;
                y = yellow / i;
                if(x == y) {
                    return new int[]{x+2,x+2};
                }
                if((x+y)*2+4 == brown) {
                    if(x < y) {
                        int tmp = y;
                        y = x;
                        x = tmp;
                    }
                    return new int[]{x+2,y+2};
                }
            }
        }
        return answer;
    }
}

yellow와 brown의 개수에 대한 공식을 알면 문제를 어렵지 않게 풀 수 있다.

import java.util.*;

class Solution {
    public int[] solution(int[] answers) {
        int[] answer = {};
        int[] first = {1,2,3,4,5};
        int[] second = {1,3,4,5};
        int[] third = {3,1,2,4,5};
        int[] uAnswer = new int[3];
        //1,2,3,4,5,1,2,3,4,5,1,2,3,4,5
        //1는 (answer % 5 == 0) ? 5 : answer % 5;
        //(answer % 2 == 1) ? 2 : (answer / 2) % 4;
        //1,3,4,5,1,3,4,5
        //2,1,2,3,2,4,2,5,2,1,2,3,2,4,2,5
        //33,11,22,44,55
        //
        for(int i = 0; i<answers.length;++i) {
            
            int f = first[i%5];
            int s = (i%2 == 0) ? 2 : second[(i/2)%4];
            int t = third[(i/2)%5];
            if(f == answers[i])
                uAnswer[0]++;
            if(s == answers[i])
                uAnswer[1]++;
            if(t == answers[i])
                uAnswer[2]++;
        }
        int max = -1;
        List<Integer> list = new ArrayList<>();
        for(int i = 0; i<uAnswer.length;++i) {
            if(uAnswer[i] > max)
                max = uAnswer[i];
        }
        for(int i = 0; i<uAnswer.length;++i) {
            if(uAnswer[i] == max)
                list.add(i+1);
        }
        answer = new int[list.size()];
        for(int i = 0; i<list.size();++i)
            answer[i] = list.get(i);
        return answer;
    }
}

찍는 방법의 규칙성만 찾아내면 되는 문제

import java.util.*;
public class main {
    public static void main(String[] args) {

        Solution s = new Solution();

        System.out.println(Arrays.toString(s.Chap4Example01(5, new String[]{"R","R","R","U","D","D"})));
        //Guide 생략
        System.out.println(s.Chap4Example02Guide(5));
        //규칙성 찾지 말고 그냥 완전탐색을 쓰라고 한다. 10만건 이하의 건이기 때문에 시간이 더 늘어날 일이 없으므로..
        //애초에 hour + minute + second 에서 "24"의 contains을 확인할 때, 024011과 같은 경우처럼 hour과 minute가 붙어있어야 확인이 되는 경우도 있으므로...
        System.out.println(s.Chap4Example03("a1"));
        System.out.println(s.Chap4Example03Guide("a1"));
        //조건을 확인하고 count를 하는 과정은 조건문이 너무 많이 사용되니 일단 값을 계산하고 한번에 조건을 확인한다.
        System.out.println(s.Chap4Example04(4,4,new int[]{1,1,0},new int[][]{{1,1,1,1},{1,0,0,1},{1,1,0,1},{1,1,1,1}}));
        //Guide 생략

    }
}
class Solution {
    public int[] Chap4Example01(int n, String[] moves){
        int[] pos = new int[2];
        //y, x로 가정 좌상이 0,0

        for(String s : moves) {
            switch (s) {
                case "R":
                    if(pos[1]+1 < n)
                        pos[1]++;
                    break;
                case "L":
                    if(pos[1]-1>-1)
                        pos[1]--;
                    break;
                case "U":
                    if(pos[0]-1> -1)
                        pos[0]--;
                    break;
                case "D":
                    if(pos[0]+1 < n)
                        pos[0]++;
                    break;
            }
        }
        pos[0]++;
        pos[1]++;
        return pos;
    }
    public int Chap4Example02(int n) {
        int answer = 0;
        //n이 포함되는 모든 시간 체크
        //nn:nn:nn
        //n~~~~~~~규칙성은 없을까..?
        //


        return answer;
    }
    public int Chap4Example02Guide(int n) {
        //000000~235959까지 경우의 수가 10만개가 되지 않으므로 완전탐색 하는게 낫다고 한다..
        int answer = 0;
        for(int i = 0; i<n+1;++i) {
            for(int j = 0; j<60;++j) {
                for(int k = 0; k<60;++k) {
                    String s = Integer.toString(i)+Integer.toString(j)+Integer.toString(k);
                    if(s.contains("3")) {
                        answer++;
                    }
                }
            }
        }
        return answer;
    }
    public int Chap4Example03(String pos) {
        int answer = 0;

        String[] xyPos = pos.split("");
        //'a' = 97 then 'a'-96 = 1
        int x = (int)xyPos[0].charAt(0)-(int)'a'+1;
        int y = Integer.parseInt(xyPos[1]);
        if(x > 2) {
            if(y > 1) {
                answer++;
            }
            if(y < 8) {
                answer++;
            }
        }
        if(x < 6) {
            if(y > 1) {
                answer++;
            }
            if(y < 8) {
                answer++;
            }
        }
        if(y > 2) {
            if(x > 1) {
                answer++;
            }
            if(x < 8) {
                answer++;
            }
        }
        if(y < 6) {
            if(x > 1) {
                answer++;
            }
            if(x < 8) {
                answer++;
            }
        }
        return answer;
    }
    public int Chap4Example03Guide(String pos) {
        int answer = 0;

        String[] xyPos = pos.split("");
        //'a' = 97 then 'a'-96 = 1
        int x = (int)xyPos[0].charAt(0)-(int)'a'+1;
        int y = Integer.parseInt(xyPos[1]);
        int[][] steps = new int[][]{{-2, -1}, {-1, -2}, {1, -2}, {2, -1}, {2, 1}, {1, 2}, {-1, 2}, {-2, 1}};

        for(int[] step : steps) {
            int nX = x+step[0];
            int nY = y+step[1];
            if(nX >= 1 && nX <= 8 && nY >= 1 && nY <= 8) {
                answer++;
            }
        }
        return answer;
    }
    public int Chap4Example04(int m, int n, int[] character, int[][] map) {
        int answer = 0;
        int[][] visited = new int[n][m];//m: x, n: y

        visited[character[0]][character[1]] = 1;//0: x, 1: y
        answer++;
        int notMoveCount = 0;
        int[][] move = new int[][]{{-1,0}, {0,-1}, {1,0}, {0,1}};
        while(true) {
            character[2] = (character[2]-1 < 0) ? 3 : character[2]-1;
            int tmpX = character[1]+move[character[2]][1];
            int tmpY = character[0]+move[character[2]][0];
            if(tmpX >= 0 && tmpY >= 0 && tmpX < m && tmpY < n && visited[tmpY][tmpX] == 0 && map[tmpY][tmpX] == 0) {
                character[1] = tmpX;
                character[0] = tmpY;
                answer++;
                visited[tmpY][tmpX] = 1;

            }
            else {
                notMoveCount++;
                if(notMoveCount == 4) {
                    notMoveCount = 0;
                    int nextMove = (character[2] + 2) % 4;
                    tmpX = character[1]+move[nextMove][1];
                    tmpY = character[0]+move[nextMove][0];

                    if(tmpX < 0 || tmpY < 0 || tmpX >= m && tmpY >= n || map[tmpY][tmpX] == 1)
                        break;

                    character[0] = tmpY;
                    character[1] = tmpX;
                }
            }
        }
        return answer;
    }
}

완전탐색 문제들이라고 봐야 하나

import java.util.*;

class Bridge implements Comparable<Bridge>{
    int cost;
    int from;
    int to;
    public Bridge(int cost, int from, int to) {
        this.cost = cost;
        if(from < to) {
            this.from = from;
            this.to = to;
        }
        else {
            this.from = to;
            this.to = from;  
        }
    }
    @Override
    public int compareTo(Bridge b) {
        if(b.cost < cost)
            return 1;
        else if(cost < b.cost)
            return -1;
        else
            return 0;
    }
}
class Solution {
    int[] parent;
    public int solution(int n, int[][] costs) {
        int answer = 0;
        parent = new int[n];
        
        for(int i = 0; i < n;++i)
            parent[i] = i;
        
        List<Bridge> list = new ArrayList<>();
        
        for(int[] cost : costs)
            list.add(new Bridge(cost[2], cost[0], cost[1]));
        
        Collections.sort(list);
        
        for(Bridge bridge : list) {
            if(!isSameParent(bridge.from, bridge.to)) {
                answer += bridge.cost;
                setParent(bridge.from, bridge.to);
            }
        }
        return answer;
    }
    public boolean isSameParent(int i, int j) {
        if(getParent(i) != getParent(j))
            return false;
        return true;
    }
    public int getParent(int i) {
        if(parent[i] != i) {
            return getParent(parent[i]);
        }
        return parent[i];
    }
    public void setParent(int i, int j) {
        if(getParent(i) != i) {
            parent[getParent(j)] = getParent(i);
        } 
        else if(getParent(j) != j) {
            parent[getParent(i)]  = getParent(j);
        }
        else {
            parent[j] = parent[i];
        }
    }
}

크루스칼 알고리즘을 써야 하는 문제이다.

처음 봤을 때는 억... 했지만 크루스칼 알고리즘을 다시 복기하고 나니까 크게 어려운 문제는 아니었다.

크루스칼 알고리즘을 써야하는 문제는 이렇게 생겼구나 하고 기억만 해두면 문제는 없을 것 같다.

까먹지 말아야 할 건 setParent에서 parent[j] = ~~~~가 아니라 parent[getParent(j)] = ~~~~~가 되야 한다는 점.

서로 다른 그룹을 연결하기 위해서는 최상위 부모가 되는 노드끼리 연결을 해주어야 하기 때문.

스터디 공부 하고 관련 문제를 풀어봤는데 재미는 있는데... 이거에 시간 쓸 때가 아닌데 어휴