99클럽 코테 스터디 26일차 TIL + 그리디 알고리즘

TIL

▶️ 그리디 알고리즘

최적해를 구하는 데에 사용하는 근사적인 방법으로, 여러 경우 중 하나를 결정해야 할 때마다 그 순간에 최적이라고 생각되는 것을 선택해 나가는 방식이다.

▶️ ArrayList 클래스

remove는 두 종류가 있다.

값을 삭제하고 싶은 경우는 Object 객체를 파라미터로 넘겨준다.

▶️ public E remove(int index)
int를 전달할 경우, 해당 index의 값이 삭제된다.

▶️public boolean remove(Object o)
Object 객체를 전달할 경우, 해당 객체를 찾아서 첫 번째로 나오는 값을 삭제한다.
값을 삭제하면 true를 리턴하고, 삭제할 값이 없으면 false를 리턴한다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
import java.util.StringTokenizer;

public class Main {
  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    int N = Integer.parseInt(br.readLine());
    int[] a = new int[N];
    int[] b = new int[N];

    // 초기값
    StringTokenizer st = new StringTokenizer(br.readLine());
    for (int i=0; i<N; i++) {
      a[i] = Integer.parseInt(st.nextToken());
    }
    st = new StringTokenizer(br.readLine());
    for (int i=0; i<N; i++) {
      b[i] = Integer.parseInt(st.nextToken());
    }
    List<Integer> list = new ArrayList<>();
    for (int i=0; i<b.length; i++) {
      list.add(b[i]);
    }

    // 그리디 알고리즘을 위한 a 정렬
    Arrays.sort(a);

    int answer = 0;
    for (int i=0; i<a.length; i++) {
      int max = Collections.max(list); // max 값을 택함
      answer += (a[i] * max);
      // 사용한 max 값은 제거 (remove(Object o))
      list.remove(Integer.valueOf(max)); // Integer.valueOf는 Integer 객체를 반환한다.
    }
    System.out.println(answer);
  }
}

---

백준

1026번: 보물 (JAVA 풀이)

https://www.acmicpc.net/problem/1026

1026번: 보물

99클럽 1기를 수강하면서 작성한 글입니다.

https://99club.oopy.io/

99클럽 스터디원 모집 중