Programmers - 외벽점검 with JAVA (V)
로직 1. DIst의 조합을 구한다. 2. 새로운 Weak 생성 - N 범위 넘어가거나 뒤로가는 경우를 묶기위함. 3. 기존의 weak의 위치에서 출발해 weak의 길이만큼 점검시 종료 예시 weak = [1, 2, 3, 4] , n = 10 new_weak = [1, 2, 3, 4, 11, 12, 13, 14] - 1부터 출발 [1, 2, 3, 4] 모두 검사 가능한지 체크 - 2부터 출발 [2, 3, 4, 11] 모두 검사 가능한지 체크 4. 친구의 수가 부족하다면 늘려서 가장 적게 친구를 사용할때가 정답 코드 import java.util.*; class Solution { public static List check = new ArrayList(); public int solution(int n,..
Programmers - 인사고과 with JAVA
로직 편하게 점수를 A, B라고 하자. 조건에서는 현재 자신의 점수보다 A, B 둘다 높은 점수가 있다면 탈락이다. 예시 : (7, 1), (6, 2), (3, 2), (3, 1), (2, 2), (2, 1) 1. A를 내림차순으로 정렬한다. -> 앞에 있을수록 A점은 뒤에보다 높다. -> 따라서 항상 B점은 앞에보다 높아야한다. A : 7, 6, 3, 3, 2, 2 B : 1, 2, 2, 1, 2, 1 -> 이렇게 된다면 (3, 2), (3, 1)과 같이 A점이 같은 경우에 (3, 1)의 경우 앞에 있는 수들과 B점을 비교해야 한다. => 현재 점수의 A점은 앞에 A보다 작거나 같고 B점은 모른다. 2. A가 같다면 B를 오름차순으로 정렬한다. A : 7, 6, 3, 3, 2, 2 B : 1, 2, 1..
Programmers - 숫자블록 with JAVA
해결 이 문제는 숫자 범위에 대해 집중을 해야한다. 1부터 천만까지의 숫자를 사용해서 1부터 1억번째 블록중 5000개의 값을 알아내는 것이다. - 완전탐색으로는 해결하지 못함을 바로 알 수 있다. - 또한 구하고자하는 블록 값의 약수는 천만을 넘지 못한다. 로직 1. 블록의 제곱근을 구한다 예를 들어 20은 약수 [1, 2, 4, 5, 10, 20] 이 있다. 20의 제곱근은 약 4이다. 이때, 4까지의 수를 가지고 [a, b] -> [1, 20], [2, 10], [4, 5] 를 만들 수 있으니 제곱근까지만 판단을 한다. 2. 2부터 시작해 제곱근까지 해당 수를 나눌 것이고 만약 해당 약수가 천만을 넘어가면 패스한다. 3. 약수 중 가장 큰 값을 구한다. 코드 import java.util.*; cl..
Programmers - 거스름돈 with JAVA (V)
해설 전형적인 DP를 활용하는 문제이며, 밑에 예시를 통해 설명해보려고 한다. 동전 종류 : [1, 2, 5], 만드려는 수 : 5 1. 1원을 사용하는 경우 추가 1원 : [1], 2원 : [1, 1] 3원 : [1, 1, 1] 4원 : [1, 1, 1, 1] 5원 : [1, 1, 1, 1, 1] 2. 2원을 사용하는 경우 추가 1원 : [1] 2원 : [1, 1], [2] 3원 : [1, 1, 1], [1, 2] 4원 : [1, 1, 1, 1], [1, 1, 2], [2, 2] 5원 : [1, 1, 1, 1, 1], [1, 1, 1, 2], [1, 2, 2] 주목할 것은 이 부분이다. 3원 = 기존 3원의 경우의 수 + 1(3-2)원의 경우의 수 4원 = 기존 4원의 경우의 수 + 2(4-2)원의 경..
