240623

240623 회고 💬

7월 7일 일요일에 정보처리기사 필기 시험이 있다. 연초에 꼭 해내리라 다짐한 목표 중 하나다. 이전에 노베이스로 잠깐 봤을 때는 딱 60점 나와서 부담 없겠거니 했지만 막상 닥치니까 긴장이 된다. 오랜만에 시험 준비를 해야하는 6월 4주차를 되돌아본다.

Keep 👍

• 알고리즘 문제풀이를 7일 연속으로 해냈다. 240623 기준으로 253일 연속 문제풀이 달성이다. 또한 출신 학교 기준으로 전교 60등(풀이문제수기준)을 달성했다~🎉
  - 테트로미노 백트래킹 응용 문제다. 처음에는 블록 클래스를 만들어서 회전을 시키는 풀이를 생각했었다. 그런데 사실 블록 길이 4만 맞춰놓고 DFS로 탐색하면 풀리는 문제였다.
  - 불! BFS 응용 문제다. 불이 번지는 시간을 계산할 BFS 함수 하나, 사람이 도망갈 시간을 계산할 BFS 함수 하나. 총 2번 연산을 하면 된다.
  - 효율적인 해킹 간단한 BFS 문제다. 양방향 노드로 생각하지 말고 잎에서 뿌리로 간선을 그어서 풀이하면 연산을 줄일 수 있다. 처음에는 오기로 DFS 풀이를 시도했는데 10번 넘게 시도 후에 BFS로 해결했다. 오기부리지말자... 🤦‍♂️
  - 컴백홈 간단한 DFS 문제다. 위 효율적인 해킹 문제에서 DFS 풀이를 실패한 바람에 DFS 문제를 하나 골라 풀었다. 백트래킹을 사용해서 쉽게 해결할 수 있다.
  - 폴짝폴짝 1차원 BFS 문제다. 배수로 이동한다는 조건을 당연히 증가한다고 이해했다. 그런데 배수로 감소하는 경우의 수까지 고려해야 하더라... 💀
• 이번 주에는 공부한 내용이 많다. (백수니까~)
  1. 자바 기본 문법 복습 완료
  - 컬렉션 프레임워크 내용 복습 -> 리스트, 셋, 맵
  2. MySQL 기본 쿼리문 복습
  - select, insert, update, delete, drop 내용 복습
  3. 자바 스프링 프레임워크 기본 내용 복습
  - @Autowired, bean scope, bean life cycle

Try 🧚

• DB 공부 마무리하기
• JPA 공부 마무리하기
• 읽던 책 마무리하기
• 타입스크립트 문법 마무리하기
• 정보처리기사 필기 준비하기!

Extras 😀

효율적인 해킹

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

public class Main {

    public static void main(String[] args) {
        try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in))) {

            Solution s = new Solution();
            System.out.println(s.solution(getInput(br)));

        } catch (IOException e) {
            throw new RuntimeException(e);
        }
    }

    private static List<List<Integer>> getInput(BufferedReader br) throws IOException {
        int[] tokens = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        List<List<Integer>> network = new ArrayList<>();
        for (int i = 0; i <= tokens[0]; i++) {
            network.add(new ArrayList<>());
        }

        for (int i = 0; i < tokens[1]; i++) {
            int[] connected = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
            network.get(connected[0]).add(connected[1]);
        }
        return network;
    }
}

class Solution {

    public String solution(List<List<Integer>> network) {
        Calculator c = new Calculator(network);
        return c.getResult();
    }

    private static class Calculator {

        List<List<Integer>> network;
        int[] mostContagiousNetwork;
        boolean[] isInfected;

        public Calculator(List<List<Integer>> network) {
            this.network = network;
            this.mostContagiousNetwork = new int[network.size()];
        }

        public String getResult() {
            explore();
            return getMostContagiousNetwork();
        }

        private void explore() {
            for (int i = 1; i < network.size(); i++) {
                isInfected = new boolean[network.size()];
                infect(i);
            }
        }

        private void infect(int start) {
            Queue<Integer> q = new ArrayDeque<>();
            q.offer(start);
            isInfected[start] = true;

            while (!q.isEmpty()) {

                int currentComputer = q.poll();

                for (Integer nextComputer : network.get(currentComputer)) {
                    if(isInfected[nextComputer]) continue;

                    isInfected[nextComputer] = true;
                    mostContagiousNetwork[nextComputer]++;
                    q.offer(nextComputer);
                }
            }
        }

        private String getMostContagiousNetwork() {
            StringBuilder result = new StringBuilder();
            int standard = getMax(mostContagiousNetwork);
            for (int i = 1; i < mostContagiousNetwork.length; i++) {
                if (mostContagiousNetwork[i] == standard) {
                    result.append(i).append(" ");
                }
            }
            return result.toString();
        }

        private int getMax(int[] list) {
            int result = 0;
            for (Integer i : list) {
                result = Math.max(result, i);
            }
            return result;
        }

    }
}