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)원의 경..
Programmers - 연속 펄스 부분 수열의 합 with JAVA
로직 1. 1,-1,1,-1,1,-1 .... , -1,1,-1,1,-1,1 을 곱한 수열을 각각 판단한다. 2. DP를 활용해 최댓값을 구한다. 3. 두가지 수열이 가질 수 있는 각각의 최댓값 중 큰 값을 반환한다. 메인 아이디어 : "DP, 현재 수의 앞의 있는 값들의 합이 음수라면 고려하지 않는다. 즉, 연속 집합에서 앞의 집합의 합이 음수라면 더이상 지금의 집합부터는 더 큰수를 만들 수 없으니 버린다." 예를 들어, 1에서 곱한 값이 아래와 같다고 가정하자. 11, -3, -6, -1, 3, 1, 2, -4 [11] -> Max = 11, sum = 11 [11, -3] -> Max = 11, sum =8 [11, -3, -6] -> Max = 11, sum = 2 [11, -3, -6, -1] ..
Programmers - 시소짝궁 with JAVA
로직 아이디어 : 무게에 (1, 1/2, 2/3, 3/4, 4/3, 3/2, 2)를 곱한 값이 다른 사람들 중 존재한다면 answer += 1 이다. 몰랐던 점 : 같은 무게라도 다른 사람이다. 따라서 Map의 모든 값을 더해줘야한다. 코드 1 - Map을 활용해 메모이제이션한 경우 import java.util.*; class Solution { public long solution(int[] weights) { long answer = 0; double[] times = {1.0, 2.0/4, 3.0/4, 2.0/3, 4.0/3, 3.0/2, 2.0}; Map map = new HashMap(); for(double weight : weights) { map.put(weight, map.getOrDe..
