정리60 탐욕법 - 단속카메라 프로그래머스(탐욕법) - 단속카메라 해당 문제는 생각하기에 따라 어려울 수도 있고 쉬울수도 있을듯합니다. 먼저입력받은 route를 진출지점 기준으로 오름차순으로 정렬한 후 진입지점이 카메라 위치보다 먼곳에 위치하면 진출지점에 카메라를 설치하도록 합니다. 진출지점 기준으로 오름차순으로 정렬했기 때문에 다음 route의 진입 지점이 카메라 위치보다 작다면 카메라를 설치할 필요가 없습니다. public int solution(int[][] routes) { int answer = 0; PriorityQueue priorityQueue = new PriorityQueue(Comparator.comparingInt(o -> o[1])); int cameraIndex = Integer.MIN_VALUE; for (.. 2022. 3. 3. 탐욕법 - 섬 연결하기 프로그래머스(탐욕법) - 섬 연결하기 해당 문제를 봤을때 제한사항으로 costs의 길이가 있기에, 한 좌표에서 각 좌표까지의 path costs를 구해 각 좌표별 최소 path를 구한 후 set에 다리를 연결 하는 방식으로 진행하려고 했습니다. 정상적으로 풀지 못해, 결국 인터넷 검색의 힘을 구했고, 해당 문제가 최소신장트리(MST), Kruskal(크루스칼) 알고리즘 과 관련된 문제라는 것을 알 수 있었습니다. public int solution(int n, int[][] costs) { int answer = 0; int[] parent = new int[n]; PriorityQueue priorityQueue = new PriorityQueue(Comparator.comparingInt(o -> o.. 2022. 3. 2. 탐욕법 - 구명보트 프로그래머스 (탐욕법) - 구명보트 해당 문제를 처음 풀때에 3가지 방법을 통해 풀어보려고 했습니다. 3가지 방법중 위에 2가지 방법은 효율성에서는 통과하지 못했고 마지막 방식만 통과하였습니다. 처음에는 정렬 없이 각 무게에 대해 다음 무게와의 합이 limit를 넘지않고 최대인 사람의 경우를 찾는 방식으로 진행했습니다. public int solution3(int[] people, int limit) { int answer = 0; int[] peopleWeights = Arrays.copyOf(people, people.length); for (int i = 0; i 0.. 2022. 3. 1. 탐욕법 - 큰 수 만들기 프로그래머스 (탐욕법) - 큰 수 만들기 해당 문제를 풀때에는 처음에는 문제를 제대로 이해 하지 못해 각 자릿수의 수를 구해 number 자리수 - k 자리수의 가장 큰수를 구했었습니다. 이후 문제를 이해해 보니 입력받은 문자의 순서는 유지한채로 k 만큼 수를 제거 했을 때 가장 큰수를 구하는 문제였습니다. 순서를 유지 해야 할 경우 가장 큰 수를 만들려면 앞자리가 가장 큰 것이 중요하기에 앞에서 k번째까지의 수중 가장 큰수가 있는 수까지 과감하게 제거 하는 방향으로 진행했습니다. base case는 제거해야하는 자릿수와 입력받은 숫자의 자릿수가 동일 할 때와 남은 제거해야 하는 수가 없을 경우 2가지로 정해 로직을 구현했습니다. public String solution(String number, int.. 2022. 2. 23. 이전 1 ··· 8 9 10 11 12 13 14 15 다음