Algorithm - Greedy

Greedy

• 현재 상황에서 지금 당장 좋은 것만 고르는 방법.
• 현재 상황에서 가장 좋아보이는 것만을 선택해도 문제를 풀 수 있는지를 파악해야함.
• '가장 큰 순서대로', '가장 작은 순서대로'와 같은 키워드가 있는지 살펴볼 것.
• 정렬 알고리즘과 짝을 이뤄 자주 출제됨.

예제(from LeetCode)

Longest Palindrome

입력받은 문자열로 만들 수 있는 가장 긴 회문(앞에서 읽어도 뒤에서 읽어도 같은 문장)의 길이를 구하는 문제.

예제 : 'aaccbbb'
1. 문자열의 문자별 갯수를 구한다. {a:2, c:2, b:3}
2. 각 문자별로 짝수개 만큼을 count에 더한다. 6개 'acbbca'
3. 문자 갯수가 홀수개인데 현재 count가 짝수라면 1을 더한다. 'acbbbca'

3번이 포인트. 홀수라도 현재 상태가 짝수 회문이라면 가운데 하나를 넣을 수 있다.

  int longestPalindrome(String s) {
    final Map<String, int> countMap = {};
    int answer = 0;
    s.split("").forEach((element) {
      if (countMap[element] == null) {
        countMap[element] = 1;
      } else {
        countMap[element] = countMap[element]! + 1;
      }
    });

    countMap.keys.forEach((element) {
      final value = countMap[element];

      if (value == null) return;

      answer = answer + ((value ~/ 2) * 2);
      if (answer % 2 == 0 && value % 2 == 1) {
        answer = answer + 1;
      }
    });
    return answer;
  }

Assign Cookies

아이들의 배고픔 정도와 쿠키의 크기를 가지고 가장 많은 아이를 배부르게 하는 방법을 찾는 문제.

• 배고픔 정도보다 작은 쿠키를 줄 수 없다

1. 아이들과 쿠키들을 정렬한다.
2. 가작 적게 배고픈 아이의 배고픔 보다 가장 큰 쿠키가 작거나 쿠키가 없다면 0을 리턴 (edge case)
3. 아이들을 역순으로(가장 배고픈 아이부터) 순환한다.
4. 아이의 배고픔이 현재 가장 큰 쿠키의 크기보다 크거나 쿠키가 없다면 더 이상 순환을 진행하지 않는다. (edge case)
5. 아이의 배고픔이 가장 큰 쿠키로 채워진다면 쿠키를 준다.

    function findContentChildren(g: number[], s: number[]): number {
      let count = 0;
      let index = s.length - 1;
      const ss = s.sort((a, b) => a - b);
      const gg = g.sort((a, b) => b - a);

      if (gg[gg.length - 1] > ss[index] || index < 0) return count;

      gg.forEach((element) => {
        if (index < 0 || gg[gg.length - 1] > ss[index]) return;

        if (element <= ss[index]) {
          count += 1;
          index -= 1;
        }
      });

      return count;
    }

Array Partition I

짝수 배열을 받아 최대 갯수의 pair를 만들 때 각 pair의 min 값의 합이 가장 큰 경우에 해당하는 값을 찾는 문제.

• 큰 숫자들끼리 min 연산을 해야 큰 값을 얻을 수 있다.

1. 배열을 내림차순으로 정렬
2. 앞에서부터 순서대로 두개씩 짝을 지어 min을 구하고 합산.

    function arrayPairSum(nums: number[]): number {
      const sortedNums = nums.sort((a, b) => a - b);
      let answer = 0;
      sortedNums.forEach((value, index) => {
        if (index % 2 == 0) {
          answer = answer + Math.min(value, sortedNums[index + 1]);
        }
      });

      return answer;
    }