섹션4. Sorting & Thinking - (2)

🎈섹션4. Sorting & Thinking - (2)

🟦 4-3. 카드 가져가기

문제 풀이

첫 시도 코드

1) 먼저 내림차순 정렬 한 뒤에

2) 기본적으로 영희 우선권이므로 (짝수 번째), 철수는 홀수번째 일텐데

3) k번의 철수 우선권이 존재하므로 각 케이스별 차이를 담을 배열을 생성하고

4) 차이가 클 때 철수가 우선권을 사용할 index값을 따로 담고 그 인덱스값의 2배에서 철수가 (짝수 번째) 값을 누적하여 사용할 수 있게 문제 풀이를 시도했다. → 코드가 꼬여서 마무리를 못했다.

import java.util.*;
class Solution {
    public int solution(int[] nums, int k){
        int answer = 0;
        //복붙
        ArrayList<Integer> numsA = new ArrayList<>();
        for(int i=0; i<nums.length; i++) {
            numsA.add(nums[i]);
        }

        //내림차순 정렬
        Collections.sort(numsA, Collections.reverseOrder());

        //두 차이 담을 용도 만들기
        ArrayList<Integer> minus = new ArrayList<>();
        for(int i=0; i<numsA.size()-1; i++) {
            minus.add( numsA.get(i) - numsA.get(i+1)  ); 
        }

        return answer;
    }

    public static void main(String[] args){
        Solution T = new Solution();
        System.out.println(T.solution(new int[]{7, 8, 5, 12, 3, 1, 3, 1, 1, 12}, 2));
        System.out.println(T.solution(new int[]{8, 2, 12, 12, 12, 12, 2, 2}, 2));
        System.out.println(T.solution(new int[]{3, 7, 12, 3, 3, 5, 7, 8, 9, 11, 23, 4, 6, 7}, 3));
        System.out.println(T.solution(new int[]{12, 34, 56, 23, 22, 34, 55, 45, 24, 23, 45, 55, 55, 23, 11, 12, 23, 12}, 3));
        System.out.println(T.solution(new int[]{14, 15, 20, 11, 10, 20, 20, 12, 9, 22, 27, 25, 30, 19}, 3));
    }
}

---

⬛ 내림차순 정렬 (역순 정렬)

• 기본적으로 int[] 기본형에 대해서는 역순 정렬 이 안된다.
• Integer와 같이 클래스 타입이어야 역순 정렬 가능

🏓 1) 기본형 int[] → 클래스형 Integer[] 타입으로 변형하기

Integer[] tmp = Arrays.stream(nums).boxed().toArray(Integer[]::new);

🏓 2) Arrays.sort() 함수 사용하기

(1) Collections.reverseOrder() 사용

Arrays.sort(배열, Collections.reverseOrder() );

(2) Lamda 람다 함수 사용

Arrays.sort(배열, (a, b) -> (b - a) ); //역순 정렬 

완성 코드

• 최초 시도 때는 라운드별 철수가 k번의 우선권 사용할 인덱스 값 얻는 것에 치중했는데 그럴 필요가 없었다.
• (1) 기본적으로 철수가 (영희 우선) 카드 뽑을 때의 누적값을 구해놓고.
• (2) 차이 배열을 내림차순 정렬시켜 앞에서 k번쨰까지의 차이값만 기존의 누적값에 + 더해주면 최대 점수가 구해진다.

package to_0524_1;
import java.util.*;
class Solution {
    //솔루션 함수 
    public int solution(int[] nums, int k){
        int answer = 0;
        int n = nums.length;
        //1) 내림차순 정렬시켜놓고 
        Integer[] tmp = Arrays.stream(nums).boxed().toArray(Integer[]::new);
        Arrays.sort(tmp, Collections.reverseOrder());

        //2) 차이 담을 diff 배열
        Integer[] diff = new Integer[n/2];

        //3) 기본적으로 철수가 가질 홀수번째 값을 누적해놓고, 그 차이도 함께 diff[]배열에 담기  
        for(int i=0; i<n/2; i++) {
            answer += tmp[i*2+1]; //기본적으로 철수가 가질 값
            //그 차이도 계산
            diff[i] = tmp[i*2] - tmp[i*2+1];// 짝수-홀수 차이를 구한다.
        }

        //4) diff도 내림차순 정렬시킴
        Arrays.sort(diff, (a, b)-> b-a);
        //5) k번까지만 앞의 차이 더하면 됨
        for(int i=0; i<k; i++) {
            answer += diff[i];
        }

        return answer;
    }
    //실행 메인 
    public static void main(String[] args){
        Solution T = new Solution();
        System.out.println(T.solution(new int[]{7, 8, 5, 12, 3, 1, 3, 1, 1, 12}, 2));
        System.out.println(T.solution(new int[]{8, 2, 12, 12, 12, 12, 2, 2}, 2));
        System.out.println(T.solution(new int[]{3, 7, 12, 3, 3, 5, 7, 8, 9, 11, 23, 4, 6, 7}, 3));
        System.out.println(T.solution(new int[]{12, 34, 56, 23, 22, 34, 55, 45, 24, 23, 45, 55, 55, 23, 11, 12, 23, 12}, 3));
        System.out.println(T.solution(new int[]{14, 15, 20, 11, 10, 20, 20, 12, 9, 22, 27, 25, 30, 19}, 3));
    }
}

