2023.02.09(목) - 프로그래머스 고득점 Kit 스터디
- 체육복
// 제출 답안
package suhyeongLee.Gready.Workout_clothes;
import java.util.Arrays;
class Solution {
public int solution(int n, int[] lost, int[] reserve) {
// 처음 운동 가능 한 사람은 전체 인원에서 잃어버린 사람을 뺀 수
int answer = n - lost.length;
Arrays.sort(lost); // 실제 정답 데이터에 sort 안된 데이터가 존재
Arrays.sort(reserve);
// 잃어 버린 사람과 여분이 있는 사람이 같을 경우 하나만 가지고 온 사람과 동일함
// 해당 자리에 사람 번호 대신 음수를 넣어 표기
for(int i = 0; i < lost.length; i++){
for(int j = 0; j < reserve.length; j++){
if(lost[i] == reserve[j]){
lost[i] = -1;
reserve[j] = -10;
answer += 1;
}
}
}
//빌려 줄 수 있는 사람 양 옆에 분실 한 사람이 있을 경우 위와 같은 방법으로
//lost 와 reserve 에 음수 값을 넣어 표기
for(int i = 0; i < lost.length; i++){
for(int j = 0; j < reserve.length; j++){
if((reserve[j] == lost[i]-1) || (reserve[j] == lost[i]+1)){
lost[i] = -1;
reserve[j] = -10;
//빌려주면서 운동 가능 한 사람이 한명 증가
answer += 1;
}
}
}
return answer;
}
}//다른 코드
// 모든 인원의 체육복 수를 기록 해 둔 people 배열을 이용해 문제 해결
class Solution {
public int solution(int n, int[] lost, int[] reserve) {
int[] people = new int[n];
int answer = n;
//잃어버린 사람은 "-1"
for (int l : lost)
people[l-1]--;
//여분이 있는 사람은 "1"
for (int r : reserve)
people[r-1]++;
//옆사람에게 빌려준 경우 여분있는 번호는 -1, 부족한 번호는 +1 을 함
for (int i = 0; i < people.length; i++) {
if(people[i] == -1) {
if(i-1>=0 && people[i-1] == 1) {
people[i]++;
people[i-1]--;
}else if(i+1< people.length && people[i+1] == 1) {
people[i]++;
people[i+1]--;
}else
answer--;
}
}
return answer;
}
}- 조이스틱
풀이 방법
- 각 자리 글자는
A -> B 로 올라갈때는 ASCII(목표) - ASCII(A)
A -> Z 로 반대로 갈 때는 ASCII(Z) - ASCII(목표) + 1
- 좌우로 이동 시 A 는 건드릴 필요가 없으므로 A 를 최대한 피해 가는게 좋다.
- 이동 방법은 다음 예시에서
left -> mid -> right 로 가는 방법(K -> D -> A -> A -> F -> I -> A -> A -> E -> A -> K -> L -> S)
left -> right 로 가는 방법(K -> D -> K -> S -> L -> K -> A -> E -> A -> A -> I -> F)
right -> left 로 가는 방법(S -> L -> K -> A -> E -> A -> A -> I -> F -> I -> A -> A -> .....-> L -> S -> K -> D)
- 글자를 바꾸기 위해 소모되는 횟수는 절대적이기 때문에 이동 방법만 최소가 되도록 해주면 해결 가능하다.
//제출 답안
package suhyeongLee.Gready.Joystick;
class Solution {
public int solution(String name) {
int answer = 0;
//가장 일반적인 이동은 좌측에서 우측으로 이동하면서 바꾸는 방법
int move = name.length()-1;
//글자를 처음부터 확인
for(int i = 0; i < name.length(); i++){
// 해당 글자를 만들기 위해 소모되는 조작 횟수
int Goal_ascii = (int)name.toCharArray()[i];
answer += Math.min(Goal_ascii-(int)'A', (int)'Z'-Goal_ascii+1);
//끝에 다다르지 않았으면서 해당 글자가 A 면 돌아갈지 계속 갈지 선택 해야 함
if(i<name.length()-1 && name.toCharArray()[i+1] == 'A'){
int j = i + 1;
while(j<name.length() && name.toCharArray()[j] == 'A'){
j++;
}
move = Math.min(move, Math.min((2*i + name.length()-j), (i + 2*(name.length()-j))) );
}
}
answer += move;
return answer;
}
}//다른 예시
class Solution {
public int solution(String name){
int answer = 0, n = name.length(),
leftOrRight = name.length() - 1;
for(int i = 0; i < n; i++){
int next = i + 1;
char target = name.charAt(i);
//diff : min 을 사용하여 비교하지 않고 기준을 잡아 구분
if(target <= 'N') answer += target - 'A';
else answer += 'Z' - target + 1;
while(next < n && name.charAt(next) == 'A') next++;
//문제 개편전이라 right -> left 에 해당하는 코드 부재
leftOrRight = Math.min(leftOrRight, i + n - next + Math.min(i, n - next));
}
answer += leftOrRight;
return answer;
}
}- 큰 수 만들기
풀이 방법
- 최대한 큰 수가 되기 위해선 앞자리 수가 최대한 커야 한다.
- 그림과 같이 stack 을 이용하여 앞에서 부터 하나씩 stack 에 넣어줌
- 그 후 stack 의 top 이 남은 수의 가장 앞의 수보다 클때까지 pop 을 해줌
- 이 작업을 pop 횟수가 k 번 될때까지 반복
//제출 답안
package suhyeongLee.Gready.Big_number;
import java.util.ArrayDeque;
import java.util.Deque;
class Solution {
public String solution(String number, int k) {
String answer = "";
char[] num_arr = number.toCharArray();
// 마지막에 수를 뽑아내기 편하게 하기 위해서 deque 를 사용함
Deque<Integer> deque = new ArrayDeque<>();
int index = 0, i = 0;
while(i < num_arr.length){
int tmp = Integer.parseInt(Character.toString(num_arr[i]));
if(deque.size()!=0 && tmp>deque.peek() && index<k){
deque.pop();
index += 1;
} else {
deque.push(tmp);
i += 1;
}
}
while(deque.size() > num_arr.length-k){
deque.pop();
}
int size = deque.size();
for(int j = 0; j < size; j++){
answer += deque.pollLast().toString();
}
return answer;
}
}
// 다른 예제
//모든 수를 훑어 가면서 i 번째 수가 i+1 번째 수보다 작으면 그 수를 제거하는 방식
//맨처음 떠올린 방법이지만 java 에서 String 은 원하는 위치의 글자를 제거할 수 없어서 포기
//StringBuilder 를 사용하면 해결 가능
class Solution {
public String solution(String number, int k) {
StringBuilder sb = new StringBuilder(number);
for (int i = 0; i+1 < sb.length() && k>0; i++) {
if(sb.charAt(i) < sb.charAt(i+1)) {
sb.deleteCharAt(i);
i=-1;
k--;
}
}
if(k!=0)
sb.delete(sb.length()-k, sb.length());
return sb.toString();
}
}- 구명 보트
풀이 방법
- 무게 순으로 정렬 후 가장 무거운 사람과 가장 가벼운 사람을 조합하여 구출
- 조합 시 둘다 탑승이 불가한 경우 무거운 사람만 먼저 탑승
- 탑승 후 가벼운 사람과 무거운 사람 index 를 변경하며 문제 해결
// 제출 답안
package suhyeongLee.Gready.Lifeboat;
import java.util.Arrays;
class Solution {
public int solution(int[] people, int limit) {
int answer = 0;
Arrays.sort(people);
int min_index = 0;
int max_index = people.length-1;
while(min_index <= max_index){
if(people[min_index]+people[max_index] > limit){
max_index -= 1;
} else {
min_index += 1;
max_index -= 1;
}
answer += 1;
}
return answer;
}
}// 다른 예시
// 알고리즘은 동일 하지만 더 짧게 작성
import java.util.Arrays;
class Solution {
public int solution(int[] people, int limit) {
Arrays.sort(people);
int i = 0, j = people.length - 1;
for (; i < j; --j) {
if (people[i] + people[j] <= limit)
++i;
}
return people.length - i;
}
}- 섬 연결하기
union-find 알고리즘
- 합집합을 만들고 같은 집합에 속해 있는지 찾아 낼 수 있는 알고리즘
- 우선 각 원소는 자기 자신을 부모 값으로 가진다.
- 만약 "a" 와 "b" 를 union 할 경우 두 원소가 연결 되며 같은 부모를 가지게 된다
- 만약 따라서 b 의 부모가 a 가 된다.
- 같은 방법으로 "c" 와 "b"를 union 하게 되면 "c" 의 부모는 "b"가 된다.
- 이때 "c"의 부모인 "b" 의 부모가 "a" 이기 때문에 "c"의 부모를 "a" 로 수정한다.
- 여기 까지 진행하고 union 을 마친다고 가정하면 부모가 같은 "a, b, c" 는 같은 집합안에 속하지만 부모가 다른 "d"는 집합이 다르다는걸 알 수 있다.
// find 함수
public static int find(int a) {
if(parent[a] == a)
return a;
else
return parent[a] = find(parent[a]);
}
// union 함수
public static void union(int a, int b) {
a = find(a);
b = find(b);
if(a != b)
parent[b] = a;
}
풀이 방법
- union-find 알고리즘을 사용
- 입력 데이터인 costs 를 비용 순으로 오름차순 정렬
이를 통해 costs 를 앞에서 부터 union 해도 비용 발생이 최소화 가늘
- 다음 그림과 같이 시작노드(costs[i][0]) 와 도착 노드(costs[i][1]) 의 부모가 같은지 판별(union 에 해당)
1. 만약 같다면 해당 node 는 연결 되었기 때문에 그냥 넘어감(continue;)
2. 같지 않다면 도착 노드의 부모를 시작 노드의 부모로 변경해 줌
3. 2번의 경우에만 새로 다리를 연결 했기 때문에 cost 를 증가
* 이 후에는 모든 원소의 부모가 동일 하기 때문에 별다른 조작을 하지 않음!
// 제출 답안
package suhyeongLee.Gready.Island_Connection;
import java.util.Arrays;
class Solution {
int[] parent;
public int find(int a){
if(parent[a] == a){
return a;
} else {
return parent[a] = find(parent[a]);
}
}
public int solution(int n, int[][] costs) {
int answer = 0;
parent = new int[n];
for(int i = 0; i < parent.length; i++){
parent[i] = i;
}
Arrays.sort(costs, (int[] c1, int[] c2) -> c1[2]-c2[2]);
for (int i = 0; i < costs.length; i++){
int from_node = costs[i][0];
int to_node = costs[i][1];
int cost = costs[i][2];
int from_parent = find(from_node);
int to_parent = find(to_node);
if(from_parent != to_parent){
parent[to_parent] = from_parent;
} else {
continue;
}
answer += cost;
}
return answer;
}
}- 단속 카메라
풀이 방법
- 입력 데이터 중 routes 배열을 자동차가 나가는 지점(routes[1]) 을 기준으로 오름차순
* 카메라를 최대한 적게 두기 위해선 자동차 이동 지점이 최대한 겹치는 위치에 설치
* 위 조건을 만족 하기 위해선 한 자동차의 이동 지점 가운데가 아닌 최대한 시작 점이나 끝점에 설치 하는것이 유리
* 정렬을 후 나가는 지점 을 기반으로 카메라를 설치 한다면 위 조건 만족 가능
- 다음 그림 처럼 순차 적으로 routes 배열을 탐색 하며 카메라를 설치
* ex) 1번 차량이 나가는 지점인 -15번에 카메라를 설치 하게 되면 2번 카메라도 감시 가능하기 때문에 2번 차량이 나가는 지점인 -13 에는 카메라를 설치 하지 x
* ex) 같은 방법으로 3번 차량이 나가는 지점인 -5번 위치에도 카메라를 설치 하게 되면 4번 카메라도 감시가 가능 하기 때문에 -3 에는 카메라 설치 x
* 따라서 카메라 2개
//제출 답안
// 처음엔 반대로 시작지점을 기준으로 정렬 한 후 나가는 지점에 카메라를 설치 하는 방법을
// 생각 했는데
// [[-200, -100], [-190, -180], [-170, -160], ...] 처럼 시작 지점이 가장 작은 차량이
// 나머지를 품는고 있는 구조에서 해결 불가능
package suhyeongLee.Gready.Intermittent_camera;
import java.util.Arrays;
class Solution {
public int solution(int[][] routes) {
int answer = 0;
Arrays.sort(routes, (int[]c1, int[]c2) -> c1[1]-c2[1]);
int cam_pos = -30000;
for(int i = 0; i < routes.length; i++){
if(cam_pos >= routes[i][0]) continue;
cam_pos = routes[i][1];
answer += 1;
}
return answer;
}
}