Hello backEnd

문제 설명1. 몇개의 노드가 주어질지 입력2. 순서대로 노드가 주어진다.3. 어떤 노드를 지울지 알려준다.4. 그 노드랑 이 노드의 모든 자식노드를 지원 후 남은 자식노드 갯수 구하기풀이 과정1. 처음에는 그냥 어떤 노드의 자식들을 모두 보관하게 하고 그 노드를 기준으로 자식을 확인해가면서 삭제해줬다.2. 그리고 ans는 처음에 모든 자식없는 노드들을 확인해서 만들어줬다.3. 리프노드 도달시 하나씩 뺴줘서 처리했다.4. 이랬더니 중간에 틀렸는데, 이유를 생각해보니 어떤 노드의 부모가 그 노드만을 자식으로 가진다면 문제가 될 것 같았다.(O-O-O 이렇게 돼있으면 안됨)5. 여러 방법이 있었겠지만... 나는 그냥 그 노드의 부모를 갖는 Map을 하나 더 만들어서 부모 찾고 자식이 하나뿐이면 더해주는 식으..

한번 틀려서 다시 풀었었다.문제 설명1. S 랑 T가 주어진다.2. S 뒤에 'A' 를 붙이거나, S 뒤에 'B'를 붙이고 뒤집을 수 있다.3. 2번의 연산을 통해서 S랑 T가 같아지면 1, 그렇게 못만들면 0을 출력하면 된다.잘못된 풀이 과정1. BF + DFS문제이다.2. S에서 위의 연산을 하나씩 수행해간다.    - A를 붙여줌    - B를 붙이고 뒤집음3. 그리고 길이가 T랑 같아졌을 때 비교해서 처리한다.    - (틀린 이유) 시간초과가 발생했는데 모든 경우에서 시간복잡도가 2^N이 되기 때문이다.6. S로부터 시작해서 T가 될 때까지 2번씩 N번 수행된 것.코드import java.util.*;public class Main{ private static String T; pri..

문제 설명1. 지름길 개수 N이랑 전체 길이 D가 주어진다.2. N개의 시작, 도착, 지름길 길이가 주어진다.3. 지름길을 통해서 가는 최소 거리를 구하면 된다.풀이 과정1. 다익스트라도 있기는 한데, 나는 DP로 풀었다.2. 전체 위치를 보면서 하나씩 현재 위치까지의 변위 / 이전에서 한칸 더 갔을때 중에 더 작은값이 지금 거리가 된다.3. 처음부터 가면서 혹시 지금 위치가 지름길을 통하는 길이라면 그 도착점을 변경해가면서 찾으면 된다.코드import java.util.*;public class Main{ public static void main(String[] args) { Scanner sc = new Scanner(System.in); int N = sc.nextI..

문제 설명1. N X N 게임판이 있다.2. 사람들이 주어지고 각 능력치의 합이 있다.3. 팀을 나눠서 전체 팀원들의 능력치 합을 구한다.4. 모든 사람들이 포함되어야 한다. 사람들의 숫자가 같지는 않아도 된다.5. 참고로 같은 팀에 있는 사람들의 모든 능력치 합을 구해야 한다.(문제 설명이 진짜 역대급으로 불친절하다. 일부러 헷갈리게 한게 아닌가 의심될 정도)풀이 과정1. BF + DFS + 백트래킹2. 비트마스킹을 이용할 수 있다고는 하는데, 2개 케이스에 대해 각각 계산을 해도 터지지는 않을 것 같아 비트마스킹을 쓰지는 않았다. 좀 오래걸리지만 그래도 통과함 -> O(n^2⋅2^2)3. 간단히 말하자면 team1, team2 에 모든 사람을 각각 넣어가면서 확인하고, 그래서 모든 사람에 대한 팀배정..

문제 설명1. N X N 복도가 있다.2. T 선생 S 학생 X 빈공간3. 선생은 상하좌우를 볼 수 있고 장애물이 있으면 그 뒤는 못본다.4. 장애물을 정확히 3개 설치해서 모든 학생이 안보이면 된다.풀이 과정1. BF + 백트래킹2. 모든 위치에 장애물을 둬 가면서 학생이 확인되는지를 보면 된다.3. 미리 선생의 위치를 알아두고, 그곳에서 볼 때 장애물인지 파악하기4. 장애물의 배치는 모든 X에 두고 보면 된다.코드import java.util.*;public class Main{ private static char map[][]; private static boolean checker[][]; private static int N; private static boolean ans..

문제 설명1. 테스트용 계란을 왼쪽부터 집는다.2. 다른 계란하고 부딪혀본다. (내구도는 무게에 의해 깎이고 내구도가 0보다 작거나 같으면 깨짐)3. 모든 경우에서 최대한 많은 계란을 깬다면 그 숫자는?풀이 과정1. BF - DFS + 백트래킹으로 풀면 된다.2. 보면 결국 어떤 계란을 집었을 때에 하나씩 테스트하고, 그렇게 마지막까지 도달하면 하나의 경우를 테스트하는 것이다(BF - DFS)3. 그리고 그 테스트가 끝나면 아무일 없던 것처럼 계란을 돌려놓는다(백트래킹)4. 재귀함수를 통해서 구하고 ans를 구해주면 된다.코드import java.util.*;public class Main{ private static List eggList = new ArrayList(); private st..

문제 설명1. 첫번째 줄에 도시의 갯수가 주어진다.2. 그 다음은 여행 계획에 속한 도시의 수가 주어진다.3. 다음부터 그 줄의 도시가 어디랑 연결되었는지 주어진다.4. 마지막에는 여행을 가는 계획이 주어진다.풀이 과정1. 유니온 파인드 문제이다. 모든 도시가 연결되어 있는지를 파악한다.2. 주어지는 값들을 유니온해서(parent에 연결) 같은 루트에 있다고 맞춰준다.3. 이후로는 마지막에 주어진 계획 도시들이 다 같은 루트에 있는지만 파악하면 된다. 코드import java.util.*;public class Main{ private static int[] parent; private static int find(int x) { if (x == parent[x]) { return ..

문제 설명1. 첫째 줄에 회의의 갯수 N이 주어진다.2. 그 다음주터 N개의 회의 시작시간 - 끝나는 시간이 주어진다.3. 그 시간을 통해 모든 회의가 멈추지 않게 작동하는 회의실의 최소 갯수를 구하면 된다.풀이 과정 1. (내가 이렇게 풀어서 시간초과가 발생했었는데) 어떤 회의가 언제부터 언제인지를 알 필요는 없다. 2. 그냥 시작시간부터 회의실 하나의 자리를 차지하고 있고, 뭐가 됐든 나가는 시간에는 나간다는 것이다. 3. 그러니까 어떤 회의가 언제인지 알 필요는 없고, 언제 입장인지 언제 퇴장인지를 알면 된다. 4. 그러고 시간 순서대로 나열하면 회의실에 들어가 있는 회의의 갯수를 알 수 있다.  코드import java.util.*;public class Main { public static v..

문제 설명1. 첫째 줄에 맵의 크기랑 이동거리가 주어진다.2. .은 갈수 있는 곳, T는 장애물로 주어진다.3. 오른쪽 아래부터 시작해서 오른쪽 위까지 이동거리로 이동할 수 있는 경우의 수를 구한다.4. 한번 지나간 길로는 못간다.풀이 과정 1. DFS 문제이다. 2. 한번 지나갔거나, 장애물이 있는 곳은 true, 나머지는 false로 구한다. 3. 현재 위치에서 DFS할 때에 이동할 곳을 이동처리하고 그 DFS끝나면 다시 이동 가능하게 하면 된다. (가게 되면 방문한거니까) 코드/****************************************************************************** Online Java Compile..

문제 설명1. 배열의 요소들을 왼쪽으로 돌리는거다.2. 그리고 맨 뒤에 애는 오른쪽 끝으로 가는식  풀이 과정 1. 딱히 어려운 문제는 아니지만, 성능에 이슈가 있을 수 있다. 2. 간단하게 말하면 어디까지 가야할지를 확인하고 돌리면 된다. 3. 근데 그거를 매번 돌릴 필요 없고 얼마나 가면 되는지 알면 되는데, 어차피 배열 전체 크기는 정해져 있으니 갈 거리에서 배열크기 나머지를 구하면 이동한 변위가 된다.  public static List rotLeft(List a, int d) { int maxLength = a.size(); d %= maxLength; List ans = new ArrayList(Collections.nCopies(max..