그리디 알고리즘 2 (예시 문제 3, 4)

그리디 알고리즘 2

예시문제 3

• 각 자리가 숫자(0부터 9)로만 이루어진 문자열 S가 주어졌을 때, 왼쪽부터 오른쪽으로 하나씩 모든 숫자를 확인하며 숫자 사이에 'x' 혹은 '+' 연산자를 넣어 결과적으로 만들어질 수 있는 가장 큰 수를 구하는 프로그램을 작성하세요. 단, +보다 x를 먼저 계산하는 일반적인 방식과는 달리, 모든 연산은 왼쪽에서부터 순서대로 이루어진다고 가정합니다.

• 예를 들어 02984라는 문자열로 만들 수 있는 가장 큰 수는 ((((0 + 2) x 9) x 8) x 4) = 576입니다. 또한 만들어질 수 있는 가장 큰 수는 항상 20억 이하의 정수가 되도록 입력이 주어집니다.

해결방법

• 덧셈보다는 곱하기가 수를 더 크게 만든다.
• 하지만 두 수 중 하나라도 0이나 1일경우 곱하는것보다 더하기를 수행하는것이 더 효율적이다.
• 따라서 두수에 대한 연산을 할 때, 두 수 중에서 하나라도 1이하인 경우에는 덧셈, 두수가 모두 2 이상인 경우에는 곱하면 정답이다.

코드

Scanner sc = new Scanner(System.in);
String str = sc.next();

//0의 아스키코드는 10진수 48이다.
long result = str.charAt(0) - '0';

for(int i = 1; i < str.length(); i++) {
    int num = str.charAt(i) - '0';
    if(num <= 1 || result <= 1) {
        result += num;
    } else {
        result *= num;
    }
}
System.out.println(result);

예시문제 4

• 한 마을에 모험가가 N명 있습니다. 모험가 길드에서는 N명의 모험가를 대상으로 '공포도'를 측정했는데, '공포도'가 높은 모험가는 쉽게 공포를 느껴 위험 상황에서 제대로 대처할 능력이 떨어집니다.

• 모험가 길드장인 동빈이는 모험가 그룹을 안전하게 구성하고자 공포도가 X인 모험가는 반드시 X명 이상으로 구성한 모험가 그룹에 참여해야 여행을 떠날 수 있도록 규정했습니다.

• 동빈이는 최대 몇 개의 모험가 그룹을 만들 수 있는지 궁금합니다. N명의 모험가에 대한 정보가 주어졌을때, 여행을 떠날 수 있는 그룹 수의 최댓값을 구하는 프로그램을 작성하세요.

해결방법

• 모험가의 공포도를 오름차순으로 정렬하여 풀어보자.

• 예를 들어, 공포도가 각각 1, 1, 2, 2, 3인 모험가 5명이 있다고 가정했을때, 공포도가 1인 모험가는 혼자서도 그룹을 꾸릴수 있다. 공포도가 1인 모험가가 두명이 있으니 이미 그룹을 두개 만들수 있다. 그리고 공포도가 2인 모험가는 반드시 2명이상으로 구성 해야한다. 공포도가 2인 모험가가 2명이 있으니 이 두명은 한그룹이 돼서 지금까지 총 3그룹이고, 공포도가 3인 모험가는 최소 3명 이상이 그룹을 구성해야 되기때문에 그룹을 구성 하지못하고 버려진다. 이로서 총 3그룹이 구성될 수 있다.

입력 예시

5
2 3 1 2 2

출력 예시

2

코드

Scanner sc = new Scanner(System.in);

int count = 0; //현재 그룹에 포함된 모험가의 수
int result = 0; //총 그룹의 수
int n = sc.nextInt();   //모험가 수 입력
ArrayList<Integer> arrayList = new ArrayList<>();

for(int i = 0; i < n; i++) {
    arrayList.add(sc.nextInt());    //모험가 수에 따른 각 공포도 입력
}
Collections.sort(arrayList);    //오름차순 정렬

for(int i = 0; i < n; i++) {
    count += 1;     //현재 그룹에 해당 모험가를 포함시키기
    if(count >= arrayList.get(i)) {
        result += 1;    // 총 그룹의 수 증가시키기
        count = 0;  //현재 그룹에 포함된 모험가의 수 초기화
    }
}
System.out.println(result);