이펙티브 자바를 읽다가 Comparator 인터페이스 코드를 봤습니다. 근데 @FunctionalInterface 어노테이션이 붙어있음에도 불구하고 두 개의 추상 메서드를 가지고 있는 겁니다!! package java.util; @FunctionalInterface public interface Comparator { // abstract method int compare(T o1, T o2); // abstract method boolean equals(Object obj); // few default and static methods } 헉 진짜 두 개네..! 사실 Java를 조금 만져보신 분들은 눈치를 채셨을 텐데요. 두 번째 추상 메서드가 equals 메서드라는 점이 눈에 띄었을 겁니다. 이점을 ..
🎨 문제 10942번: 팰린드롬? 총 M개의 줄에 걸쳐 홍준이의 질문에 대한 명우의 답을 입력으로 주어진 순서에 따라서 출력한다. 팰린드롬인 경우에는 1, 아닌 경우에는 0을 출력한다. www.acmicpc.net 📘 풀이 이 문제는 DP로 풀 수 있습니다. 문제를 정리하면 다음과 같습니다. 길이가 최대 2,000인 수열이 주어진다. 수열의 [S, E] 구간의 수가 펠린드롬인지 판별한다. 판별 질의는 최대 1,000,000 주어진다. 주어진 구간이 펠린드롬인지 판별하는 일반적인 방법은 구간 양 끝점부터 서로 같은 수인지 비교를 하는 방법입니다. 이 경우 한 쿼리 당 최대 수열의 길이만큼의 확인이 필요합니다. 하지만 질의가 1,000,000번 주어지기 때문에 매 번 비교를 할 수 없습니다. 그래서 이전 쿼..
🎨 문제 1513번: 경로 찾기 첫째 줄에 0개 방문했을 때, 1개 방문했을 때, ..., C개 방문했을 때 총 경로의 개수를 한 줄에 공백을 사이에 두고 출력한다. 경로의 개수는 1,000,007로 나눈 나머지를 출력한다. www.acmicpc.net 📘 풀이 이 문제는 DP로 풀 수 있습니다. 만약 완전 탐색을 할 경우 거쳐가는 오락실의 개수의 경우의 수(0~50)만큼 학원을 가는 경우의 수를 완전탐색으로 구하게 됩니다. 1,000,0007로 나누는 것을 보면 경우의 수가 아주 커서 이 방법은 옳지 않음을 짐작할 수 있습니다. 따라서 이동 경로를 기억하여 다음 연산에 사용하도록 합시다. DP문제 풀이의 중요한 포인트는 점화식도 있지만, 상태값도 중요합니다. 점화식은 특정 상태에서의 최적값을 구하는 식..
🎨 문제 https://www.acmicpc.net/problem/4781 4781번: 사탕 가게 각 테스트 케이스의 첫째 줄에는 가게에 있는 사탕 종류의 수 n과 상근이가 가지고 있는 돈의 양 m이 주어진다. (1 ≤ n ≤ 5,000, 0.01 ≤ m ≤ 100.00) m은 항상 소수점 둘째자리까지 주어진다. 다음 n개 www.acmicpc.net 📘 풀이 이 문제는 DP로 풀 수 있습니다. 특히 배낭 문제를 아신다면 쉽게 풀 수 있습니다. 문제의 특이한 점은 사탕의 가격이 소수점 둘째자리까지 표현된 소수인 점입니다. 소수 간 연산은 오차가 발생할 수 있으므로 소수를 정수로 변환해 주었습니다. 저는 문자열에서 '.'을 지워주는 방식을 선택했습니다. String input = "8.00"; String..
🎨 문제 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 📘 풀이 이 문제는 정렬과 그리디로 풀 수 있습니다. 폭격 미사일을 s에 대해 오름차순, e에 대해 내림차순으로 정렬합니다. // int[][] targets = [[s, e]] Arrays.sort(targets, (int[] a, int[] b) -> { if (a[0] - b[0] == 0) return b[1] - a[1]; return a[0] - b[0]; }); 요격 미사일을 최소한으로 사용해야 하기 때문에 최대한 많은 폭격 미사일이 겹치는 지점을 찾아야 합니다. 폭격 미사일은 (s, e..
🎨 문제 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 📘 풀이 이 문제는 분할 정복으로 풀 수 있습니다. 루트 노드를 기준으로 왼쪽 서브 트리와 오른쪽 서브 트리가 포화 이진 트리인지 확인하면 됩니다. 우선 포화 이진 트리에 대해 간단히 알아보겠습니다. 포화 이진 트리 포화 이진 트리는 모든 내부 노드가 두 개의 자식 노드를 가지며 모든 리프 노드가 동일한 깊이 또는 레벨을 갖습니다. 완전 이진트리는 레벨에 따라 노드의 개수가 정해져 있습니다. 루트 노드의 레벨을 0 레벨이라 했을 때 n 레벨의 노드의 개수는 2의 n승이 됩니다. 따라서 n레벨의 포화 ..
🎨 문제 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 📘 풀이 이 문제는 완전 탐색으로 해결할 수 있습니다. 할인율은 10%, 20%, 30%, 40% 중 하나로 설정됩니다. 각 이모티콘의 할인율을 정하고 이에 따라 이모티콘 플러스 가입자 수와 총판매액을 구할 수 있습니다. 따라서 가능한 할인율을 모두 구하고 이 둘이 최대인 값을 구하면 됩니다. DFS, 백트래킹으로 가능한 할인율 순열을 구합니다. private static final int[] RATE = {90, 80, 70, 60}; private void dfs(int[] emoticons, i..
🎨 문제 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 📘 풀이 이 문제는 그리디로 문제를 해결할 수 있습니다. 가장 멀리 있는 배달을 갔을 때 가장 멀리 있는 택배 상자를 수거하면 됩니다. 즉, 다음과 같은 전략으로 문제를 해결할 수 있습니다. 1. 배달 및 수거할 택배 상자가 남은 가장 먼 집부터 택배를 배달 및 수거합니다. 2. 트럭이 물류창고에서 출발해 가장 먼 집으로 이동할 때는 배달만 하고, 다시 물류창고로 돌아올 때는 수거만 합니다. 3. 트럭이 물류창고에서 출발할 때 항상 택배를 최대 개수만큼 배달하고, 물류창고로 돌아갈 때 최대 개수만큼 ..
