2. 카드 점수 (+슬라이딩 윈도우)

DFS 이용한 풀이

 

package Q2;

import java.util.Arrays;

public class Main {
    //카드 점수
    //카드 종류와 뽑을 카드 수가 주어지면
    //가장 왼쪽 또는 가장 오른쪽 끝에 있는 카드를 가져온다.
    //가져온 카드의 총 합이 가장 큰 경우를 출력
    public static void main(String[] args) {
//        int[] nums={3,2,5,6,7,1};
//        int k=3;
        //int[] nums={3, 1, 4, 5, 4, 1, 2, 5};
        //int k=5;
        int[] nums={6, 7, 1, 3, 1, 4, 3, 1, 1, 5, 4, 1, 2, 5};
        int k=10;
        System.out.println(solve(nums, k));
    }
    static int answer=0;

    public static int solve(int[] nums, int k){
        int n=nums.length;
        //lt, rt
        //가장 왼쪽 혹은 가장 오른쪽 끝에 있는 카드를 가져온다.

        DFS(nums, 0, k, 0, 0, nums.length-1);
        return answer;
    }
    public static void DFS(int[] nums,int L, int k, int sum,int lt, int rt){
        if(L==k){
            answer=Math.max(answer, sum);
            return;
        }
        DFS(nums, L+1, k, sum+nums[lt],lt+1, rt);
        DFS(nums, L+1, k, sum+nums[rt],lt, rt-1);
        //return -1;
    }
}

---

+) 세련된 풀이

: 슬라이딩 윈도우, 연속 부분 수열

 

참고자료

: 슬라이딩 윈도우

1. 단어 중복 없는 가장 긴 문자열

https://and-some.tistory.com/901

[LeetCode- Ch4. 투 포인터] 1. 단어중복없는 가장 긴 문자열 #(+ 슬라이딩 윈도우)

2. 최대 매출

https://and-some.tistory.com/513

[Ch.03 - 투 포인터] 3. 최대 매출 (+ 슬라이딩 윈도우)

 

:연속부분수열

1. 연속부분수열

https://and-some.tistory.com/514

[Ch.03 - 투 포인터] 4. 연속 부분수열

2. 최대길이 연속부분수열

https://and-some.tistory.com/516

[Ch.03 - 투 포인터] 6. 최대 길이 연속부분수열 #

 

---

nums에서 k개를 제거 후, (nums.length-k) 개가 배열 안쪽에서 연속으로 남는 연속부분수열의 합이 가장 작은 경우 찾기

:O(n)의 시간복잡도

import java.util.*;
import java.util.Map.Entry;
class Main {	
	public int solution(int[] nums, int k){
		int answer=0;
		for(int x : nums) answer+=x;
		int remain=nums.length-k;
		int sum=0;
		for(int i=0; i<remain; i++) sum+=nums[i];
		int Nmin=sum;
		for(int i=remain; i<nums.length; i++){
			sum+=(nums[i]-nums[i-remain]);
			Nmin=Math.min(Nmin, sum);
		}
		return answer-Nmin;
	}

	public static void main(String[] args){
		Main T = new Main();
		int[] arr1={3, 2, 5, 6, 7, 1};
		System.out.println(T.solution(arr1, 3)); //14
		int[] arr2={3, 1, 4, 5, 4, 1, 2, 5};
		System.out.println(T.solution(arr2, 5)); //18
		int[] arr3={6, 7, 1, 3, 1, 4, 3, 1, 1, 5, 4, 1, 2, 5};
		System.out.println(T.solution(arr3, 10)); //35
	}
}

 

package Q2;

import java.util.Arrays;

public class Main {
    //카드 점수
    // 가장왼쪽 또는 가장 오른쪽 끝에 있는 카드를 가져온다.
    public static void main(String[] args) {
//        int[] nums={3,2,5,6,7,1};
//        int k=3;
        //int[] nums={3, 1, 4, 5, 4, 1, 2, 5};
        //int k=5;
        int[] nums={6, 7, 1, 3, 1, 4, 3, 1, 1, 5, 4, 1, 2, 5};
        int k=10;
        System.out.println(solve(nums, k));
    }
    static int answer=0;

    public static int solve(int[] nums, int k){
        int answer=0;
        for(int x: nums) answer+=x;
        //모든 카드 중 뽑아야하는 개수를 제외한 개수를 구한다.
        int remain=nums.length-k;

        //뽑고 남은 카드의 숫자 합을 구한다.
        int sum=0;
        //최솟값 변수를 남은 카드 개수로 초기 설정
        for(int i=0;i<remain;i++) sum+=nums[i];
        int Nmin=sum;

        //뽑고 남은 카드부터 전체 카드 개수만큼 반복을 수행한다.
        for(int i=remain; i<nums.length; i++){
            sum+=(nums[i]-nums[i-remain]);
            Nmin=Math.min(Nmin, sum);
        }
        return answer-Nmin;
    }
}