개발 공부기록

👇 내가 작성한 코드

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

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

        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        int[] account = new int[N];

        for(int i = 0; i < N; i++) {
            account[i] = Integer.parseInt(br.readLine());
        }

        int left = Arrays.stream(account).max().getAsInt(); // 모든 지출 중 최대값
        int right = Arrays.stream(account).sum(); // 모든 지출의 합
        int K = 0;

        while(left <= right) {
            int mid = (left + right) / 2; // 날짜 별 지출을 mid 금액으로 커버할 수 있는지 확인
            int sum = 0;
            int count = 1; // 인출 횟수

            for(int money : account) {
                // 현재까지의 sum에 다음 일자의 금액을 더했을 때, mid보다 크다면 재인출
                // 현재 인출한 금액으로는 다음 일자의 금액을 충당할 수 없다는 의미
                if(sum + money > mid) {
                    count++; // 재인출
                    sum = 0;
                }
                sum += money; // 현재일자 금액 더하기
            }

            // 인출 횟수가 M이하인지 검색하고 가능한 최소 금액 찾기
            // 인출 금액을 줄여볼 수 있는 여지가 있음
            if(count <= M) {
                right = mid - 1;
                K = mid;
            } else left = mid + 1;
            // count가 M보다 크다면, 인출 횟수가 너무 많다는 얘기. == mid 금액 증가
        }
        System.out.println(K);
    }
}

👇 내가 작성한 코드

import java.util.*;

class Solution {
    public String solution(int[] numbers) {
        String[] arr = new String[numbers.length];
        
        for(int i = 0; i < numbers.length; i++) {
            arr[i] = String.valueOf(numbers[i]);
        }
        
        // 두 수를 합친 값을 기준으로 내림차순
        // o1 : 30, o2 : 5 일 경우, 305와 530 중 더 큰 값 비교
        Arrays.sort(arr, (o1, o2) -> (o2 + o1).compareTo(o1 + o2));
        
        // 정렬된 배열의 맨 처음이 0이라면 0으로만 되어있음. 0 반환
        return arr[0].equals("0") ? "0" : String.join("", arr);
    }
}

👇 내가 제출한 코드

import java.util.*;

class Solution {
    public long solution(int n, int[] times) {
        long answer = 0;
        Arrays.sort(times); // 이분 탐색을 위해 정렬

        long left = 0;
        long right = (long) n * times[times.length - 1]; // 최악의 경우 고려
        
        while(left <= right) {
            long mid = (left + right) / 2;
            
            long sum = 0; // 심사한 인원
            for(int time : times) {
                sum += mid / time;
            }
            
            // n명 심사해야하는데 못했다면, 시간이 더 필요하기 때문에 left 옮겨줌
            if(sum < n) left = mid + 1;
            // n명 이상 했다면 시간을 줄여서 최적의 시간을 확인해보기
            else {
                right = mid - 1;
                answer = mid;
            }
        }
        return answer;
    }
}

👇 내가 제출한 코드

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

public class Main {
    static int N, M;
    static int[] dr = {-1, 0, 1, 0};
    static int[] dc = {0, -1, 0, 1};
    static int[][] ocean;
    static boolean[][] visited;
    static List<int[]> icebergs = new ArrayList<>();

    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());
        ocean = 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++) {
                ocean[i][j] = Integer.parseInt(st.nextToken());
                if(ocean[i][j] > 0) {
                    icebergs.add(new int[] {i, j}); // 빙산 좌표 저장
                }
            }
        }

        int time = 0;
        while(!icebergs.isEmpty()){
            time++; // 빙산 분리되는 시간
            melting(); // 빙산 녹이기

            if(searchSplit()) {
                System.out.println(time);
                return;
            }
        }
        System.out.println(0);
    }
    public static void melting() {
        int[][] tempMap = new int[N][M];
        List<int[]> nextIcebergs = new ArrayList<>();

        // 빙산 좌표 돌면서 얼마나 녹일지 확인하기
        for(int[] iceberg : icebergs) {
            int x = iceberg[0];
            int y = iceberg[1];

            int melt = 0;
            for(int d = 0; d < 4; d++) {
                int nx = dr[d] + x;
                int ny = dc[d] + y;

                if(nx >= 0 && ny >= 0 && nx < N && ny < M && ocean[nx][ny] == 0) melt++;
            }
            // 녹인 후 빙산의 높이 임시배열에 저장해두기
            tempMap[x][y] = Math.max(0, ocean[x][y] - melt);
            // 다 녹지 않았다면 좌표 저장
            if(tempMap[x][y] > 0) nextIcebergs.add(new int[] {x, y});
        }

        icebergs = nextIcebergs; // 빙산 좌표 갱신
        // 임시배열 반영하기
        for(int i = 0; i < N; i++) {
            System.arraycopy(tempMap[i], 0, ocean[i], 0, M);
        }
    }

    public static boolean searchSplit() {
        int count = 0;
        for(boolean[] row : visited) Arrays.fill(row, false); // 방문 판별 배열 초기화

        // 빙산 좌표만 dfs 돌면서 분리된 덩어리 개수 확인하기
        for(int[] iceberg : icebergs) {
            int x = iceberg[0];
            int y = iceberg[1];

            if(!visited[x][y]) {
                dfs(x, y);
                count++; // 분리된 덩어리 개수
                if(count > 1) return true;
            }
        }
        return false;
    }

    public static void dfs(int x, int y) {
        visited[x][y] = true;
        for(int d = 0; d < 4; d++) {
            int nx = dr[d] + x;
            int ny = dc[d] + y;

            if(nx >= 0 && ny >= 0 && nx < N && ny < M && !visited[nx][ny] && ocean[nx][ny] > 0) {
                dfs(nx, ny);
            }
        }
    }
}

