Part of your World

문제 설명

코니는 매일 다른 옷을 조합하여 입는것을 좋아합니다.

예를 들어 코니가 가진 옷이 아래와 같고, 오늘 코니가 동그란 안경, 긴 코트, 파란색 티셔츠를 입었다면 다음날은 청바지를 추가로 입거나 동그란 안경 대신 검정 선글라스를 착용하거나 해야합니다.

종류 이름

• 코니는 각 종류별로 최대 1가지 의상만 착용할 수 있습니다. 예를 들어 위 예시의 경우 동그란 안경과 검정 선글라스를 동시에 착용할 수는 없습니다.
• 착용한 의상의 일부가 겹치더라도, 다른 의상이 겹치지 않거나, 혹은 의상을 추가로 더 착용한 경우에는 서로 다른 방법으로 옷을 착용한 것으로 계산합니다.
• 코니는 하루에 최소 한 개의 의상은 입습니다.

코니가 가진 의상들이 담긴 2차원 배열 clothes가 주어질 때 서로 다른 옷의 조합의 수를 return 하도록 solution 함수를 작성해주세요.

제한사항

• clothes의 각 행은 [의상의 이름, 의상의 종류]로 이루어져 있습니다.
• 코니가 가진 의상의 수는 1개 이상 30개 이하입니다.
• 같은 이름을 가진 의상은 존재하지 않습니다.
• clothes의 모든 원소는 문자열로 이루어져 있습니다.
• 모든 문자열의 길이는 1 이상 20 이하인 자연수이고 알파벳 소문자 또는 '_' 로만 이루어져 있습니다.

입출력 예

clothes return

입출력 예 설명

예제 #1

headgear에 해당하는 의상이 yellow_hat, green_turban이고 eyewear에 해당하는 의상이 blue_sunglasses이므로 아래와 같이 5개의 조합이 가능합니다.

1. yellow_hat 2. blue_sunglasses 3. green_turban 4. yellow_hat + blue_sunglasses 5. green_turban + blue_sunglasses

예제 #2

face에 해당하는 의상이 crow_mask, blue_sunglasses, smoky_makeup이므로 아래와 같이 3개의 조합이 가능합니다.

1. crow_mask 2. blue_sunglasses 3. smoky_makeup

package LV2;

import java.util.HashMap;
import java.util.Map;

public class H42578 {
	public static void main(String[] args) {
		// 테스트 케이스 정의
		String[][] clothes1 = {{"yellow_hat", "headgear"}, {"blue_sunglasses", "eyewear"}, {"green_turban", "headgear"}};
		String[][] clothes2 = {{"crow_mask", "face"}, {"blue_sunglasses", "face"}, {"smoky_makeup", "face"}};

		// 테스트 케이스 실행 및 결과 출력
		System.out.println(solution(clothes1)); // 출력: 5
		System.out.println(solution(clothes2)); // 출력: 3
	}

	public static int solution(String[][] clothes) {
		// HashMap 객체 생성 (의상의 종류를 키로, 해당 종류의 의상 개수를 값으로 저장)
		Map<String, Integer> clothesMap = new HashMap<>();

		// clothes 배열을 순회하면서 의상의 종류별 개수를 HashMap에 저장
		for (String[] cloth : clothes) {
			clothesMap.put(cloth[1], clothesMap.getOrDefault(cloth[1], 0) + 1);
		}

		// 모든 경우의 수를 저장할 변수 초기화 (1로 초기화하는 이유는 아래 곱셈 연산 때문)
		int answer = 1;

		// HashMap을 순회하면서 각 종류별 경우의 수를 모두 곱함
		for (int val : clothesMap.values()) {
			answer *= (val + 1); // 해당 종류의 의상을 입지 않는 경우를 고려하여 +1을 함
		}

		// 옷을 하나도 입지 않는 경우를 제외하고 반환
		return answer - 1;
	}
}

HashMap을 사용하여 각 의상의 종류를 키로하고 그 종류의 의상 개수를 값으로 저장할 수 있다.
이렇게 하면, 각 의상의 종류별로 착용하지 않거나, 1개를 착용하는 경우의 수를 계산할 수 있다. 모든 경우의 수를 구하려면 각 의상 종류별 경우의 수를 모두 곱한 후, 1을 빼준다.
이때 1을 빼는 이유는 최소 한 개의 의상은 입어야 하므로 모든 종류의 의상을 착용하지 않는 경우는 제외해야 하기 때문이다.

문제 설명

무인도에 갇힌 사람들을 구명보트를 이용하여 구출하려고 합니다. 구명보트는 작아서 한 번에 최대 2명씩 밖에 탈 수 없고, 무게 제한도 있습니다.

예를 들어, 사람들의 몸무게가 [70kg, 50kg, 80kg, 50kg]이고 구명보트의 무게 제한이 100kg이라면 2번째 사람과 4번째 사람은 같이 탈 수 있지만 1번째 사람과 3번째 사람의 무게의 합은 150kg이므로 구명보트의 무게 제한을 초과하여 같이 탈 수 없습니다.

