프로그래머스 구명보트, 조이스틱

오래간만에 프로그래머스에서 문제를 풀었다.

아직도 감을 잘 못 잡고 있는(...) 그리디 문제 2문제 풀어본 내용 정리. 

그리디가 시중에 판매되는 알고리즘 책들 보면 꽤 앞쪽에 나와있는데... 난 그리디를 왜이렇게 못하는...?

 

---

구명보트 

https://school.programmers.co.kr/learn/courses/30/lessons/42885

프로그래머스

- 여기서 아무 생각이 없이 풀다가 놓쳤는데, 무조건 보트엔 2명밖에 못 탄다. 그러므로 가장 무거운 사람 + 가장 가벼운 사람 조합으로 가야 한다...이걸 생각 못함; 

- 따라서, 그냥 사람들 무게 배열을 정렬하고, left(가벼운 사람) - right(무거운 사람) 설정해서 투포인터 알고리즘처럼 풀면된다. 

import java.util.*;
class Solution {
    public int solution(int[] people, int limit) {
        Arrays.sort(people);
        int answer = 0;
        int left = 0;
        int right = people.length - 1;
        
        while (left <= right) {
            if (people[left] + people[right] <= limit) {
                left++;
            } 
            answer++;
            right--;
        }
        
        return answer;
    }
}

 

---

 

조이스틱 

https://school.programmers.co.kr/learn/courses/30/lessons/42860

프로그래머스

솔직히 이 문제는 ... 그리디로 분류되어 있는데..테스트 케이스가 추가되면서 좀 더 복잡해진 느낌이다..

살짝 당황스러웠다.... 그리고 머리가 돌아가지 않았다... 

 

이 조이스틱 문제가 level2인가 그랬는데 어려워서 구글링했다.

https://velog.io/@jeeseob5761/프로그래머스-조이스틱

이 분의 블로그를 참고해서 해결 방안을 찾았다.

 

알파벳을 전환하는 것을 계산하는건 어렵지 않다. 

이 문제에서는 좌우 이동하는 횟수를 줄이는게 관건이기 때문이다. 

따라서 좌우 이동 + 상하 이동(알파벳을 전환하는거) 이렇게 따로 구분해서 계산을 했는데, 이 좌우 이동 계산하는 경우가 이렇다

- BBBAAAB 이런 경우처럼 오른쪽으로 쭉 가다가 꺾는게 더 빠른 경우도 있을 수 있다.

- AAAAABB 이런 경우처럼 걍 처음부터 왼쪽으로 꺾어서 가는게 더 빠른 경우도 있을 수 있다. 

- BCBCBC처럼 그냥 오른쪽으로 쭉 가는게 최적인 경우도 있다. (A가 하나도 없다거나)

이 3가지 중 최소한의 움직임이 무엇인지 다 계산해줘야한다. 아마 2022년 1월쯤에 테스트 케이스 추가되면서 더 복잡해진 것 같다.

 

 

아무튼 코드는 그래서 간단한데, horizon(좌우 이동횟수) 이거 계산하는 방식을 생각하기 .. 어려웠다. ㅡㅡ

class Solution {
    public int solution(String name) {
        int answer = 0;
        int horizon = name.length() - 1; // 좌우 이동
        int end = 0;
        
        char[] names = name.toCharArray();
        for (int i = 0; i < name.length(); i++) {
            // 각 알파벳 바꾸는 개수 세는 로직
            answer += Math.min(names[i] - 'A', 26 - (names[i] - 'A'));
    
            end = i + 1;
            while (end < name.length() && names[end] == 'A') {
                end++;
            }       
            
            
            // 오른쪽으로 쭉 가다가 꺾기 vs 오른쪽 쭉 가기 (원래의 horizontal 값)
            horizon = Math.min(horizon, i * 2 + name.length() - end);
            // 아묻따 바로 왼쪽으로 꺾는 경우 
            horizon = Math.min(horizon, (name.length() - end) * 2 + i);
        }
        
        return answer + horizon;
    }
}