---

🟦 4-4. 심사위원

문제 풀이

⬛ Math 클래스 사용하기

🏓 1) 소수점 내림(바닥으로 floor) | Math.floor() 함수

🏓 2) 소수점 올림 (천장으로 ceiling) | Math.ceil() 함수

🏓 3) 소수점 반올림(반올림round) | Math.round() 함수

🏓 4) 절댓값 | Math.abs() 함수

완성 코드

• Sliding windor (조금씩 밀면서) 풀어야 할 문제
• 어쨋든 문제의 요구 조건은 평균을 k개 골라 구하되 여러 개이면 가장 작은 평균을 이용한다고 했으므로
• 1) Arrays.sort() 오름차순 정렬 후
• 2) i~(i+k-1) 사이 차가 10 이하이면서 → 3개의 연속된 값의 평균이 곧장 정답이 된다. (그래야 가장 작은 평균이 되므로)
• [n 이 10만 이상이라는 제한사항]

⇒ 이중for문 돌면 안되므로 따로 평균 구하는 getAve() 함수 정의한 뒤,

solution() 함수 내부에서 for문으로 i하나씩 밀면서 i, i+k-1 사이값이 10 이하인 연속된 값 찾았으면 곧장 getAve() 함수 호출하여 return 하면

// 4-4. 심사위원 
import java.util.*;
class Solution {
    //평균 얻기 
    public int getAve(int[] score, int s, int e) {
        int sum = 0;

        for(int i=s; i<=e; i++) {
            sum += score[i];
        }
        //소수점 버리기 
        return (int) Math.floor((sum/(e-s+1)));
    }

    //솔루션 함수 
    public int solution(int[] score, int k){
        int answer = 0;
        int n = score.length;
        //오름차순 정렬 (작은->큰)
        Arrays.sort(score);
        //이중 for문 안돌고 한번에 끝내는 방법 
        for(int i=0; i<n-k; i++) {
            //처음부터 발견한 차이 10이하의 연속된 값 발견 시, 
            if(score[i+k-1] - score[i] <= 10) {
                return getAve(score, i, i + k - 1);
            }
        }

        return answer;
    }
    public static void main(String[] args){
        Solution T = new Solution();
        System.out.println(T.solution(new int[]{99, 97, 80, 91, 85, 95, 92}, 3));
        System.out.println(T.solution(new int[]{92, 90, 77, 91, 70, 83, 89, 76, 95, 92}, 4));
        System.out.println(T.solution(new int[]{77, 88, 78, 80, 78, 99, 98, 92, 93, 89}, 5));
        System.out.println(T.solution(new int[]{88, 99, 91, 89, 90, 72, 75, 94, 95, 100}, 5));
    }
}

다시 풀이  RE

package to_0524_2;

import java.util.*;
class Solution_Re {
	//평균 - 소수점 버림
	public int getAve(int s, int e, int[] score) {
		int sum = 0;
		for(int i=s; i<=e; i++) {
			sum += score[i];
		}
		
		return (int) Math.floor(sum / (e - s + 1));
				
	}
	
	//솔루션 함수 
	public int solution(int[] score, int k){
		int answer = 0;
		
		int n = score.length;
		
		//오름차순 정렬
		Arrays.sort(score);
		
		for(int i = 0; i<n-k ; i++) {
			//양끝단 차이 10이하인 연속된 세 수 발견 시,
			if(score[i+k-1] - score[i] <= 10) {
				//그 평균이 정답이 됨
				return getAve(i, i+k-1, score);
			}
		}

		return answer;
	}
	//실행 메인 
	public static void main(String[] args){
		Solution_Re T = new Solution_Re();
		System.out.println(T.solution(new int[]{99, 97, 80, 91, 85, 95, 92}, 3));
		System.out.println(T.solution(new int[]{92, 90, 77, 91, 70, 83, 89, 76, 95, 92}, 4));
		System.out.println(T.solution(new int[]{77, 88, 78, 80, 78, 99, 98, 92, 93, 89}, 5));
		System.out.println(T.solution(new int[]{88, 99, 91, 89, 90, 72, 75, 94, 95, 100}, 5));
	}
}