목록greedy (23)
기록방
👉 문제링크🔸 문제 분석 🔸N개의 단어가 주어진다. 단어는 알파벳으로 구성되어 있는데, 각 알파벳은 0~9 숫자로 변환할 수 있다.알파벳은 최대 10종류가 주어지고, 알파벳의 숫자는 겹치지 않아야 한다.N개의 단어를 숫자로 변환했을 때 총합의 최대값을 출력한다.🔸 문제 풀이 🔸각 알파벳이 어떤 숫자와 매칭 되어야 최대값이 되는지 찾는 문제이다.Brute Force로 전부 넣어봐도 찾을 수 있지만, 좀더 효율적으로 찾고자 각 알파벳 별 가중치를 계산한다.가중치 순서대로 9부터 0까지 부여한 후 값을 계산해 출력한다.🔸 코드 🔸import java.io.*;import java.util.Arrays;public class Main { public static void main(String[..
👉 문제링크 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 🔸 문제 분석 🔸 x축에 평행한 미사일들의 시작과 끝 인덱스가 주어진다. 요격 하기 위해서 미사일들의 범위에 해당하는 곳을 선택해야하며 끝 인덱스에 걸칠 수는 없다. 요격에 필요한 미사일의 최소 수를 구한다. 🔸 문제 풀이 🔸 최소한의 요격 미사일 개수로 최대한 많은 수의 폭격 미사일을 요격해야 하므로 그리디 문제로 볼 수 있다. 포격 미사일의 범위가 겹치는 인덱스를 빠르게 알기 위해 끝 인덱스로 오름차순 정렬한다. 문제에서의 제한 사항으로 실수 좌표도 가능하며 끝 인덱스에 겹치면 안된다. 이전 ..
👉 문제링크 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 🔸 문제 분석 🔸 k개의 귤을 선택할 때, 귤의 크기 종류의 최소값을 반환한다. 🔸 문제 풀이 🔸 귤의 크기 종류와 각각의 귤 개수를 카운트한다. 그리디하게 접근해서, 귤 개수가 많은 종류부터 k개를 고른다면 최소한의 종류로 선택할 수 있다. 🔸 코드 🔸 import java.util.HashMap; import java.util.Map; import java.util.ArrayList; import java.util.List; class Solution { public int solution(i..
👉 문제링크 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 🔸 문제 분석 🔸 0에서 n까지 이동하는 최소 점프 수를 반환한다. 점프하면 한 칸 앞으로 이동한다. 텔레포트하면 현재 인덱스의 2배 인덱스로 이동하고, 점프 수는 증가하지 않는다. 🔸 문제 풀이 🔸 텔레포트는 짝수 인덱스에서만 가능하고, 점프 수가 증가하지 않으므로 무조건 많이 쓰면 좋다. 0부터 시작해 n으로 향하면, 쓸 데 없는 경우의 수가 많아지므로 확실히 도착하는 경로를 찾기 위해서 n부터 시작해 0으로 끝나도록 계산한다. 현재 수가 짝수라면 n/2 절반 인덱스로 이동한다. (텔레포트) ..
👉 문제링크 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 🔸 문제 분석 🔸 사람을 무게 제한이 limit인 구명 보트로 각각 최대 2명씩 구조할 수 있다. 모든 사람을 구하기 위한 구명보트 개수의 최솟값을 반환한다. 🔸 문제 풀이 🔸 그리디적으로 접근한다. 사람들의 몸무게를 정렬한다. 오름차순으로 정렬했을때 가장 무거운 사람이 오른쪽 끝에 있다. 가장 무거운 사람을 옮길 때 가장 가벼운 사람과 같이 탈 수 없다면, 혼자만 탈 수 있다. 가장 무거운 사람 + 가장 가벼운 사람 둘이 탈 수 있으면 타고 탈출하면 된다. 🔸 코드 🔸 import java.ut..