👇 내가 작성한 코드

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int tc = Integer.parseInt(br.readLine());
        StringBuilder sb = new StringBuilder();

        while(tc-- > 0) {
            String answer = "YES";
            int N = Integer.parseInt(br.readLine());
            String[] phone_book = new String[N];
            for(int i = 0; i < N; i++) {
                phone_book[i] = br.readLine();
            }

            Arrays.sort(phone_book); // 접두어 판별을 더 빠르게 하기 위해 정렬

            for(int i = 0; i < phone_book.length - 1; i++) {
                if(phone_book[i + 1].startsWith(phone_book[i])) {
                    answer = "NO"; // 접두어라면 NO 출력 후 for문 빠져나가기
                    break;
                }
            }
            sb.append(answer).append("\n");
        }
        System.out.println(sb);
    }
}

👇 내가 작성한 코드

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

public class Main {
    static int N, M;
    static int min = Integer.MAX_VALUE;
    static int[] selected;
    static List<int[]> house = new ArrayList<>();
    static List<int[]> chicken = new ArrayList<>();
    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());
        selected = new int[M];

        for(int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            for(int j = 0; j < N; j++) {
                int value = Integer.parseInt(st.nextToken());
                if(value == 1) house.add(new int[] {i, j}); // 집 좌표 저장
                else if(value == 2) chicken.add(new int[] {i, j}); // 치킨가게 좌표 저장
            }
        }
        dfs(0, 0);
        System.out.println(min);
    }

    public static void dfs(int L, int start) {
        if(L == M) { // 유지하는 치킨집 M개 선택 완료되면 dist 메소드 실행
            dist();
            return;
        }

        // 유지할 치킨집 M개 조합하여 selected배열에 인덱스 저장
        for(int i = start; i < chicken.size(); i++) {
            selected[L] = i;
            dfs(L + 1, i + 1);
        }
    }

    public static void dist() {
        int sum = 0;
        for(int[] h : house) {
            int tempMin = Integer.MAX_VALUE;
            for(int idx : selected) { // 유지할 치킨집 M개의 인덱스가 담겨져있는 배열
                int[] hCur = chicken.get(idx);
                int distance = Math.abs(h[0] - hCur[0]) + Math.abs(h[1] - hCur[1]); // 거리 차이 구하기
                tempMin = Math.min(tempMin, distance); // 집에서 가장 가까운 치킨집 선택
            }
            sum += tempMin; // 선택한 치킨거리 누적합
        }
        min = Math.min(sum, min); // 치킨거리 최솟값 구하기
    }
}

👇내가 작성한 코드

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 max = Integer.MIN_VALUE;
    static int[][] map;
    static int[][] copyMap;
    static int[] dr = {-1, 0, 1, 0};
    static int[] dc = {0, 1, 0, -1};
    static Queue<int[]> q = new LinkedList<>();

    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(max);
    }

    // 벽 세우기
    public static void dfs(int wall) {
        // 벽이 3개 세워지면, 해당 map에서 bfs돌리며 바이러스 뿌리기
        if(wall == 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(wall + 1);
                    map[i][j] = 0;
                }
            }
        }
    }

    // 바이러스 뿌리는 메소드
    public static void bfs() {
        copyMap = new int[N][M];

        for(int i = 0; i < N; i++) {
            copyMap[i] = map[i].clone();
            for(int j = 0; j < M; j++) {
                if(map[i][j] == 2) q.add(new int[] {i, j});
            }
        }

        while(!q.isEmpty()) {
            int[] cur = q.poll();
            int x = cur[0];
            int y = cur[1];

            for(int d = 0; d < 4; d++) {
                int nr = dr[d] + x;
                int nc = dc[d] + y;

                if(nr >= 0 && nc >= 0 && nr < N && nc < M && copyMap[nr][nc] == 0) {
                    copyMap[nr][nc] = 2;
                    q.add(new int[] {nr, nc});
                }
            }
        }
        safeZone(copyMap);
    }

    // 안전한 공간(0)의 칸 세고 최댓값 갱신
    public static void safeZone(int[][] copyMap) {
        int cnt = 0;

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

👇 내가 작성한 코드

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

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

        int N = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());
        int[] doll = new int[N];
        st = new StringTokenizer(br.readLine());

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

        int left = 0, right = 0, count = 0, min = Integer.MAX_VALUE;

        while(right < N) {
            // 현재 위치에 라이언 인형이 있다면 라이언 개수 증가
            if(doll[right] == 1) count++;

            // 라이언 인형이 K개 이상이라면, 총 인형 개수의 최솟값 갱신
            // 왼쪽 포인터의 위치에 라이언 인형이 있다면 라이언 개수 감소
            // 왼쪽 포인터 오른쪽으로 이동
            while(count >= K) {
                min = Math.min(min, right - left + 1);
                if(doll[left] == 1) count--;
                left++;
            }
            // 오른쪽 포인터 증가
            right++;
        }

        System.out.println(min == Integer.MAX_VALUE ? -1 : min);
    }
}