T_era

1. 문제 내용map의 시작점에서 끝점까지 좌표의 값이 1인 곳만 통해서 최단거리를 구하라단, 경로가 없다면 -1을 반환2. 접근 방법최단경로를 구하는 문제이므로 BFS를 적용해 보았다3. 구현 과정int rows = maps.length;int cols = maps[0].length;Queue queue = new LinkedList();boolean[][] visited = new boolean[rows][cols];int[][] distance = new int[rows][cols];int[] dy = {-1, 1, 0, 0};int[] dx = {0, 0, -1, 1};사용할 변수들queue.offer(new int[]{0, 0, 1});visited[0][0] = true;distance[0][..

1. 문제 내용요약n개의 컴퓨터가 있고, n개의 컴퓨터가 제각각 연결되어있을 때 총 네트워크망의 개수를 구해라2. 접근 방법탐색 한번에 연결되있는 모든 컴퓨터를 찾고 탐색이 되지않은 컴퓨터가 있을 때 탐색을 또 하는 방식으로 하면 될 것으로 생각되서 적합한 DFS를 사용했다3. 구현 과정public void dfs(int n, int[][] arr, boolean[] visible, int index){ if(!visible[index]) { visible[index] = true; for (int i = 0; i visible을 통해 탐색기록을 저장면서 최초탐색의 경우 연결된 컴퓨터를 다시 탐색한다public int solution(int n, int[][] compute..

1. 문제 내용요약수열이 있으면 가장 큰 수가 나오는 부분 수열의 합을 구해라단, 합을 구하기 전에 1,-1 또는 -1,1을 번갈아가면서 곱해준 후에 더해라2. 접근방법 매 수열의 최대 값을 저장하면서 계산하면 되는 것으로 보인다현재 자신의 값과 이전에 저장한 최대값을 연산을 하면 최대값이 저장될 듯하다이전에 연산한 내용을 저장하고 더 큰값이 나오면 처음부터 연산하는 과정을 떠올려 DP를 적용해봤다점화식 Math.max(sequence[i] * (-1 or 1), dp[i - 1] + sequence[i] * (-1 or 1));3. 구현과정long answer = Integer.MIN_VALUE;long[] dp1 = new long[sequence.length];long[] dp2 = new long..

1. 문제 내용요약정수 배열이 입력되면 그 정수들이 +,-를 통해 target 값을 만들 수 있는 경우의 수를 반환하라2. 접근방법모든 경우를 탐색해야하고 +의 경우와 -의 경우가 나누어져 있는 것이 트리의 형태와 비슷한걸로 보인다그러므로 트리의 모든 경우의 수를 찾기 위해 DFS를 사용해 보았다3. 구현과정class Solution { int count = 0; public int solution(int[] numbers, int target) { dfs(numbers, target, 0, 0); return count; } public void dfs(int[] numbers, int target, int index ,int total){ i..

1. 문제 내용요약현재 내 피로도와 2차원 배열에 최소 입장 피로도와 입장시 소모 피로도가 입력된다현재 내 피로도로 던전 최대한 많이 던전에 들어갈 수 있는 수를 출력하라2. 접근 방법 모든 배열의 값들을 순차적으로 전부 비교하여 입장 횟수가 가장 높은 값을 출력하면 될 것 같다3. 구현 과정Queue queue = new LinkedList();for(int i = 0; i 순차적으로 비교하기 위한 큐를 생성해 던전배열을 저장public int search(Queue queue, int k, int count){ if(queue.isEmpty()) return count; int length = queue.size(); int inCount = count; ..

1. 문제 내용요약테두리는 brown 안에는 yellow인 카펫이 있는데 brown의 개수와 yellow의 개수를 입력받으면 만들어지는 카펫의 가로길이와 세로길이를 출력하라단, 세로길이는 가로길이보다 작거나 같다2. 접근방법첫번째 줄의 경우 무조건 brown이 채워지니 brown이 첫줄에 3개(가운데 yellow가 들어가기 시작하는 경우)를 채운 시점에서부터 하나씩 경우를 확인해서 brown과 yellow를 정확히 쓰는 경우를 찾아보자3. 구현 과정class Solution { public int[] solution(int brown, int yellow) { for(int i = 3; i = y && ((brown - tb) / 2) * (i - 2) == yellow){ ..

1. 문제 내용요약입력된 문자열을 1개씩 분해하여 모든 조합에서 소수인 것을 찾기2. 접근방법 모든 경우의 수를 확인해야하므로 완전탐색 기법을 사용해봤다그리고 중복되는 값의 경우는 Set을 사용해 제외하면 될 것 같다3. 구현 과정int count = 0;char[] numberArray = numbers.toCharArray();Queue queue = new LinkedList();Set set = new HashSet();for(char number : numberArray){ queue.offer(String.valueOf(number));}입력된 값을 한글자씩 쪼개서 배열화하고 queue에 저장queue는 값을 순차적으로 사용하기위해 사용그리고 중복값을 제외하기위한 set public vo..

1. 문제 내용요약시작점과 끝점까지의 최단경로의 갯수 구하기단, 입력값으로 중간에 길이 막혀있는 경우도 있다2. 접근방법 최단경로를 구하기위해 DP를 이용해봤다.DP를 이용해 이미 방문했던 좌표를 판단하여 그 이후는 탐색을 하지않고 값을 가져오는 과정을 거쳐 해결하면 될 것 같다3. 구현과정 처음에 재귀호출을 통해 구현을 해보았는데 코드는 아래와 같다int[][] dp = new int[n][m];dp[n-1][m-1] = 1;for(int i = 0; i 일단 탑다운DP를 사용했기 때문에 배열의 마지막위치를 1로 초기화를 하고 물웅덩이의 위치를 -1로 초기화해주었다그외에는 0으로 자동초기화 된다public int mapping(int[][] dp, int x, int y, int n, int m){ ..

1.문제 내용요약삼각형 꼭대기부터 자식노드 2개 중 하나를 더하여 바닥까지 더했을 때 최대값 구하기2. 접근방법간단하게 재귀 함수를 통해 구현해 보았는데 시간초과가 발생해서 원인을 고민해보니 같은 문제를 탐색하는 과정이 있어서 그런거였다. 그래서 이를 해결하기위해 DP를 알아보게 되었고 DP를 사용해 풀어보기로 하였다3. 구현과정class Solution { public int solution(int[][] triangle) { int answer = getMax(triangle, 0, 0); return answer; } public int getMax(int[][] triangle, int x, int y) { if(x == triangle.len..

1. 문제내용요약I 숫자는 큐에 삽입D 1은 최대값 삭제D -1은 최솟값 삭제위 세가지를 진행하고 원하는 데로 진행하고 큐에 남은 값이 있을 때 {최대값, 최소값} 을 출력하라2. 접근방법최대, 최소값을 찾는 방법에 힙을 사용하면 간편하게 된다는 걸 생각해 우선순위 큐를 사용해 적용해보면 될 것 같다3. 구현과정최대, 최소값을 관리할 큐 두개 생성PriorityQueue minQueue = new PriorityQueue();PriorityQueue maxQueue = new PriorityQueue(Comparator.reverseOrder());입력받은 요청을 Split으로 구분 하고 삽입구문엔 두 큐 모두 데이터 삽입삭제구문엔 -1과 1을 구분하여 최대 최소값 삭제하고 반대 큐에 같은 값 삭제for..