240728 회고 💬
잠시라도 밖에 있으면 육수가 줄줄 흐르는 날씨에 지쳐 집 밖으로 나갈 생각조차 안 하는 1인. 에어컨 시원하게 맞춰놓고 알고리즘 문제를 풀고 있노라면 이보다 행복할 수가 있을까? 점점 이성을 놓게 되는 7월의 마지막 주를 되돌아본다.
Keep 👍
- 알고리즘 문제 풀이를 7일 연속 해냈다. 288일째 연속으로 풀이하고 있다. 🥳
- 치킨 배달 백트래킹 문제다. 거리 구하는 식을 알려주기 때문에 BFS 로직을 구현하지 않아도 된다. 지도상에 있는 치킨 가게 n 개 중에서 r개를 정해서 해당 가게들의 총 거리를 계산하면 되는 문제다.
- 가운데를 말해요 최소힙과 최대힙을 같이 사용하는 문제다. 해당 아이디어만 떠올리면 쉽게 풀 수 있는 문제다.
- 양치기 꿍 오랜만에 BFS 문제 풀이를 했다. 이전에 한참을 붙잡고 있던 유형이여서 오랜만에 풀이해도 손이 저절로 움직였다. 사실 DFS로 풀어도 된다. 뭐든 상관없으니 기본기만 있다면 쉽게 풀 수 있는 문제다. - 함께 자라기를 계속 읽고 있다.
- 이번 주에는 알고리즘 문제 풀이에 재미가 들려서 스프링 공부는 못했다.
Problem 🤢
Try 🧚
- 함께 자라기 마무리하기
- 최소신장트리 공부하기
- 유니온파인드
- 프림 - 알고리즘 문제 풀이
Extras 😀
치킨 배달
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) {
try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in))) {
Input ip = getInput(br);
Solution s = new Solution();
System.out.println(s.solution(ip.board, ip.target));
} catch (IOException e) {
throw new RuntimeException(e);
}
}
private static Input getInput(BufferedReader br) throws IOException {
int[] tokens = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
int len = tokens[0];
int target = tokens[1];
int[][] board = new int[len][len];
for (int i = 0; i < board.length; i++) {
board[i] = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
}
return new Input(target, board);
}
private static class Input {
int target;
int[][] board;
public Input(int target, int[][] board) {
this.target = target;
this.board = board;
}
}
}
class Solution {
public int solution(int[][] board, int target) {
Calculator c = new Calculator(board, target);
return c.getResult();
}
}
class Calculator {
int[][] board;
int target;
int[] selectedChickens;
int result = Integer.MAX_VALUE;
List<Point> houses = new ArrayList<>();
List<Point> chickens = new ArrayList<>();
public Calculator(int[][] board, int target) {
this.board = board;
this.target = target;
this.selectedChickens = new int[target];
}
public int getResult() {
init();
select(0, 0);
return result;
}
private void init() {
for (int i = 0; i < board.length; i++) {
for (int j = 0; j < board[i].length; j++) {
if(board[i][j] == 1) houses.add(new Point(i, j));
else if (board[i][j] == 2) chickens.add(new Point(i, j));
}
}
}
public void select(int numOfSelected, int shopNum) {
if (numOfSelected == target) {
calc();
} else {
for (int i = shopNum; i < chickens.size(); i++) {
selectedChickens[numOfSelected] = i;
select(numOfSelected + 1, i + 1);
}
}
}
private void calc() {
int sum = 0;
for (Point house : houses) {
int chickenDistance = Integer.MAX_VALUE;
for (int i : selectedChickens) {
Point selectedChicken = chickens.get(i);
int distance = Math.abs(house.x - selectedChicken.x) + Math.abs(house.y - selectedChicken.y);
chickenDistance = Math.min(chickenDistance, distance);
}
sum += chickenDistance;
}
result = Math.min(result, sum);
}
private static class Point {
int x, y;
public Point(int x, int y) {
this.x = x;
this.y = y;
}
}
}가운데를 말해요
import java.io.*;
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 int[] getInput(BufferedReader br) throws IOException {
int len = Integer.parseInt(br.readLine());
int[] result = new int[len];
for (int i = 0; i < result.length; i++) {
result[i] = Integer.parseInt(br.readLine());
}
return result;
}
}
class Solution {
MidHeap mh = new MidHeap();
public String solution(int[] nums) {
StringBuilder result = new StringBuilder();
for(int num : nums){
mh.add(num);
result.append(mh.getMidNum()).append("\n");
}
return result.toString();
}
}
class MidHeap {
PriorityQueue<Integer> maxQ = new PriorityQueue<>(Collections.reverseOrder());
PriorityQueue<Integer> minQ = new PriorityQueue<>();
public void add(int num) {
if (maxQ.size() >= minQ.size()) {
maxQ.add(num);
minQ.add(maxQ.poll());
} else {
minQ.add(num);
maxQ.add(minQ.poll());
}
}
public int getMidNum() {
if(maxQ.isEmpty() || maxQ.size() < minQ.size()) return minQ.peek();
return maxQ.peek();
}
}양치기 꿍
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Queue;
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 String[][] getInput(BufferedReader br) throws IOException {
String[] dimensions = br.readLine().split(" ");
int x = Integer.parseInt(dimensions[0]);
int y = Integer.parseInt(dimensions[1]);
String[][] field = new String[x][y];
for (int i = 0; i < field.length; i++) {
field[i] = br.readLine().split("");
}
return field;
}
}
class Solution {
public String solution(String[][] field) {
SeekAndHide sh = new SeekAndHide(field);
return sh.getResult();
}
}
class SeekAndHide {
String[][] field;
boolean[][] isChecked;
int[][] directions = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
int sheepSurvived = 0;
int wolvesSurvived = 0;
public SeekAndHide(String[][] field) {
this.field = field;
this.isChecked = new boolean[field.length][field[0].length];
}
public String getResult() {
explore();
return sheepSurvived + " " + wolvesSurvived;
}
private void explore() {
for (int i = 0; i < field.length; i++) {
for (int j = 0; j < field[i].length; j++) {
if (!field[i][j].equals("#") && !isChecked[i][j]) {
isChecked[i][j] = true;
seekAndHide(i, j);
}
}
}
}
private void seekAndHide(int x, int y) {
int wolves = 0;
int sheep = 0;
Queue<int[]> q = new ArrayDeque<>();
q.offer(new int[]{x, y});
while (!q.isEmpty()) {
int[] cur = q.poll();
int curX = cur[0];
int curY = cur[1];
if(field[curX][curY].equals("v")) wolves++;
else if(field[curX][curY].equals("k")) sheep++;
for (int[] direction : directions) {
int nx = curX + direction[0];
int ny = curY + direction[1];
if (isWithinField(nx, ny) && !isChecked[nx][ny] && !field[nx][ny].equals("#")) {
isChecked[nx][ny] = true;
q.offer(new int[]{nx, ny});
}
}
}
if(sheep > wolves) sheepSurvived += sheep;
else wolvesSurvived += wolves;
}
private boolean isWithinField(int x, int y) {
return 0 <= x && x < field.length && 0 <= y && y < field[x].length;
}
}독서 목록
서평 완료 목록
서평 예정 목록 (읽는 중)
- 프로그래머의 길, 멘토에게 묻다
- 함께 자라기 애자일로 가는 길
독서 예정 목록
목록은 우선순위 큐이다. 상단에 있더라도 더 중요한 책이 들어온다면 순위가 뒤로 밀릴 수 있다.
- 객체지향의 사실과 오해
- 오브젝트
- 파이브 라인스 오브 코드
- HTTP 완벽 가이드
- 자바/스프링 개발자를 위한 실용주의 프로그래밍
- 모던 자바 인 액션
- 자바 성능 튜닝 이야기
- 자바 개발자와 시스템 운영자를 위한 트러블 슈팅 이야기 / scouter를 활용한 시스템 장애 진단 및 해결 노하우 자바 트러블슈팅
- 헤드 퍼스트 서블릿
- Hello Coding 그림으로 개념을 이해하는 알고리즘
What doesn't kill you, makes you stronger