Cos Pro 1급 - 샘플 문제 5차 5번 - 이길 수 있는 몬스터의 최대수

문제 지문 #5

XX게임에선 캐릭터는 자신과 공격력이 같거나 자신보다 공격력이 작은 몬스터에게 이깁니다. 내가 가진 캐릭터가 최대 몬스터 몇 마리를 이길 수 있는지 구하려 합니다. 단, 한 캐릭터는 한 번만 싸울 수 있습니다.

예를 들어, 세 몬스터의 공격력이 각각 [1, 4, 3]이고, 내가 가진 두 캐릭터의 공격력이 각각 [1, 3]이라면 첫 번째 캐릭터는 첫 번째 몬스터와, 두 번째 캐릭터는 세 번째 몬스터와 싸워서 이길 수 있습니다. 따라서 이길 수 있는 몬스터 수는 최대 2마리입니다.

모든 몬스터의 공격력을 담은 배열 enemies, 내가 가진 모든 캐릭터의 공격력을 담은 배열 armies가 매개변수로 주어질 때, 내 캐릭터로는 최대 몬스터 몇 마리를 이길 수 있는지 return 하도록 solution 메서드를 작성해주세요.

---

매개변수 설명

모든 몬스터의 공격력을 담은 배열 enemies, 내가 가진 모든 캐릭터의 공격력을 담은 배열 armies가 solution 메서드의 매개변수로 주어집니다.

• 몬스터 수는 1마리 이상, 500마리 이하입니다.
• 각 몬스터의 공격력은 1 이상 100 이하입니다.
• 내가 가진 캐릭터 수는 1개 이상 500개 이하입니다.
• 각 캐릭터의 공격력은 1 이상 100 이하입니다.

---

return 값 설명

내가 가진 캐릭터로는 최대 몬스터 몇 마리를 이길 수 있는지 return 해주세요.

---

입출력 예

enemies	armies	return
[1, 4, 3]	[1, 3]	2
[1, 1, 1]	[1, 2, 3, 4]	3

입출력 예 설명

입출력 예 #1
문제에 나온 예와 같습니다.

입출력 예 #2
캐릭터를 어떻게 보내도 모든 몬스터를 이길 수 있습니다.

728x90

 

혼자 풀이

전체 코드를 작성하는 문제입니다. armies와 enemies 배열을 받아서 armies가 enemies를 최대 몇 마리까지 이길 수 있는지 찾는 문제입니다. 

최대 이길 수 있는 수를 구하려면, armies의 각 캐릭터의 공격력과 enemies 캐릭터의 공격력 차이가 적게 효율적으로 이겨야 한다고 생각했습니다. 그래서 armies는 오름차순으로 enemies는 내림차순으로 정렬하여 armies의 공격력이 가장 작은 캐릭터가 이길 수 있는 가장 큰 enemies 캐릭터를 for문으로 순환하면서 찾았습니다.

Arrays.sort()의 내림차순은 기본 타입인 int에 대해서는 정렬이 안되므로 wrapper 클래스인 Integer로 변경했습니다.

// 다음과 같이 import를 사용할 수 있습니다.
import java.util.*;

class Main {
    public int solution(int[] enemies, int[] armies) {
        // 여기에 코드를 작성해주세요.
        int answer = 0;
        Integer[] enemiesInteger = new Integer[enemies.length];
        
        //enemies 배열을 내림차순 정렬하기 위해 wrapper class로 변경합니다
        for(int i=0;i<enemies.length;i++){
        	enemiesInteger[i]=enemies[i];
        }
        
        //enemies는 내림차순, armies는 오름차순 정렬합니다
        Arrays.sort(enemiesInteger,Collections.reverseOrder());
        Arrays.sort(armies);
        
        //armies의 가장 약한 캐릭터로 이길수있는 가장 강한 캐릭터를 찾아서
        //answer를 증가시키고, 해당 enemies 캐릭터는 0으로 처리함
        for(int i=0;i<armies.length;i++){
            for(int j=0;i<enemiesInteger.length;j++){
                if(enemiesInteger[j]>0){
                    if(armies[i]>=enemiesInteger[j]){
                        answer++;
                        enemiesInteger[j]=0;
                        break;
                    }
                }
            }
        }
			
        return answer;
    }

    // 아래는 테스트케이스 출력을 해보기 위한 main 메소드입니다.
    public static void main(String[] args) {
    	Main sol = new Main();
    	int[] enemies1 = {1, 4, 3};
    	int[] armies1 = {1, 3};
    	int ret1 = sol.solution(enemies1, armies1);

    	// [실행] 버튼을 누르면 출력 값을 볼 수 있습니다.
    	System.out.println("solution 메소드의 반환 값은 " + ret1 + " 입니다.");

    	int[] enemies2 = {1, 1, 1};
    	int[] armies2 = {1, 2, 3, 4};
    	int ret2 = sol.solution(enemies2, armies2);

    	// [실행] 버튼을 누르면 출력 값을 볼 수 있습니다.
    	System.out.println("solution 메소드의 반환 값은 " + ret2 + " 입니다.");
    }
}

 

정답

정답에서는 두 배열을 모두 오름차순 정렬하여 순차 비교했는데요. 생각해보니, 내림차순으로 만들어서 비교하나, 오름차순으로 만들어서 비교하나, armies가 이길 수 있는 enemies의 캐릭터가 달라지더라도, enemies의 가장 약한 캐릭터를 이길 수 있는 가장 약한 armies 캐릭터를 찾으면 이기는 횟수 자체에는 변경이 없었습니다. 

class Solution {
    public int solution(int[] enemies, int[] armies) {
        int answer = 0;
        
        Arrays.sort(enemies);
        Arrays.sort(armies);
        int i = 0, j = 0;
        while(i < enemies.length && j < armies.length) {
        	if(enemies[i] <= armies[j]) {
        		answer++;
        		i++;
        		j++;
        	} else {
        		j++;
        	}
        }
        
        return answer;
    }
}

 

실습은 아래 참고

2022.10.25 - [Programming/Cos Pro 1급] - Cos Pro 1급 공부 사이트 추천 - 구름 에듀(https://edu.goorm.io/)

Cos Pro 1급 공부 사이트 추천 - 구름에듀(https://edu.goorm.io/)