모항이코딩한다

풀이방법 사용된 것: Comparator 오버라이딩 2022.03.05 문제에서 제시하는 기준에 맞게 정렬하는 Comparator를 정의하여 사용해주면 된다. 이 때, str1.compareTo(str2);를 사용하였는데, 이 함수는 str1이 사전순으로 str2보다 앞설 때는 음수를, 그렇지 않을 때는 양수를 리턴한다. 코드 Java(2022.03.05) import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Arrays; import java.util.Comparator; public class Main { static int n;//기타 개수 static St..

풀이방법 사용된 것: 큐 2022.03.02 큐를 활용했다. 이번 턴에 뱀 머리가 새롭게 이동해야 하는 칸의 좌표가 (row, col)이라 하자. 만약 (row, col)의 위치에 뱀의 몸이 있거나 벽이 있다면 게임을 종료하고, 현재 시간을 화면에 출력한다. 만약 (row, col)의 위치에 아무것도 없다면, 큐에 (row, col)을 넣어주고 큐의 반대쪽 끝에서 요소 하나를 poll 한다. 만약 (row, col)의 위치에 사과가 있다면, 큐에 (row, col)을 넣어주고 큐에서 아무것도 poll 하지 않는다. 방의 각 좌표에 무엇이 있는지는 2차원 정수 배열로 기록하였다. 해당 칸에 아무것도 없다면 0을, 뱀의 몸이나 머리가 있다면 1을, 사과가 있다면 2를 저장하였다. 코드 Java(2022.03..

풀이방법 2022.03.02 기준이 되는 문자열의 알파벳별 개수를 센다. 길이가 26인 정수 배열 arr1을 선언하여, arr1[0]에는 A의 개수를, arr1[1]에는 B의 개수를... arr1[25]에는 Z의 개수를 저장하는 방식으로 세면 된다. 그 다음 문자열부터 다음의 과정을 거친다. 1. 기준문자열의 알파벳별 개수를 셌던 것과 같은 방식으로, 문자열의 알파벳별 개수를 세어 arr2에 저장한다. 2. int[] gap을 선언한다. gap[i] = arr1[i] - arr2[i]이다. 3. gap[0]~gap[25]를 점검한다. 2 이상의 정수 혹은 -2 이하의 정수가 저장된 요소가 존재하면 즉시 점검을 종료하고 다음 문자열로 넘어간다. 2개 이상의 문자를 변경해야 할 경우, 이 문자열은 비슷한 문..

풀이방법 사용된 것: 스택 2022.03.02 boolean 형 변수 v를 사용한다. 해당 문자열이 올바른 괄호 문자열이면 v 를 true로, 그렇지 않으면 false로 설정할 것이다. v의 초기값은 true이다. 반복문 내에서, 주어진 문자열을 가장 앞 글자부터 한 글자씩 다룬다. 이번 문자가 '(' 라면 스택에 넣는다. 이번 문자가 ')' 라면, 현재 스택에 '(' 가 하나 이상 들어있을 경우 '(' 하나를 pop 한다. 현재 스택이 비어있다면 이 문자열은 올바른 괄호 문자열이 아니다. v의 값을 false로 바꾸고 반복문을 종료한다. 중단 없이 문자열의 마지막 글자까지 처리를 마쳤다면, 이 때 스택이 비어있으면 이 문자열은 올바른 괄호 문자열이다. 이 때 스택에 '(' 가 하나 이상 남아있다면 이 ..

풀이방법 사용된 것: 브루트포스 0부터 시작하여 n 미만의 모든 정수를 점검하는 방법이 가장 빠른 방법이므로 브루트포스 알고리즘이 적합하다. 2022.03.02 0부터 시작하여, n 미만의 모든 정수의 분해합을 구해본다. 분해합이 n인 정수가 발견되면 즉시 그 정수를 화면에 출력하고 프로그램을 종료한다. n-1까지 모두 점검하였는데도 해당하는 수가 없다면 화면에 0을 출력하고 프로그램을 종료한다. 코드 Java(2022.03.02) import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; public class Main { static int n; static int a,b,c,d,e,f,g;//..

풀이방법 사용된 것: 그리디 알고리즘 정렬 2022.02.24 자라는 데 가장 오래 걸리는 나무부터 심어야 한다. 그러므로 자라는 데 걸리는 일 수를 내림차순 정렬해준다. 정렬된 배열의 앞에 있는 나무부터 심는다. 한 나무가 다 자라는 날의 날짜는, (이 나무를 심기 전에 다른 나무를 심느라 보낸 시간) + (이 나무를 심는 데 걸리는 하루) + (이 나무가 자라는 데 걸리는 시간) 이다. 모든 나무에 대하여, 다 자라는 날의 날짜를 구한다. 다 자라는 날이 가장 나중인 놈이 있을 것이다. 그놈이 다 자라는 날짜가 바로 정답이다. 코드 Java(2022.02.24) import java.io.BufferedReader; import java.io.IOException; import java.io.Inpu..

풀이방법 사용된 것: 그리디 알고리즘 2022.02.24 예제를 통해 설명하겠다. n = 5, k = 6 사람이 5명, 만들어야 하는 관계가 6개인 경우를 보자. 일단 초기상태로, 5명에게 오름차순으로 쪽지를 쥐어준다. 이 상태에서 쪽지를 한 단계에 하나씩만 옮길 것이다. 하나를 옮길 때마다, 그렇고 그런 관계들이 새로 생기게 된다. 그럼 새로 생긴 만큼을 k에서 빼준다. k가 0이 될 때까지 이를 반복한다. 첫 번째 단계이다. 현재 k = 6이다. 쪽지를 하나만 옮겨서 가장 많은 그렇고 그런 관계를 만드는 방법은 무엇일까? 그렇다. 숫자의 크기가 가장 큰 쪽지를 제일 왼쪽으로 보내는 것이다. 다음과 같이 움직이면 된다. 그렇고 그런 관계가 4개 만들어졌다. (5, 1), (5, 2), (5, 3), (..

풀이방법 사용된 것: 그리디 알고리즘 정렬 Comparator 재정의 2022.02.24 각 날마다, 5000원짜리와 1000원짜리 중 무조건 더 맛있는 것을 고른다. 두 메뉴의 맛수치가 같다면 1000원짜리를 고른다. 그 후, 사용할 돈이 예산을 초과하는지 체크한다. 초과하지 않는다면 지금의 맛수치 합을 출력하고 프로그램을 종료한다. 예산을 초과한다면 다음과 같이 돈 아끼기를 수행한다. 일단, 각 날마다 '맛손실'을 구한다. 맛손실이란, 5000원짜리를 고르지 않고 1000원짜리를 골랐을 때 손해보는 맛수치의 크기이다. 즉, (5000원짜리의 맛수치 - 1000짜리의 맛수치) 이다. 1000원짜리가 더 맛있는 날에는 맛손실이 음수이다. 맛손실을 기준으로 날들을 오름차순 정렬한다. 그 후, 정렬된 배열의..

풀이방법 사용된 것: 정렬 동적 프로그래밍(DP) 2022.02.24 이 문제는 DP를 사용하기에 적합하다. n번째 사람의 최종 소요시간은 n-1번째 사람의 최종 소요시간에 자신의 개인 소요시간을 더한 것이다. 즉 앞사람의 최종 소요시간을 구하는 것이 뒷사람의 최종 소요시간을 구하는 문제의 부분 과제이다. 사람들의 개인 소요시간을 담은 배열을 오름차순으로 정렬한 뒤, DP를 이용해 앞 사람부터 차곡차곡 수를 더해가며 값을 기록해주면 된다. 코드 언어(2022.02.24) import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Arrays; import java.ut..

풀이방법 사용된 것: 동적 프로그래밍 깊이우선탐색(DFS) 2022.02.23 오답노트 #15681 : 트리와 쿼리 풀이방법 및 문제점 2022.02.12 55%에서 시간초과가 난다. 예제의 답은 옳게 출력된다. 일단은 출력 방식을 바꾸어봐야겠다. 18870번 문제를 풀 때처럼 System.out.println을 Q번 수행한 것이 문제일 수 있 blowupmomo.tistory.com 동적 프로그래밍을 사용한다. n번 노드의 자식이 m1, m2라 할 때, n의 서브노드의 개수는 m1의 서브노드 개수 + m2의 서브노드 개수 + 1 이다. 따라서 이 문제는 동적 프로그래밍으로 풀기에 알맞다. 간선정보를 일단 이중 ArrayList에 저장해둔다. 이 정보를 활용하여, 루트에서 출발하여 모든 노드를 DFS 순..