woody

- 문제설명 - 해결과정 입력으로 주어진 간선 정보를 이용해 인접 리스트를 만든다. 최초 시작 노드를 파라미터로 dfs를 호출한다. 시작 노드에 연결되어 있는 노드 중 가장 번호가 작은 노드를 찾는다. 해당 노드를 시작으로 다시 dfs를 호출한다. 가장 번호가 작은 노드를 찾으면 finalNode값을 갱신해줬기 때문에, 마지막 dfs를 마치고나면 자연스럽게 최종 도착지 노드를 알 수 있다. 그대로 출력하면 된다. - 솔루션 import java.util.*; import java.io.*; class Main { private static boolean[] visited; private static List[] node; private static int finalNode = 0; private stat..

- 문제설명 - 해결과정 어제 풀었던 발전기 문제에서 심화된 문제이다. 아래와 같은 흐름으로 문제를 풀이했다. BFS를 돌면서 현재 그룹에서 이어진 집의 개수가 몇개인지 확인한다. 최종 이어진 개수가 K개 이상이라면 "단지"라고 판단해 리스트에 해당 번호를 추가한다. 배열을 전부 탐색해 가능한 모든 단지가 리스트에 담겼다면 요소를 하나씩 빼서 해시맵에 같은 유형의 단지가 몇 개씩 있는지 옮긴다. 완성된 해시맵을 순회하며 가장 단지 수가 많은 유형을 찾아 반환한다. - 솔루션 import java.io.*; import java.util.*; class Main { private static int[][] town; private static boolean[][] visited; private static..

- 문제설명 - 해결과정 입력값을 받아 배열을 초기화 시킨 후 모든 배열을 탐색하면서 BFS를 호출한다. BFS가 중간에 끊긴다면 상하좌우로 이어진 모든 집을 탐색한 것이다. 이때 count를 증가시키고, 아직 방문하지 않은 나머지 집에 대해서 BFS를 호출하면 된다. 결론적으로 모든 배열을 돌고나면 몇번의 BFS가 호출되었는지 count값으로 확인할 수 있다. - 솔루션 import java.io.*; import java.util.*; class Main { private static int[][] town; private static boolean[][] visited; private static int[] dx = {-1, 1, 0, 0}; private static int[] dy = {0, 0..

- 문제설명 - 해결과정 문제의 조건에서 두 아이템의 이름이 A, B일때 B가 회복시켜주는 양이 A보다 더 크다고 나와있다. 이를 이용해 문제를 풀어보자. 아이템 사용량이 가장 최소가 되는 상황부터 아이템 사용량이 가장 최대가 되는 상황으로 올라가면서 각 단계별로 피로도를 0으로 만들 수 있는지 판단하면 된다. --> 가장 먼저 피로도를 0으로 만들 수 있는 상황을 만난다면 해당 경우가 아이템을 가장 적게 사용해 피로도를 0으로 만드는 것이다. 아이템 사용량이 가장 최소가 되는 상황이란 누적 피로도를 아이템 B의 회복량으로 나눈 몫만큼 아이템 B를 사용하고 그 나머지는 아이템 A로 피로를 회복하는 상황이다. 이 상황부터 아이템 B의 사용량을 하나 줄이고, 다시 나머지를 아이템 A로 채워 피로도를 0으로 ..

- 문제설명 - 해결과정 문제를 해결하는데 고려해야하는 포인트는 아래와 같다. 한 칸씩 나아갈 때 방문처리를 하며 나아가야한다. 이후 방문처리가 되어있는 칸을 방문할 시 게임종료. 각 칸에 써있는 count, command 정보를 알 수 있어야 한다. 위의 포인트들을 처리하기 위해서 Node라는 static class를 만들었다. 해당 클래스에는 아래와 같은 멤버변수를 담아놨고, 생성자 및 getter, setter를 만들었다. 방문여부를 알 수 있는 boolean visited; 진행방향을 알 수 있는 char command; 진행횟수를 알 수 있는 int count 두 명의 플레이어 각각에 대한 게임판이 필요하다. 따라서 배열 초기화 단계에서 동일한 두 개의 배열을 만들어준다. --> 하나의 게임판만..

- 문제설명 - 해결과정 최초 주어지는 배열만 가지고 문제를 해결할 수 없었다. 최초 배열의 정보를 가지고 누적해서 스코어를 계산해 나가야하기 때문에, 최초 배열과 동일한 사이즈의 점수판이 필요했다. 조금 다른 관점으로, 하나의 배열판만 쓰지만 타입을 직접만든 static class로 지정해줬다. 해당 클래스에는 1. init 이라는 최초 배열 정보 2. score 라는 누적 점수 정보 이렇게 두 가지가 포함되어 있는 클래스이다. 문제풀이 흐름은 아래와 같다. 입력으로 주어지는 정보를 배열로 받는다. 이때는 최초 배열이므로 생성자 주입을 통해 멤버변수 init에 정보를 담는다. 이제 폭탄을 떨구며 점수를 획득하자. 상황별로 몇 점을 주냐만 다르지 점수를 주는 방식은 getScore() 메소드로 기존 점수..

- 문제설명 - 해결과정 단순히 현재 남아있는 통증 수치를 넘지 않는 선에서 가장 효과가 큰 아이템을 사용하면 된다. 추가적인 복잡한 조건이 없었기에 그리디한 솔루션으로 풀리는 문제였다. - 솔루션 import java.io.*; import java.util.*; class Main { public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out)); int N = Integer.parseInt(br...

- 문제설명 - 해결과정 완전탐색 문제이다. 배열의 모든 좌표를 순회하는데 현재 좌표값이 0이라면 상하좌우 + 대각선 총 8방향에서 1이 있는지 검사하고 그 개수를 저장한다. 1의 개수가 K와 같다면, 따로 결과로 내보내줄 result값을 하나 올려준다. 전형적인 완전탐색 문제이다! - 솔루션 import java.io.*; import java.util.*; class Main { private static int[] dx = {1, -1, 0, 0, 1, -1, 1, -1}; private static int[] dy = {0, 0, -1, 1, -1, -1, 1, 1}; public static void main(String[] args) throws Exception { BufferedReader..

- 문제설명 - 해결과정 문자열을 세 덩어리로 분리하고, 각 덩어리를 HashSet에 저장 (중복방지) 세 덩어리를 하나의 결과로 본다. 해당 결과를 배열의 형태(String[])로 리스트에 저장한다. 세 덩어리로 분리가능한 모든 경우를 순회해 1,2번 과정을 끝냈다면, 인덱스를 얻기위해 HashSet에 저장한 덩어리들을 리스트로 옮긴다. 이후 오름차순 정렬 2번 과정을 통해 세 덩어리로 묶인 혹은 세 덩어리로 쪼개질 수 있는 모든 경우의 수를 알아냈다. 하나씩 꺼내면서 최댓값이 될 수 있는지 3번에서 얻은 리스트의 인덱스를 활용하여 판단해보면 된다. 주어진 문자열 S를 세 덩어리로 쪼개는 방식이 중요하다고 생각한다. 1. 세 덩어리로 쪼개진 부분문자열은 모두 이어져야 한다. 2. 각 덩어리는 1개 이상..

- 문제설명 - 해결과정 단순히 오름차순, 내림차순 정렬이 아니라 특정 상황에 따라 정렬 조건이 달라지기 때문에 Node라는 static class를 만들고 클래스 내부에서 compareTo() 메소드를 오버라이드해 정렬 기준을 재정의했다. 멤버변수로는 십진수 값과 이진수로 변환했을 때 1의 개수를 갖는다. 이후 풀이는 Integer.toBinaryString()으로 바이너리 코드를 만들고 1의 개수를 세준 뒤, 리스트에 Node를 생성해 담아주면 된다. 이후 Collections.sort()를 통해 정렬하면 Node 클래스에서 오버라이드한 정렬 기준에 따라 리스트가 정렬된다. 이제 원하는 K번째 값을 꺼내오면 된다. - 솔루션 import java.io.*; import java.util.*; clas..