Hello backEnd

문제 설명1. 배열이 주어진다.2. 모든 학생은 사탕을 최소 1개 이상을 가진다.3. 양 옆 학생 중 나보다 점수가 낮은 녀석들 보다는 사탕을 많이 가져야 한다.3-1. 참고로 나랑 점수가 같으면 어떨지는 상관이 없다.풀이 과정 1. 무조건 사탕을 1개만 받는 사람들을 큐에 넣는다. (양옆이 모두 나보다 크거나 같은 경우)2. 그 사람들부터 시작해서 오른쪽 왼쪽 모두 찾는다.3. 다음에 찾은 친구의 점수가 이전 친구보다 높다면, 사탕을 그보다 1개 이상 더 가지고 있어야 한다.4. 그런데, 그 높은 친구의 반대쪽에도 더 점수가 낮은 학생이 있을 수 있다.5. 우리는 이미 모든 위치에서 찾기로 했다. 결국 최종적으로 어떤 학생은 양옆보다 큰 숫자를 가지고 있으면 된다.6. 이렇게 해서 구한 모든 사탕을 더..

문제 설명1. 게임판 크기 N 이 주어진다.2. 현 위치의 숫자만큼만 오른쪽 혹은 아래로 이동 가능하다.3. 왼쪽 위부터 시작해서 오른쪽 아래로 갈 수 있는지를 체크하면 된다.풀이 과정1. DFS2. 굉장히 쉬운 문제다. 그냥 위치 확인하고 DFS 해주면 간단하게 풀린다.3. 현재 위치를 지나왔다고 체크하고, 거기서 점프하는걸 하면 해결 가능(근데 나는 살짝 더럽게 풀었는데, 그냥 check라는 배열을 하나 더 만들면 조금 더 깔끔하게 해결 가능하다.)코드import java.util.*;import java.io.*;public class Main{ private static int N; private static int[][] map; private static int[] xMove ..

문제 설명1. N, M이 주어진다.2. 1~N 의 숫자를 가진 애들이 N-1줄 주어지는데 두 점이랑 거리가 주어진다.3. 그 다음에는 M개의 노드 쌍이 주어진다.4. 3번 과정에 애들에 대해 거리를 출력하면 된다.풀이 과정1. DFS + 백트래킹2. 얘랑 비슷하다.3. 노드를 각자 가지고 있고 그 거리를 DFS로 갱신시키면서 봐주면 된다.4. 그리고 현재 방문한 곳은 check해주고 다시 안보면 된다.코드/****************************************************************************** Online Java Compiler. Code, Compile, Run and Debug java program online. Write your code in..

문제 설명1. 사람 수 N, 관계 수 M 이 주어진다.2. 그 다음부터 M 개로 관계들이 주어진다.3. A - B - C - D - E 이렇게 친구인지 여부를 구하면 된다.풀이 과정1. DFS + 백트래킹2. 각 친구 상태를 가지는 ArrayList 를 배열로 가지면 된다.3. 현 사람을 기준으로 모든 관계 ArrayList 를 찾고 주르륵 찾으면 된다.4. 그리고 이전에 확인한 사람인지 체크 여부를 확인해서 백트래킹 해주면 된다.5. 이게 잘 동작하는 이유는 어차피 이전으로 돌아가지 않으니 depth 가 차면 알아서 ABCDE 열차가 완성되기 때문이다.코드/****************************************************************************** Onl..

문제 설명1. 격자 N M 이 주어진다.2. 맵이 주어지고 높이가 주어진다.3. 현재 높이 기준으로    - 같은 높이 : 같은 산봉우리    - 같은 산봉우리 주변에는 얘보다 낮은 높이밖에 없어야 한다.4. 산봉우리 개수를 구하면 된다.풀이 과정1. DFS문제이다.2. 모든 위치에서 주변 7방향 모두를 확인해준다.3. 그 중에 하나라도 얘보다 높으면 이건 산봉우리가 아니다.4. 같은 높이가 있으면 걔도 같은 산봉우리인지 확인해야 한다. 그 주변 애가 산봉우리가 아니라면 당연히 얘도 아니다.5. 산봉우리인지 체크를 한다면 그거는 모두 방문처리해준다.6. 그리고 산봉우리인지 return해서 호출한 메인쪽에서 확인해서 구하면 된다.코드/****************************************..

문제 설명1. 테스트 케이스 개수가 주어진다.2. N이 주어지면, 1부터 N 까지 오른차순 수열이 있다.3. '+' '-' ' ' 이렇게 삽입된다. 4. 이렇게해서 1 ~ N 까지의 수식이 완성되었을 때 그 수식의 결과가 0이 되면 그걸 출력한다.5. 참고로 ASCII 순서에 따라 출력한다.풀이 과정1. BF + DFS문제이다.2. String에다가 모든 수식이랑 숫자를 다 DFS로 찾도록 구하고 그걸 처리하면 된다.3. 계산하는 방법은 공백 없이 문자를 이어주고(이러면 알아서 붙음) 수식 위치를 구한 후에 숫자를 뽑아서 이 수식대로 처리해주면 된다.4. 0이 되면 출력5. 참고로 ASCII 순서에 따라 DFS처리하면 간단하다 ' ' -> '+' -> '-' 순서임.코드import java.util.*;..

한번 틀려서 다시 풀었었다.문제 설명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. 테스트 케이스 개수가 주어진다.2. 몇개의 MBTI가 주어질지 알려주고3. MBTI가 주어진다.4. 다른 알파뱃만큼 거리가 있는 것이다.풀이 과정1. 나는 좀 골때리게 풀었다.2. HashMap을 두고 같은 MBTI가 3개 이상 주어졌는지 확인한다.3. 중복 3개까지는 list에 저장하고 그거 넘으면 저장 안한다.4. 이후로 list를 실제로 돌면서 심리적 거리를 구하고 넣으면 된다.5. 이렇게 한 이유는 모든 MBTI가 같은 경우 나 중복을 제거했더니 2개만 남는 경우 를 제외하기 위해서이다. 특히 2개만 남으면 이게 뭐가 어떤 갯수를 가졌는지 몰라서 난감해지기 때문.코드import java.util.*;public class Main{ public static void main(S..

문제 설명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 에 모든 사람을 각각 넣어가면서 확인하고, 그래서 모든 사람에 대한 팀배정..