반응형 탐욕(Greedy)6 [프로그래머스] 단속카메라 [JAVA(자바)] ‘프로그래머스 코딩테스트 고득점 Kit’ 문제 입니다. 😀 문제 👉 1. 문제 고속도로를 이동하는 모든 차량이 고속도로를 이용하면서 단속용 카메라를 한 번은 만나도록 카메라를 설치하려고 한다. 고속도로를 이동하는 차량의 경로 routes가 매개변수로 주어질 때, 모든 차량이 한 번은 단속용 카메라를 만나도록 하려면 최소 몇 대의 카메라를 설치해야 하는지를 return 한다. 2. 풀이 Greedy 를 이용한 문제 풀이 진출 시점을 기준으로 오름차순으로 정렬 진출하려는 차량이 카메라를 한번이라도 거쳤는지 확인하기 위해 카메라의 초기 위치는 -30000 으로 설정 (설치는 아님) 카메라의 위치가 진입 시점 이전이라면 진출 시점에 설치 3. 코드 import java.util.*; class Solution .. 2021. 11. 25. [프로그래머스] 구명보트 [JAVA(자바)] ‘프로그래머스 코딩테스트 고득점 Kit’ 문제 입니다. 😀 문제 👉 1. 문제 구명보트에 1명 또는 최대 2명을 태워 무인도에서 구출한다. 2명의 무게가 구명보트의 무게 제한을 넘지 않을 때만 2명이 탄다. 구출에 필요한 최소의 구명보트를 return한다. 2. 풀이 Greedy 를 이용한 문제 풀이 사람들의 무게를 정렬한다. 가장 무거운 사람과 가장 가벼운 사람의 무게를 통해 2명이 탈 지 1명이 탈지 정한다. 3. 코드 import java.util.*; class Solution { public int solution(int[] people, int limit) { int answer = 0; Arrays.sort(people); int i = 0; for (int j=people.length-1; i 2021. 11. 25. [프로그래머스] 섬 연결하기 [JAVA(자바)] ‘프로그래머스 코딩테스트 고득점 Kit’ 문제 입니다. 😀 문제 👉 1. 문제 n개의 섬 사이에 다리를 건설하는 비용(costs)이 주어질 때, 최소의 비용으로 모든 섬이 서로 통행 가능하도록 만들 때 필요한 최소 비용을 return 하도록 solution을 완성하세요. costs를 그림으로 표현하면 다음과 같으며, 이때 초록색 경로로 연결하는 것이 가장 적은 비용으로 모두를 통행할 수 있도록 만드는 방법입니다. 2. 풀이 Greedy 와 Union-Find 를 이용한 문제 풀이 Union-Find Union-Find 란 여러개의 노드가 존재할 때 연결된 노드들을 같은 집합 구성원으로 묶어주는 알고리즘이다. 그림과 같이 각 노드들의 번호와 연결된 노드들이 주어졌을 때, 몇개의 집합이 있는지, 각 노드들은.. 2021. 11. 25. [프로그래머스] 큰 수 만들기 [JAVA(자바)] ‘프로그래머스 코딩테스트 고득점 Kit’ 문제 입니다. 😀 문제 👉 1. 문제 어떤 숫자에서 k개의 수를 제거했을 때 얻을 수 있는 가장 큰 숫자를 구한다. 2. 풀이 Greedy 를 이용한 문제 풀이 index는 1 부터 이전 index와 비교한다. 이전 값이 작을 때 이전 값 제거 이전 값이 클 때 index가 마지막이면 값 제거 index + 1 3. 코드 class Solution { public String solution(String number, int k) { StringBuilder sb = new StringBuilder(); sb.append(number); int idx = 1; while (k != 0) { // 이전값이 작을 때 if (idx >= 1 && sb.charAt(id.. 2021. 11. 25. [프로그래머스] 체육복 [JAVA(자바)] ‘프로그래머스 코딩테스트 고득점 Kit’ 문제 입니다. 😀 문제 👉 1. 문제 체육복을 잃어버린 학생은 앞 뒤 번호 학생들 중 여벌의 체육이 있는 학새에게 체육복을 빌릴 수 있다. 여벌의 체육이 있는 학생이 도난을 당한 경우는 체육복 하나만 도난당한 것이며, 남은 체육복을 다른 학생에게 빌려줄 수 없다. 2. 풀이 Greedy 를 이용한 문제 풀이 전체 학생의 체육복 개수를 하나의 배열에 저장한다. 기본 체육복의 개수를 배열의 초기값이 0으로 가정 여분의 체육복이 있을 경우 : +1 체육을 도난당한 경우 : -1 체육복의 개수가 -1인 학생의 경우 왼쪽/오른쪽 학생을 확인하고 빌릴 수 있으면 빌린다. 3. 코드 class Solution { public int solution(int n, int[] lo.. 2021. 11. 25. [프로그래머스] 조이스틱 [JAVA(자바)] ‘프로그래머스 코딩테스트 고득점 Kit’ 문제 입니다. 😀 문제 👉 1. 문제 모든 글자가 A로 구성된 문자를 조이스틱을 최소한의 조작 횟수로 원하는 문자를 만들어야 한다. 조이스틱을 각 방향으로 움직이면 아래와 같다. ▲ - 다음 알파벳 ▼ - 이전 알파벳 (A에서 아래쪽으로 이동하면 Z로) ◀ - 커서를 왼쪽으로 이동 (첫 번째 위치에서 왼쪽으로 이동하면 마지막 문자에 커서) ▶ - 커서를 오른쪽으로 이동 2. 풀이 Greedy 를 이용한 문제 풀이 알파벳 변경을 위해 A->B->C 방향과 A->Z->Y 방향 중 가까운 것으로 한다. 커서 이동을 할 경우 연속된 A가 나오면 이동할 커서의 값이 줄어든다. 커서를 오른쪽으로 순서대로 이동하는 경우 (array.length - 1) Ex) ABCAAAAA.. 2021. 11. 25. 이전 1 다음 반응형