구명보트를 최대한 적게 사용하여 모든 사람을 구출하려고 합니다.

사람들의 몸무게를 담은 배열 people과 구명보트의 무게 제한 limit가 매개변수로 주어질 때, 모든 사람을 구출하기 위해 필요한 구명보트 개수의 최솟값을 return 하도록 solution 함수를 작성해주세요.

제한사항

• 무인도에 갇힌 사람은 1명 이상 50,000명 이하입니다.
• 각 사람의 몸무게는 40kg 이상 240kg 이하입니다.
• 구명보트의 무게 제한은 40kg 이상 240kg 이하입니다.
• 구명보트의 무게 제한은 항상 사람들의 몸무게 중 최댓값보다 크게 주어지므로 사람들을 구출할 수 없는 경우는 없습니다.

입출력 예

people limit return

package LV2;

import java.util.Arrays;

public class H42885 {
	public static void main(String[] args) {
		int[] people1 = {70, 50, 80, 50};
		int limit1 = 100;
		int[] people2 = {70, 80, 50};
		int limit2 = 100;

		System.out.println(solution(people1, limit1)); // 출력: 3
		System.out.println(solution(people2, limit2)); // 출력: 3
	}

	public static int solution(int[] people, int limit) {
		Arrays.sort(people); // 사람들의 몸무게를 오름차순으로 정렬

		int i = 0, j = people.length - 1; // i는 가장 가벼운 사람을, j는 가장 무거운 사람을 가리킴
		int answer = 0; // 필요한 구명보트의 최소 개수

		while(i <= j) { // 구출해야 할 사람이 더 있는 동안 반복
			answer++; // 구명보트 1개 추가

			if (people[i] + people[j] <= limit) // 가장 가벼운 사람과 가장 무거운 사람이 함께 탈 수 있으면
				i++; // 가장 가벼운 사람을 구출 완료로 표시

			j--; // 가장 무거운 사람을 구출 완료로 표시
		}

		return answer; // 필요한 구명보트의 최소 개수 반환
	}
}

탐욕법은 문제 해결의 각 단계에서 지금 당장 가장 좋은 선택을 하는 것을 기반으로 하는 알고리즘 디자인 패러다임이다.
이러한 선택은 그 순간에는 최적이지만 전체적인 해결책에 대해 최적이라는 보장은 없다.

people 배열을 오름차순으로 정렬한 후, 가장 가벼운 사람(i)과 가장 무거운 사람(j)를 가리키는 인덱스를 사용한다.
이 두 사람이 함께 보트에 탈 수 있는지 확인한 후, 그들을 보트에 태우거나(즉, i를 증가시키거나) 무거운 사람만 보트에 태운다(즉, j를 감소시킨다). 이 과정은 더 이상 구출해야 할 사람이 없을 때까지(즉, i가 j를 초과할 때까지) 계속된다.

결과적으로 **answer**는 필요한 최소한의 구명보트의 개수를 나타낸다.

문제 설명

H-Index는 과학자의 생산성과 영향력을 나타내는 지표입니다. 어느 과학자의 H-Index를 나타내는 값인 h를 구하려고 합니다. 위키백과1에 따르면, H-Index는 다음과 같이 구합니다.

어떤 과학자가 발표한 논문 n편 중, h번 이상 인용된 논문이 h편 이상이고 나머지 논문이 h번 이하 인용되었다면 h의 최댓값이 이 과학자의 H-Index입니다.

어떤 과학자가 발표한 논문의 인용 횟수를 담은 배열 citations가 매개변수로 주어질 때, 이 과학자의 H-Index를 return 하도록 solution 함수를 작성해주세요.

제한사항

• 과학자가 발표한 논문의 수는 1편 이상 1,000편 이하입니다.
• 논문별 인용 횟수는 0회 이상 10,000회 이하입니다.

입출력 예

citations return

입출력 예 설명

이 과학자가 발표한 논문의 수는 5편이고, 그중 3편의 논문은 3회 이상 인용되었습니다. 그리고 나머지 2편의 논문은 3회 이하 인용되었기 때문에 이 과학자의 H-Index는 3입니다.

package LV2;

import java.util.Arrays;

public class H42747 {
	public int solution(int[] citations) {
		Arrays.sort(citations);  // 인용 횟수를 오름차순으로 정렬

		int max = 0;  // H-Index를 저장할 변수를 초기화
		for (int i = 0; i < citations.length; i++) {  // 각 인용 횟수에 대해 반복
			// 현재 인용 횟수와 남은 논문 수 중 작은 값이 H-Index의 후보가 된다.
			int min = Math.min(citations[i], citations.length - i);
			if (max < min) max = min;  // 후보가 현재 H-Index보다 크면 값을 갱신
		}

		return max;  // 계산된 H-Index를 반환
	}
}