처음
그리디와 관련된 백준 연습 문제를 추가적으로 풀어봤다.
중간
1. 백준 11399 - ATM
i번째 사람에게 필요한 시간 p에 대해서, (n-(i+1))*p만큼 총 시간이 늘어나기 때문에, p가 작은 순서대로 ATM기를 사용해야한다.
public class BOJ11399 {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
StringTokenizer st = new StringTokenizer(br.readLine());
Queue<Integer> queue = new PriorityQueue<>();
for (int i = 0; i < n; i++) {
queue.offer(Integer.parseInt(st.nextToken()));
}
int tmp = queue.poll();
int result = tmp;
while (!queue.isEmpty()) {
result += tmp += queue.poll();
}
System.out.println(result);
}
}
우선순위 큐로 자동으로 오름차순으로 정렬한 뒤, 각 사람이 기다리는 시간을 result에 모두 더해 반환했다.
아주 기본적인 그리디 문제였다.
2. 백준 2457 - 공주님의 정원
그리디를 활용한 알고리즘을 생각해내는 것은 그렇게 어렵지 않았지만, 예외 경우를 처리하는 데 애를 많이 먹었다. 전반적인 알고리즘은 다음과 같다.
- (start, end)쌍을 start 오름차순으로 검사한다.
- 현재까지 선택한 꽃의 end 날짜와 검사하는 꽃의 start 날짜를 비교한다.
2-1. start 날짜가 더 크다면 현재까지 뽑은 꽃 중에서 end가 최대인 꽃을 선택한다. (start가 더 크면 꽃이 피지 않는 기간이 생기는 것이므로)
2-2. 그렇지 않다면 검사한 꽃들의 end날짜와 비교해서 더 크다면 최대 end날짜를 갱신한다.
package greedy;
class Flower2 implements Comparable<Flower2> {
int start;
int end;
public Flower2(int start, int end) {
this.start = start;
this.end = end;
}
@Override
public int compareTo(Flower2 flower) {
if (this.start == flower.start) return this.end - flower.end;
return this.start - flower.start;
}
@Override
public String toString() {
return "(" + start + ", " + end + ")";
}
}
public class BOJ2457_2 {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
List<Flower2> list = new ArrayList<>();
int start;
int end;
for (int i = 0; i < n; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
String month = st.nextToken();
String day = st.nextToken();
if (day.length() == 1) start = Integer.parseInt(month + "0" + day);
else start = Integer.parseInt(month + day);
month = st.nextToken();
day = st.nextToken();
if (day.length() == 1) end = Integer.parseInt(month + "0" + day);
else end = Integer.parseInt(month + day);
list.add(new Flower2(start, end));
}
Collections.sort(list);
// System.out.println(list);
int tmpEnd = 301;
int tmpMax = 0; //현재 최대 end날짜
int answer = 0;
int idx = 0;
while (idx < list.size()) {
Flower2 flower = list.get(idx);
if (flower.start > tmpEnd) {
if (tmpMax == 0) {
System.out.println(0);
return;
}
// System.out.println(tmpMax + " 사용");
tmpEnd = tmpMax;
tmpMax = 0;
answer++;
continue;
}
tmpMax = tmpMax > flower.end ? tmpMax : flower.end;
if (tmpMax >= 1201) {
tmpEnd = tmpMax;
answer++;
break;
}
idx++;
}
if (tmpEnd < 1201) System.out.println(0);
else System.out.println(answer);
}
}예외로 처리해야하는 경우는, 중간에 연결이 끊기는 기간이 생기는지 확인하는 것, 1201을 넘어가면 꽃을 추가하지않고 종료하는 것 정도가 있었다.
다섯 번 틀리고 나서야 통과했다.
3. 백준 11501 - 주식
덱 (스택)을 활용해서 풀었다. 우선 덱을 다음 과정을 통해 만든다.
- 덱에 (값, 인덱스) 쌍을 순서대로 저장해나간다.
- 값을 넣을 때, deque.peek()이 자신보다 작다면, 삭제하고 다시 반복한다.
- 자신보다 큰 것이 나왔다면, push한다.
위 과정을 통해 주식 수익에 관여하는 중간의 고점들만을 저장할 수 있게 된다. 그리고 나서는 덱에 저장된 고점들의 인덱스를 이용해서 고점의 값과 그 이전의 값들을 뺌으로써 수익을 구할 수 있다.
public class BOJ11501 {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
for (int i = 0; i < n; i++) {
int n2 = Integer.parseInt(br.readLine());
int[] arr = new int[n2];
StringTokenizer st = new StringTokenizer(br.readLine());
Deque<Integer[]> queue = new LinkedList<>(); // [0] : 값, [1] : 인덱스
queue.offer(new Integer[]{arr[0] = Integer.parseInt(st.nextToken()), 0});
for (int j = 1; j < n2; j++) {
int tmp = Integer.parseInt(st.nextToken());
while (!queue.isEmpty()) {
if (queue.peekLast()[0] > tmp) break;
queue.pollLast();
}
queue.offer(new Integer[]{tmp, j});
arr[j] = tmp;
}
long answer = 0;
int prev = 0;
while (!queue.isEmpty()) {
Integer[] tmp = queue.poll();
for (int j = prev; j < tmp[1]; j++) {
if (tmp[0] > arr[j]) {
answer += tmp[0] - arr[j];
}
}
prev = tmp[1] + 1;
}
System.out.println(answer);
}
}
}매우 귀찮게 풀었는데, 사실 그냥 뒤에서부터 검색해가며 풀면 된다. 현재 값보다 크면 max를 갱신하고, 현재 값보다 작으면 answer+=다음 값 해버리면 된다...
4. 백준 1541 - 잃어버린 괄호
+, -로만 이루어진 식을 최소로 만드는 방법은 마이너스하는 값을 최대로 만들면 된다. 그렇다면 뒤에서부터 검샇면서 모든 더하기를 먼저 계산하고, (마이너스 하는 값을 최대로) 마지막에 마이너스를 해주면 되는 것
public class BOJ1541 {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String str = br.readLine();
List<String> list = new ArrayList<>();
StringBuilder sb = new StringBuilder();
for (char chr : str.toCharArray()) {
if (chr == '+' || chr == '-') {
list.add(sb.toString());
list.add(chr + "");
sb = new StringBuilder();
continue;
}
sb.append(chr);
}
list.add(sb.toString());
Stack<Integer> stack = new Stack<>();
int prev = Integer.parseInt(list.get(list.size() - 1));
for (int i = list.size() - 2; i >= 0; i -= 2) {
if (list.get(i).equals("+")) {
prev += Integer.parseInt(list.get(i - 1));
} else {
stack.push(prev);
prev = Integer.parseInt(list.get(i - 1));
}
}
stack.push(prev);
// System.out.println(stack);
int answer = stack.pop();
while (!stack.isEmpty()) {
answer -= stack.pop();
}
System.out.println(answer);
}
}알고리즘보다 문자열 처리하는 게 훨씬 어려운 문제였다. 다시 생각해보면 어차피 +만 먼저 하니까 -를 기준으로 문자열을 쪼갠 다음에 다 더해버리는 방법이 더 편했을 것 같다.
5. 백준 1744 - 수 묶기
수열에 있는 임의의 두 수를 곱한 합을 최대로 만들어야한다. '두 수의 곱의 합'을 최대로 만들기 위해서는 당연히 최대한 큰 수 끼리만 곱하면 된다. 또 이 문제에서 주의할 점은 음수와 0이 존재하기 때문에 음수도 따로 관리해줘야했다.
public class BOJ1744_2 {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
List<Integer> pos = new ArrayList<>();
List<Integer> neg = new ArrayList<>();
for (int i = 0; i < n; i++) {
int tmp = Integer.parseInt(br.readLine());
if (tmp > 0) pos.add(tmp);
else neg.add(tmp);
}
Collections.sort(pos, Collections.reverseOrder());
Collections.sort(neg);
int answer = 0;
for (int i = 0; i < pos.size(); i += 2) {
if (i == pos.size() - 1) {
answer += pos.get(i);
break;
}
if (pos.get(i+1) == 1) {
answer += pos.get(i) + 1;
continue;
}
if (pos.get(i) == 1 && pos.get(i + 1) == 1) {
answer += 2;
continue;
}
answer += pos.get(i) * pos.get(i + 1);
}
//홀수개면 마지막 하나 남음
for (int i = 0; i < neg.size() - 1; i += 2) {
answer += neg.get(i) * neg.get(i + 1);
}
if (neg.size() % 2 != 0) answer += neg.get(neg.size() - 1);
System.out.println(answer);
}
}다음의 예외를 처리해줬다.
- 묶으려는 두 수 중 하나가 1일 때 : 곱하는 것보다 더하는 것이 더 값이 크므로 묶지 않는다.
- 원소의 개수가 홀수개일 땐 묶지 않고 더해준다.
6. 백준 2170 - 선 긋기
위의 공주님의 정원의 간단한 형태의 문제였다.
- 선이 시작되는 위치를 기준으로 오름차순 검사한다.
- 이전 선과 이어지면, tmpEnd 변수를 지금 검사하는 선의 끝나는 지점으로 갱신한다.
2-1. 이어지지 않는다면, answer에 tmpEnd-tmpStart를 하고, tmpEnd와 tmpStart를 현재 선으로 갱신한다.
class Pair implements Comparable<Pair> {
int start;
int end;
public Pair(int start, int end) {
this.start = start;
this.end = end;
}
@Override
public int compareTo(Pair pair) {
if (pair.start == this.start) return this.end - pair.end;
return this.start - pair.start;
}
@Override
public String toString() {
return "(" + start + " to " + end + ")";
}
}
public class BOJ2170 {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
Queue<Pair> queue = new PriorityQueue<>();
for (int i = 0; i < n; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
queue.offer(new Pair(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken())));
}
long answer = 0;
Pair tmp = queue.poll();
int tmpStart = tmp.start;
int tmpEnd = tmp.end;
while (!queue.isEmpty()) {
tmp = queue.poll();
//tmp.end가 tmpEnd보다 더 클때만..
if (tmpEnd >= tmp.start && tmpEnd < tmp.end) tmpEnd = tmp.end;
else if (tmpEnd < tmp.start){
answer += tmpEnd - tmpStart;
tmpStart = tmp.start;
tmpEnd = tmp.end;
}
}
answer += tmpEnd - tmpStart;
System.out.println(answer);
}
}
7. 백준 1700 - 멀티탭 스케줄링
콘센트를 뽑는 경우를 최소로 하기 위해서는, 꽂혀있는 콘센트를 뽑아야하는 상황에서 다음에 사용해야하는 시기가 가장 늦는 제품을 뽑아야 한다. 로직은 다음과 같다.
- 가장 먼저 가전 제품 별로 인덱스를 저장하는 리스트 배열 (List[]의 형태) machines를 선언해서 관리
- 전기용품 순서대로 검사
1-1. 현재 꽂힌 플러그 중에서 검사하는 용품이 있다면, continue
1-2. 현재 멀티탭이 꽉찬 상태가 아니라면, tmpPlugs에 추가하고 continue
1-3. 꽂혀있는 전기용품 중 앞으로 꽂을 일이 없는 것이 있다면 바로 뽑아버림
1-3-1. 그렇지 않다면 다음에 사용해야하는 시기가 가장 늦는 용품을 뽑음
{
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int n = Integer.parseInt(st.nextToken());
int k = Integer.parseInt(st.nextToken());
List<Integer>[] machines = new List[101];
int[] arr = new int[k];
st = new StringTokenizer(br.readLine());
for (int i = 0; i < k; i++) {
int tmp = Integer.parseInt(st.nextToken());
if (machines[tmp] == null) machines[tmp] = new ArrayList<>();
machines[tmp].add(0, i);
arr[i] = tmp;
}
//list로 선언해서...
List<Integer> tmpPlugs = new ArrayList<>();
int answer = 0;
//꽂을 전기용품마다 돌아간다
for (int i = 0; i < k; i++) {
machines[arr[i]].remove(machines[arr[i]].size() - 1);
if (contains(tmpPlugs, arr[i])) continue;
if (tmpPlugs.size() < n) {
tmpPlugs.add(arr[i]);
continue;
}
int willBeUnplug = -1; //뽑을 plug idx
int tmpMax = Integer.MIN_VALUE; //뽑는 순서 중 가장 먼 것
//뽑을 전기용품 찾기
for (int j = 0; j < tmpPlugs.size(); j++) {
List<Integer> tmpList = machines[tmpPlugs.get(j)];
//다시 꽂을 일 없는 거 바로뽑기
if (tmpList.size() == 0) {
willBeUnplug = j;
break;
}
if (tmpMax < tmpList.get(tmpList.size()-1)) {
tmpMax = tmpList.get(tmpList.size()-1);
willBeUnplug = j;
}
}
tmpPlugs.set(willBeUnplug, arr[i]);
answer++;
}
System.out.println(answer);
}
private static boolean contains(List<Integer> arr, int n) {
for (int x : arr) {
if (n == x) return true;
}
return false;
}
}전기 용품을 List[]로 선언한 방식은 수의 범위가 적었기 때문에 가능했다. 가독성이 정말 구린 와중에 이 부분이 코드를 깔끔하게 만드는데 도움이 된 것 같다.
끝
구현력이 부족해서인지 그리디 문제는 디버깅해가면서 예외 상황을 추가하는 횟수가 엄청 많았다. 그래서 코드도 지저분해지고 전체적인 흐름을 파악하기 힘들어 새로 푸는 경우도 있었다. 다른 사람들의 코드를 참고하면서 연습해야할 것 같다.
'이 문제를 그리디로 풀 수 있는 지'를 판단하고 아이디어를 떠올리는 것은 연습을 통해 익숙해질 수 있을 것 같다. 내가 생각해낸 풀이가 문제의 요구사항 중에 cover하지 못하는 경우가 있는지 꼼꼼하게 확인해야 한다.
연습문제 출처 : 바킹독 github
컴퓨터 사이언스, 알고리즘, 모든 애플리케이션에 관심이 있습니다.