[프로그래머스 스쿨] 알고리즘 - 1

그리디 알고리즘

수학적 논리로 풀어야 하는 문제들이었습니다. 전기 요금을 최소로 쓸 수 있는 경우의 수를 모두 구한다거나, 모든 집에 전기를 공급하기 위해 기지국을 어디에 세워야 최소 개수를 세울 수 있는지에 대한 문제 말이죠.

그리디 알고리즘은 모든 경우의 수를 알아봐야 하기 때문에 알고리즘 공식보단 규칙을 찾아 공식화 하고 코드로 나타내는 점이 중요합니다.

따라서 여러 문제를 풀어보고 접근 방식을 정리해야 데이터가 쌓여 비슷한 유형을 풀 수 있을거라 생각됩니다.

정리한 것을 토대로 주기적으로 푼 문제들을 다시 풀어보면 그리디 알고리즘 풀이 능력이 꾸준히 늘 것입니다.

1. 기지국 설치

기지국은 전기를 공급하는 범위인 W를 가집니다. 범위는 기지국이 설치된 인덱스 양 옆 W만큼 전기를 공급합니다. 그리고 기지국이 설치된 배열 인덱스들이 주어집니다. 기지국이 공급할 수 없는 배열 인덱스들에 최소한의 기지국을 설치할 수 있는 경우의 수를 구하면 됩니다.

접근 방식은 기지국이 설치되지 않은 범위일 때 기지국을 설치하고, 전기를 공급할 수 있는 범위만큼 건너뛴 다음 설치 여부를 확인하는 작업을 반복하면 됩니다. 만약 설치된 인덱스라면 다음 인덱스로 넘어갑니다.

전기를 공급할 수 있는 범위는 2 * W + 1이 됩니다. 2를 곱하는 이유는, 기지국을 설치한 양쪽으로 W만큼 전기가 공급되기 때문입니다. 1을 더하는 것은 기지국이 설치된 인덱스도 더해줘야 하기 때문이죠.

이 문제의 포인트는 설치 여부에 따라 설치 되지 않았으면 무조건 기지국을 설치하고, 전기를 공급할 수 있는 범위 를 공식으로 구하는 것이었습니다.

2. 자전거 공장(최소 전기요금으로 자전거 만들기)

시간이 적고 지문의 input 부분을 이해하지 못해 풀지 못했습니다. 적은 전기요금 구간에서 최대한 많은 자전거를 생산해야 합니다. 전기요금 구간별로 낮은 구간부터 차례대로 주문 재고가 0이 될 때까지 주문하면 됩니다.

3. 가장 큰 수 구하기

주어진 숫자 문자 배열을 조합해서 최대 수를 구하면 됩니다. 문자로 정렬하면 되지 않을까란 생각이 먼저 듭니다. 하지만 30, 3이 있을 때 문자 정렬은 30이 크지만, 조합했을때 330이 303보다 크기 때문에 정렬(Comparator) 메서드를 직접 구현하는 것이 포인트 입니다.

따라서 다음 옆의 문자 배열과 조합했을 때 큰 수가 될 수 있도록 정렬하는 식을 Comparator -> compareTo 메서드를 활용해주면 됩니다. (o2 + o1).compareTo(o1 + o2) 처럼 말이죠.

그리고 예외 케이스로 0으로만 이루어진 배열일 수 있기 때문에 정렬했을 때 첫 문자가 "0"인 경우 0을 리턴해주면 됩니다.