(24.10.15)
먼저 문제를 파악해보자. 두 배열과 k가 입력되면 k만큼의 num1배열의 값들의 합과 k만큼의 num2배열의 최소값을 곱해 점수를 계산한다. 이때 최대 점수를 구하는 문제이다. 쉬워보인다.
public long maxScore(int[] nums1, int[] nums2, int k) {
int max=0;
int length= nums1.length;
for(int i=0; i<length-k; i++){
int sum=0;
int min=nums2[i];
for(int j=i; j<i+k; j++){
sum+=nums1[j];
if(nums2[j]<min){
min=nums2[j];
}
}
int score=sum*min;
//System.out.println("sum="+sum+", min="+min+", score="+score);
if(max<score){
max=score;
}
}
return max;
}다만 문제를 잘못이해한 부분이 있었는데, 연속된 subsequence가 아닌 k개의 원소를 고르는 문제같아보인다.
그래서 수정을 해보니 이것도 아니다.. 문제 이해하기가 조금 어렵다..
class Solution {
public long maxScore(int[] nums1, int[] nums2, int k) {
int length= nums1.length;
int max=0;
for(int i=0; i<length; i++){
for(int j=i+1; j<length; j++){
for(int l=j+1; l<length; l++){
int sum=nums1[i]+nums1[j]+nums1[l];
int min=Math.min(Math.min(nums2[i], nums2[j]), nums2[l]);
int score=sum*min;
if(max<score)
max=score;
}
}
}
return max;
}
}ㅇㅎ 앞뒤 순서는 지키면서 하는 듯하다. 이해하였다.
(24.10.16)
현재 문제는 k이다. 몇개의 원소를 선택할지를 결정하는 중요한 인자가 변수값으로 되어있어 일괄적인 코드를 작성하기 어렵다. 예를들어 k가 1이면 for문을 사용해 모든 원소를 선택하는 경우를, k가 2이면 for문 2개로 모든 원소를 선택하는 경우를 설계하면 되는데 for문이 몇개 사용될지 자체가 k변수여서 어려움이 있다. for문이 아닌 다른 방식으로 접근해봐야할 듯 하다. subsequence를 구하는 것이니 역으로 불필요한 원소를 삭제하는 방식으로 접근해보자. k가 남게끔 다른 원소들을 삭제하는 방법이 뭐가 있을까? 그러나 인자가 int[]로 되어있어 삭제가 힘들것이라 판단, 동적할당을 이용하여 접근해보았다.
class Solution {
public long maxScore(int[] nums1, int[] nums2, int k) {
int length=nums1.length;
int[] pointer=new int[k];//동적 할당 사용
for(int i=0; i<k; i++)
pointer[i]=i;//초기값 세팅(시작 index)
int minimum_score=10000000;
for(int ptr=k-1; 0<=ptr; ptr--){//끝 원소부터 역으로 시작
for(;pointer[ptr]<length; pointer[ptr]++){
int sum=0, min=1001;
for(int i=0; i<k; i++){
sum+=nums1[pointer[i]];
if(min>nums1[pointer[i]]){
min=nums1[pointer[i]];
}
}
int score=sum*min; System.out.println(score);
if(minimum_score>score){
minimum_score=score;
}
}
if(ptr-1!=-1)
pointer[ptr-1]++;
pointer[ptr]=k-1;
}
return minimum_score;
}
}코드 초안이다. 어떤 Case도 통과하지 못했지만 동적할당을 이용해 for문으로 k를 구현해내는 시도를 보완해보겠다.
(24.10.17)
조금 더 시도해봤는데 동적할당으로 코드를 설계하기에 너무 복잡하여 내 두뇌의 한계를 느꼈다. 다른 간편한 방법이 없을까? 도저히 모르겠어서 Hint1을 열어보니 sort를 제시해주었다. 이런 대박..인데 잘 모르겠다. . 아예 기본 접근 방법조차 감이 안잡히는 것 같다.
(24.11.06)
굉장히 오랜만에 풀이하는 것이기에 문제를 다시 읽어보자.
기억이 난다. k개를 앞에서부터 순서대로 골라서 nums1에서는 sum을 num2에서는 minimum을 구한 뒤 곱 중 최댓값을 반환하는 문제였다.
이 문제의 핵심은 인덱스 k개를 어떻게 로직으로 만들것인가로 기억한다. 기존에 for루프를 이용한 방법으로는 구현해내기 굉장히 어려웠다. 문제를 분해해서 접근해보자. k개의 원소를 고르는 것부터 생각해보자. 사실 그게 어렵다.. 그럼 문제를 크게 생각해보자. 구해야하는 것은 두 값의 곱 최댓값이다. nums1에서 구한 sum값이 커야하고, nums2에서 구한 min값이 커야한다. 힌트로 주어진 sort를 잘 이해못하겠으니 Example1을 sort해서 분석해보자.
Example 1을 sort하면 nums1=[1,2,3,3] nums2=[1,2,3,4]이다.
근데 sort를 하면 nums1과 nums2의 index 순서가 엇갈려 문제가 생긴다. 두 조건을 고려하여 sort 조건을 새로이 만들면 될까? 이는 어려워보인다. 각각을 sort하고 엮을 수 있는 방법이 있을까? 위 상황에서 직관적인 최댓값은 k가 3일 때 (2+3+3)(2)=16이다. 다만 index가 달라 불가능하다. 아무리 생각해도 sort를 엮을 마땅한 방법이 보이지 않는다. sliding window는 어떨까? 떨어져 있는 원소를 엮을 순 없어 문제의 조건을 모두 충족시키진 못하지만 이용할 수 있지 않을까?
Example 1을 sliding window로 접근하면
(1+2+3)(1)=6
(1+2+3)(2)=12
(2+3+3)(1)=8
(2+3+3)*(2)=16
4가지 경우가 존재한다. 이때 답인 12도 있고 답이 아닌 16도 있다. 답이 아닌 경우를 거를 수 있을까? sort를 할 때 원래의 index를 담은 lookup table을 만들고 sliding window를 거치며 원래의 인덱스가 일치하는 경우에만 max값을 갱신하게 코딩을 해볼까? 모든 경우를 다 담을 수 있는지 아직은 잘 모르겠지만 힌트가 sort니 최대한 시도를 해봐야 할 듯 하다.
아래는 내가 작성한 인덱스 정보를 담으며 정렬하는 함수이다.
private int[] sort_with_index(int[] nums){
int[] indices=new int[nums.length];
for(int i=0; i<nums.length; i++)
indices[i]=i;
Arrays.sort(indices, new Comparator<Integer>(){
@Override
public int compare(Integer i1, Integer i2){
return nums[i1]-nums[i2];
}
});
nums=Arrays.stream(nums).sorted().toArray();
return indices;
}하지만 Comparator의 이해 부족으로 gpt의 도움을 청하게 되었다.
private int[] sort_with_index(int[] nums){
Integer[] indices=new Integer[nums.length];//정렬 시 변경될 인덱스 정보를 저장할 인덱스 lookup table
for(int i=0; i<nums.length; i++)
indices[i]=i;//초기값 설정
Arrays.sort(indices, new Comparator<Integer>(){//Arrays.sort에서 특별한 조검을 지정하고 싶으면 Comparator객체를 생성해서 준다.
@Override
public int compare(Integer i1, Integer i2){//compare함수를 가지고 있으면 되고 반환타입읜 Comparator<>제네릭 타입을 따른다.
return Integer.compare(nums[i1], nums[i2]);//num1-num2보다 직관적으로 Integer.compare을 사용.
}
});
Arrays.sort(nums);//실제 배열 정렬
return Arrays.stream(indices).mapToInt(Integer::intValue).toArray();//Integer[]타입을 int[]로 변경
}위의 함수를 기반으로 코드를 작성하였다.
class Solution {
private int[] sort_with_index(int[] nums){
Integer[] indices=new Integer[nums.length];//정렬 시 변경될 인덱스 정보를 저장할 인덱스 lookup table
for(int i=0; i<nums.length; i++)
indices[i]=i;//초기값 설정
Arrays.sort(indices, new Comparator<Integer>(){//Arrays.sort에서 특별한 조검을 지정하고 싶으면 Comparator객체를 생성해서 준다.
@Override
public int compare(Integer i1, Integer i2){//compare함수를 가지고 있으면 되고 반환타입읜 Comparator<>제네릭 타입을 따른다.
return Integer.compare(nums[i1], nums[i2]);//num1-num2보다 직관적으로 Integer.compare을 사용.
}
});
Arrays.sort(nums);//실제 배열 정렬
return Arrays.stream(indices).mapToInt(Integer::intValue).toArray();//Integer[]타입을 int[]로 변경
}
public long maxScore(int[] nums1, int[] nums2, int k) {
int length=nums1.length;
int max_score=0;
int[] sorted_nums1_indices=sort_with_index(nums1);
int[] sorted_nums2_indices=sort_with_index(nums2);
for(int i=length-1; k<=i; i--){
int sum=0, min=100000;//데이터가 양의 정수기에 0으로 초기화
boolean is_align=true;//인덱스 순서 체크 플래그
for(int j=0; j<k; j++){
//가산
sum+=nums1[i-j];
//최소
if(min>nums2[i-j]) {
min = nums2[i - j];
}
//인덱스 순서 체크
if(sorted_nums1_indices[i-j] == sorted_nums2_indices[i-j]) {
is_align = false;
break;
}
}
if(is_align && max_score < sum*min){
max_score=sum*min;
}
}
return max_score;
}
}
하지만 sorted_nums_indices등으로 인덱스 순서가 안맞아 걸려졌어야 할 최댓값이 그대로 나오고 있다. 디버깅해보자. 같은 값의 인덱스 위치가 두번 저장되었다.
문제는 저 인덱스만 바꾸어 실행해도 여전히 16이 출력된다는 것이다. 실수했다. 저건 데이터 값인 nums고 sorted_nums1_indices는 잘 계산되어 있다.
힌트를 전부 열람해보자.
nums2를 기반으로 정렬을 해보라고 한다. minimum중에 최댓값을 찾으라 한다.
nums2를 sort하고 뒤에서 k번째 값이 minimum 중에 최댓값이 된다. 그 후 k만큼의 합을 곱해서 계산해보자.
class Solution {
private int[] sort_with_index(int[] nums){
Integer[] indices=new Integer[nums.length];//정렬 시 변경될 인덱스 정보를 저장할 인덱스 lookup table
for(int i=0; i<nums.length; i++)
indices[i]=i;//초기값 설정
Arrays.sort(indices, new Comparator<Integer>(){//Arrays.sort에서 특별한 조검을 지정하고 싶으면 Comparator객체를 생성해서 준다.
@Override
public int compare(Integer i1, Integer i2){//compare함수를 가지고 있으면 되고 반환타입읜 Comparator<>제네릭 타입을 따른다.
return Integer.compare(nums[i1], nums[i2]);//num1-num2보다 직관적으로 Integer.compare을 사용.
}
});
Arrays.sort(nums);//실제 배열 정렬
return Arrays.stream(indices).mapToInt(Integer::intValue).toArray();//Integer[]타입을 int[]로 변경
}
public long maxScore(int[] nums1, int[] nums2, int k) {
int length=nums1.length;
int[] sorted_nums2_indices=sort_with_index(nums2);
int min=nums2[length-k], sum=0;
for(int i=0; i<k; i++){
sum+=nums1[sorted_nums2_indices[length-1-i]];
}
return min*sum;
}
}
처음으로 상당한 진전이 있었다.
(24.11.07)
오류가 발생한 15번 케이스를 살펴보면 [0, 1, 2]번 인덱스를 봤을 때 177=119로 내가 고른 최댓값이지만, [0, 2, 3]번 인덱스를 보면 286=168로 더 최댓값이 나오게 된다. 즉, 현재는 nums2를 기준으로 정렬하여 계산하기에 nums1을 기준으로 계산된 값이 무시되고 있는 것이다. 방법은 간단해보인다. nums1을 기준으로도 값을 계산한 뒤 두 값 중 최댓값을 리턴시켜보자.
class Solution {
private int[] sort_with_index(int[] nums){
Integer[] indices=new Integer[nums.length];//정렬 시 변경될 인덱스 정보를 저장할 인덱스 lookup table
for(int i=0; i<nums.length; i++)
indices[i]=i;//초기값 설정
Arrays.sort(indices, new Comparator<Integer>(){//Arrays.sort에서 특별한 조검을 지정하고 싶으면 Comparator객체를 생성해서 준다.
@Override
public int compare(Integer i1, Integer i2){//compare함수를 가지고 있으면 되고 반환타입읜 Comparator<>제네릭 타입을 따른다.
return Integer.compare(nums[i1], nums[i2]);//num1-num2보다 직관적으로 Integer.compare을 사용.
}
});
Arrays.sort(nums);//실제 배열 정렬
return Arrays.stream(indices).mapToInt(Integer::intValue).toArray();//Integer[]타입을 int[]로 변경
}
public long maxScore(int[] nums1, int[] nums2, int k) {
int length=nums1.length;
int[] tmp=new int[length];
for(int i=0; i<length; i++)
tmp[i]=nums1[i];
int[] sorted_nums1_indices=sort_with_index(nums1);
int min1=100000, sum1=0;
for(int i=0; i<k; i++){
sum1+=nums1[length-1-i];
if(min1 > nums2[sorted_nums1_indices[length-1-i]]){
min1=nums2[sorted_nums1_indices[length-1-i]];
}
}
int max_val1=min1*sum1;
int[] sorted_nums2_indices=sort_with_index(nums2);
int min2=nums2[length-k], sum2=0;
for(int i=0; i<k; i++){
sum2+=tmp[sorted_nums2_indices[length-1-i]];
}
int max_val2=min2*sum2;
return max_val1>max_val2?max_val1:max_val2;
}
}
테스트 케이스 17번까지 진행할 수 있었다.
(24.11.08)
현황이다. 저 사진 기준으로 Case 3 디버깅을 시작해보자.
max_val1은 nums1을 우선적으로 고려한 계산값이다. 올바르게 계산되었는지 확인해보자. sorted_nums1_indices는 정상적으로 정렬이 되었고, 계산은 (22+25+28)9=675이다.
max_val2은 nums2을 우선적으로 고려한 계산값이다. sorted_nums2_indices는 정상적으로 정렬이 되었고, 계산은 25(5+25+15)=1125이다.
그렇다면 정답은 어떻게 계산되었을까? 22*(22+25+15)=1364로 계산된다. 이는 아쉽게도 nums1을 우선적으로 고려한 값도, nums2를 우선적으로 고려한 값도 아니다.
그렇다면 이 중간값까지도 찾아내기 위하여 할 수 있는 선택지는 무엇일까? nums1과 nums2를 모두 정렬하고 k만큼의 sliding window를 적용해서 산출되는 max_val값들을 for문으로 비교하면 어떨까?
지금까지 시도한 테스트 케이스들은 모두 통과했지만, testcase14번에서 max_val값이 0이되는 오류를 발견하였다. 이는 min값의 초기화에 관련이 깊을 것으로 보인다.
그런데 문득 생각이 들었다. 현재 이 문제를 해결하기 위해서는 nums1의 배열에서 k만큼의 sub index들을 골라서 값을 계산하는 과정이 필요하다. 일반적인 sliding window방식은 sub index를 고르는 것과 차이가 존재하지만, 문제의 힌트에서 얻은 정렬과 함께 사용하여 그 차이를 매꾸고자 했었다. 하지만 현재 5개의 테스트케이스를 통과했음에도 불구하고 다른 테스트 케이스에서 문제가 발생했다는 것을 보아, 내가 의도한 대로 코드는 작성되었지만 내가 사용한 로직이 sliding window와 sub index의 차이를 극복해내지 못했다고 판단된다. 결론적으로, 현재의 접근방식이 아닌 새로운 접근 방식이 필요하다는 것이다.
문제 접근의 모토로 simple is best를 가지고 있는데 어떻게 하면 이 sub index 문제를 효율적으로 해결할 수 있을지 다시한번 고민이 필요해보인다.
(24.11.13)
오늘은 이 문제를 꼭 해결했으면 좋겠다.
문제를 다시 정리해보면 nums1과 nums2배열에서 무작위 k개의 인덱스를 추출, nums1에서의 합과 nums2에서의 최솟값의 곱이 최대가 되는 값을 구하는 것이다.
이전에 접근한 방법인 nums1 합이 최대가 되는 경우, nums2의 최솟값이 최대가 되는 경우로 접근했을 때 웬만한 테스트 케이스를 통과할 수 있었지만 둘 다 해당하지 않는 경우가 존재했다. 코딩에 편법은 없다는 사실을 다시금 깨닫게 된다. 어떻게 하면 최적의 알고리즘으로 문제를 해결할 수 있을까?
가장 이상적인 for 반복문을 사용한 접근법의 딜레마는 아래와 같다.
k에 따라서 필요한 for 반복문의 깊이가 달라진다. 재귀를 이용하면 어떨까? 아니면 int[k]로 인덱스를 조절하면?
열심히 머리를 굴려보니 int[k]로 접근이 가능할 듯 하다.
class Solution {
public int calculate(int[] nums1, int[] nums2, int[] indexes){
int sum=0, min=100000;
for(int i=0; i<indexes.length; i++){
sum+=nums1[indexes[i]];
if(nums2[indexes[i]]<min){
min=nums2[indexes[i]];
}
}
int result_val=sum*min;
return result_val;
}
public long maxScore(int[] nums1, int[] nums2, int k) {
final int length=nums1.length;//1. 배열의 길이 저장
int[] indexes=new int[k];//2. 인덱스들 초기값 세팅
for(int i=0; i<k; i++){
indexes[i]=i;
}
int max_val=0;
for(int i=0; i<k; i++){//3. 인덱스 접근 시작
int cur_idx=k-1;
for(int j=indexes[cur_idx]; j<length; j++){//4. 마지막 인덱스부터 ~ 끝 접근
indexes[cur_idx]=j;//5. 함수 전달을 위해 indexes 갱신
int result_val=calculate(nums1, nums2, indexes);//6. indexes기반 값 계산
if(result_val>max_val){//7. 최댓값 갱신
max_val=result_val;
}
}
//8. 다음 탐색을 위한 indexes 갱신. 앞의 indexes[]원소 탐색을 위해 앞 index를 ++, 뒤의 인덱스를 한칸 앞으로 옮겨야 한다.
if(cur_idx>0){//0번은 이전 원소가 없기 때문에
for(int j=cur_idx-1; j<k; j++){//9. 현재 탐색한 인덱스 앞 인덱스를 현재 인덱스로 옮기고 나머지는 +1한 값으로 갱신
indexes[j]=j+1;//초기값에서 한칸씩 shift하여 갱신
}
} else{//0번 원소라면
for(int j=cur_idx; j<k; j++){//자기부터 shift하여 갱신
indexes[j]=j+1;
}
}
}
return max_val;
}
}k번의 for 루프를 i, i+1꼴을 사용하는 반복문 구조로 표현하였다.
내가 짠 코드대로라면 모든 경우를 전부 구해낼 수 있기 때문에 어느 부분에서 오류가 발생했는지 Case 10번을 디버깅해보자.
위는 값 계산 시 indexes의 상태들을 출력한 결과이다. 값 계산 이후 제대로 indexes가 갱신되고 있지 않음을 확인할 수 있다.
감각적으로 인덱스를 변경시켜서 원활히 루프를 돌 수 있게 수정하였다.
이번엔 TestCase 11번에서 아예 결과값이 0이 출력되는 오류를 발견하였다. 디버깅해보자.
놀랍게도 값 갱신 과정에서 일부 경우가 빠져있었다. 확인해보니 cur_idx의 갱신를 하지 않았다. 그래서 감각적으로 고칠 때 i를 빼서 cur_idx 갱신값을 계산하여 고친 것.
cur_idx--를 루프 마지막에 넣어주자.
너무 어렵다.. for 반복문이 유지보수가 왜 어려운지 알 수 있는 부분이다. 딱 5분만 더 시도해보자. 우선 문제가 발생하는 부분은 아래와 같다.
그러나 현재 sout내용을 자세히 보니 아래로 갈수록 7,1,2 등 난장판이 되고 있었다. cur_idx--변경 전의 코드로 되돌아가자. 아래의 코드는 현재의 코드이다.
public int calculate(int[] nums1, int[] nums2, int[] indexes){
int sum=0, min=100000;
for(int i=0; i<indexes.length; i++){
sum+=nums1[indexes[i]];
if(nums2[indexes[i]]<min){
min=nums2[indexes[i]];
}
}
int result_val=sum*min;
return result_val;
}
public long maxScore(int[] nums1, int[] nums2, int k) {
final int length=nums1.length;//1. 배열의 길이 저장
int[] indexes=new int[k];//2. 인덱스들 초기값 세팅
for(int i=0; i<k; i++){
indexes[i]=i;
}
int max_val=0;
int cur_idx=k-1;
for(int i=0; i<k; i++){//3. 인덱스 접근 시작
for(int j=indexes[cur_idx]; j<length; j++){//4. 마지막 인덱스부터 ~ 끝 접근
indexes[cur_idx]=j;//5. 함수 전달을 위해 indexes 갱신
//print_indexes(indexes, cur_idx);
int result_val=calculate(nums1, nums2, indexes);//6. indexes기반 값 계산
if(result_val>max_val){//7. 최댓값 갱신
max_val=result_val;
}
}
//8. 다음 탐색을 위한 indexes 갱신. 앞의 indexes[]원소 탐색을 위해 앞 index를 ++, 뒤의 인덱스를 한칸 앞으로 옮겨야 한다.
if(cur_idx-1>=0){//0번은 이전 원소가 없기 때문에
for(int j=cur_idx-1; j<k; j++){//9. 현재 탐색한 인덱스 앞 인덱스를 현재 인덱스로 옮기고 나머지는 +1한 값으로 갱신
indexes[j]=j+1;//초기값에서 한칸씩 shift하여 갱신
}
} else{//0번 원소라면
for(int j=cur_idx; j<k; j++){//자기부터 shift하여 갱신
indexes[j]=j+1;
}
}
cur_idx--;
}
return max_val;
}오늘은 일단 여기까지 하자.. 새로운 int[]접근법으로 TestCase 11/28이면 꽤나 선방했다고 생각한다.
아래는 자바엔 왜 const가 없을까 하고 찾아본 글이다. https://sslblog.tistory.com/23
(24.11.14)
오늘 몸이 좋지 않아 커밋이 가능할진 모르겠지만 천천히 뭐라도 해보자.
(24.11.15)
결국 못했다 ㅋㅋ 오늘도 안좋지만 그래도 하자!
오늘의 목표는 새로 바꾼 코드가 현재 막혔었던 8개 테스트 케이스 중 2개에 fail이 뜨는데 8개 모두 성공시키고 제출하는 것 까지 목표로 잡자.
우선 현재의 코드를 검토해보자. 주석으로 정리하면서 우선 내가 작동되길 원하는 방식으로 코드를 일부 수정해보았다. 하지만 Case 11번을 기준으로 테스트를 돌렸을 때 정상적으로 indexes가 갱신되지 않았는데 이제부터 디버깅을 시작해보자.
import java.util.*;
class Solution {
public void print_indexes(int[] indexes, int cur_idx, int result_val){
System.out.print("[");
for(int i=0; i<indexes.length; i++)
System.out.printf("%d, ", indexes[i]);
System.out.printf("] cur_idx: %d, result_val: %d\n", cur_idx, result_val);
}
public int calculate(int[] nums1, int[] nums2, int[] indexes){
int sum=0, min=100000;
for(int i=0; i<indexes.length; i++){
sum+=nums1[indexes[i]];
if(nums2[indexes[i]]<min){
min=nums2[indexes[i]];
}
}
int result_val=sum*min;
return result_val;
}
public long maxScore(int[] nums1, int[] nums2, int k) {
final int length=nums1.length;//1. 배열의 길이 저장
int[] indexes=new int[k];//2. 인덱스들 초기값 세팅. k개의 배열을 이용해 각각의 원소 인덱스를 저장한다.
for(int i=0; i<k; i++){
indexes[i]=i;
}// 초기값은 0, 1, ... k-1로 순서를 유지한다. indexes는 이전의 원소보다 이후의 원소가 큰 값이어야 한다.
int max_val=0;//indexes에 접근한 값들로 계산한 값의 최댓값을 저장할 원소. 초기값은 0으로 한다.
for(int i=0; i<k; i++){//3. indexes에 해당하는 모든 인덱스를 i로 접근 시작
int cur_idx=k-1;// 원소의 위치를 옮길 때 앞에서부터 뒤로 움직일 것이기에 맨 뒤에 위치하는 원소부터 계산한다.
for(int j=indexes[cur_idx]; j<length; j++){//4. cur_idx부터 끝날 때 까지 값을 계산할 예정이다.
indexes[cur_idx]=j;//5. 함수 전달을 위해 indexes 갱신
int result_val=calculate(nums1, nums2, indexes);//6. 문제에서 요구하는 값 계산(nums1의 합 x nums2의 최소)
print_indexes(indexes, cur_idx, result_val);// debug
if(result_val>max_val){//7. 최댓값 갱신
max_val=result_val;
}
}// 현재까지 indexes의 마지막 원소 ~ 끝을 계산했다. 그 다음은 indexes의 이전 원소를 +1하고 다시 마지막 원소를 ++하며 옮겨가야한다.
//8. 다음 탐색을 위한 indexes 갱신. 앞의 indexes[]원소 탐색을 위해 앞 index를 ++, 뒤의 인덱스를 한칸 앞으로 옮겨야 한다.
// 이전 원소를 기반으로 반복문의 횟수를 줄일 예정이기에 이전 원소가 존재하는 경우(index==0)와 그렇지 않은 경우를 나누어 처리한다.
if(cur_idx>0){//0번은 이전 원소가 없기 때문에
for(int j=cur_idx-1; j<k; j++){//9. 현재 탐색한 인덱스 앞 인덱스를 현재 인덱스로 옮기고 나머지는 +1한 값으로 갱신
indexes[j]=j+1;//초기값에서 한칸씩 shift하여 갱신. 이때 정상적으로 작동한다면, k<=length이기에 인덱스 오버플로우가 안되겠지만 혹시 모르니 예외처리를 해두자.
}//ck. 위에 인덱스 잘 한건지 확인. 검토결과 맞는 듯.
if(indexes[k-1]>=length){// 인덱스 접근 예외 발생
System.out.println("(cur_idx>0)_ERROR! Index out of range");
}
} else{// 0번 원소라면
indexes[0]++;// 기존의 값에서 하나 ++
for(int j=1; j<k; j++){//9. 현재 탐색한 인덱스 앞 인덱스를 현재 인덱스로 옮기고 나머지는 +1한 값으로 갱신
indexes[j]=indexes[j-1]+1;//이전에 +1된 indexes[0]값에서 한칸씩 shift하여 갱신. 이때 정상적으로 작동한다면, k<=length이기에 인덱스 오버플로우가 안되겠지만 혹시 모르니 예외처리를 해두자.
}
if(indexes[k-1]>=length){// 인덱스 접근 예외 발생
System.out.println("(cur_idx==0)_ERROR! Index out of range");
}
}
//cur_idx 갱신이 필요한가?
}
return max_val;
}
void print_status(int[] ptr, int score, int ii, int j){
System.out.print("Score: "+score+" / ");
for(int i=0; i<ptr.length; i++)
System.out.print(ptr[i]+", ");
System.out.print(" / i="+ii+", j="+j);
System.out.println();
}
public void test(long answer, long result){
if(answer==result)
System.out.println("passed! answer: "+answer+", result: "+result);
else
System.out.println("fail! answer: "+answer+", result: "+result);
}
public static void main(String[] args){
Solution solution=new Solution();
// //Case1
// int[] nums1= new int[]{1,3,3,2};
// int[] nums2= new int[]{2,1,3,4};
// solution.test(
// solution.maxScore(nums1, nums2, 3)
// ,12
// );
//
// //Case2
// int[] nums1= new int[]{4,2,3,1,1,};
// int[] nums2= new int[]{7,5,10,9,6};
// solution.test(
// solution.maxScore(nums1, nums2, 1)
// ,30
// );
//
// //Case3
// int[] nums1= new int[]{22,5,25,15,28,1};
// int[] nums2= new int[]{22,30,25,25,9,18};
// solution.test(
// solution.maxScore(nums1, nums2, 3)
// ,1364
// );
//
// //Case4
// int[] nums1= new int[]{1,4};
// int[] nums2= new int[]{3,1};
// solution.test(
// solution.maxScore(nums1, nums2, 2)
// ,5
// );
//
// //Case5
// int[] nums1= new int[]{2,1,14,12};
// int[] nums2= new int[]{11,7,13,6};
// solution.test(
// solution.maxScore(nums1, nums2, 3)
// ,168
// );
//Case10
// int[] nums1= new int[]{44,10,25,0,25,49,0};
// int[] nums2= new int[]{18,39,15,31,43,20,45};
// solution.test(
// solution.maxScore(nums1, nums2, 6)
// ,2304
// );
//Case11
int[] nums1= new int[]{79,76,41,28,41,6,44,30,25};
int[] nums2= new int[]{25,0,69,67,55,0,9,77,26};
solution.test(
solution.maxScore(nums1, nums2, 7)
,2592
);
}
}
놀랍게도 꽤나 테스트를 많이 통과했다! 다행이다ㅎㅎ
step by step으로 아래의 문제 부터 수정해보자.
indexes[k-1]까지는 갱신이 잘 되었지만 indexes[k-2]부터 제대로 갱신이 안되는 것을 확인할 수 있다. 위 부분을 갱신하는 코드를 살펴보자
문제가 발생하는 저 상황은 j의 초기값을 cur_idx-1부터로 해두어서로 추정된다. 계산이 진행될수록 앞부분의 원소부터 끝까지 접근하는 유동적인 구조여야 하기에 최상위 for반복문의 i를 이용하여 수정하겠다.
굉장히 갱신이 잘 이루어지고 있는 것을 확인할 수 있었다. 다만 indexes[0]번째 원소가 갱신되고 얼마 후 index -1로 out of range error가 발생한 것을 확인할 수 있었다.
루프가 값을 다시 계산하기 위해 돌며 cur_idx가 k-1로 초기화 되고, indexes[0]원소까지 ++이 된 상황이면 마지막 루프일 테니 i==k-1일 것이다. 고로 for 루프 안의 j가 초기화 되는 cur_idx-1-i는 k-1-1-k+1=-1이 되어 out of range 에러가 발생한 것이었다.
그러면 코드가 잘못된 것일까? 아니다. 위의 사진을 다시 봐보자.
이미 모든 탐색은 끝났다. 종료조건이 잘못 설정되어 과다하게 계산을 수행했고, 이로 인해 out of range가 발생한 것이었다.
이를 해결하기 위해 가장 쉬운 방법은 아래와 같다.
코드가 복잡해지긴 하겠지만, 현재 내 추측이 맞다면 저 코드 하나로 모든 테스트 케이스가 통과될 것 이다.
아쉽지만 오늘 목표의 1/3을 완료하였다. 실패한 테스트 케이스가 2개로 줄어들었다. 뭐야 ㅋㅋㅋ 생각해보니 저 Case 8번이 지금 수정하던거고 Case 7번은 그냥 디버깅이 되었다. 현재 모든 result_val이 0으로 나오고 있는 것으로 보아 calculate함수에도 문제가 있을 수 있다는 생각이 들었다. 디버깅해보자.
어라 원소가 9개이다. 무슨소리냐면 아래사진처럼 마지막 탐색이 [1,2,3,4,5,6,7] 꼴이 아니라 [2,3,4,5,6,7,8]이어야 한다는 말이다. 또한 [1, ]로 시작하는 indexes의 탐색 역시 제대로 되지 않았다. 이는 indexes[0]을 갱신하는 코드에 문제가 있다는 것을 의미한다.
검토해보니 현재 TestCase의 nums2에 원소 0이 두개나 있어 result_val의 계산은 오류가 없다. 인덱스 갱신이 역시나 제대로 이루어지지 않았던 것이다.
어라.. [0,3,4,5,6,7,8]도 가능한 경우이다. 또한 [0,1,4,5,6,7,8]역시도 가능한 경우이다. 뭔가가.. 모든 루프에서 마지막 계산이 빠져있는 듯 한 느낌이 든다.
아마 내일로 미루어 질 듯 한데 모범답안을 스스로 작성해보자.
indexes의 출력 결과는 아래와 같아야 한다.
[0,1,2,3,4,5,6]
[0,1,2,3,4,5,7]
[0,1,2,3,4,5,8]
[0,1,2,3,4,6,7]
[0,1,2,3,4,6,8]
[0,1,2,3,4,7,8]
[0,1,2,3,5,6,7]
...
[1,2,3,4,5,6,7]
[1,2,3,4,5,6,8]
[1,2,3,4,5,7,8]
...
[2,3,4,5,6,7,8]
현재 [0,1,2,3,4,7,8]부터가 빠져있다.
(24.11.17)
조금만이라도 접근해보자.
다행히 지난번에 정리를 아주 잘해둬서 고쳐야할 사항이 바로 이해가 됐다. 로그값을 보면 끝자리 [..., 7, 8, ]이 모두 누락된 것을 확인할 수 있다. 이는 반복문의 종료조건이 한 단계 먼저 종료되었을 것으로 추측된다.
처음엔 이 부분이 문제로 생각했으나, 이 부분은 단순히 indexes[k-1] 맨 끝 원소를 length-1까지만 옮기는 끝자리 옮기기에 불과하다.
문제는 indexes를 갱신시키는 이 부분에서 있을 것으로 보인다.
디버깅을 해보니 이 부분은 무조건 방금 탐색한 indexes[i]앞의 원소를 세팅시키기에 위에 부분에서 빠진 것처럼 보이는데, 이는 필수적인 로직이 하나 빠져있음을 의미한다.
코드를 급급하게 바꾸었지만 최초 1회만 7,8이 나온다..
우선 7,8만 빠져있는 듯 해 따로 처리코드를 작성하였다.
하지만 당연하게도 저거만 빠져있는게 아니었다.. [1,2,3,4,6,7,8] 도 빠져있고, [2,3,4,5,6,7,8]이 빠져있다. 뭔가 다 같은 부분의 로직이 문제인 듯 하다.
후... 위 로직을 leetcode에 돌려보니 많은 부분에서 오류가 발생한다.. ㅎㅎ...이거 점점 문제가 산으로 가는 것 같다.
case 추가한 순서의 차이이지 실질적인 변화는 크게 없다..
점점 코드가 산으로 가는 만큼 욕심을 버리고 다시 처음부터 시작해야할 듯 하다..
(21.11.19)
생각해보니, 이전에 정렬을 사용한 방식에서 별도로 인덱스 관리를 위한 변수 indexes를 사용했는데 자바 API이용하면 nums1기준으로 정렬될 때 nums1도 그 순서에 맞게끔 정렬이 가능한 것으로 알고있다.
하지만.. 그러면 가독성만 높아질 뿐 기존과 같은 접근이다.
하지만 문제의 힌트가 nums2 기반으로 두 배열을 정렬한 뒤, nums2를 루프하며 찾아보라고 한다.
우선 정렬의 코드는 아래와 같이 작성하였다.
//1. nums2 기준 nums1과 nums2 정렬
int[][] sorted_nums2= IntStream.range(0, length)//인덱스
.mapToObj(i -> new int[]{nums2[i], i})//를 쌍으로 저장
.sorted(Comparator.comparingInt(a -> a[0]))//0번째 값 기준 정렬(1번째 index는 자동)
.toArray(int[][]::new);
int[] sorted_nums1=new int[length];
for(int i=0; i<length; i++)
sorted_nums1[i]=nums1[sorted_nums2[i][1]];nums2 기준으로 nums1이 잘 정렬된 것을 확인할 수 있었다.
다음으로 할 것은 k개를 추출하는 과정이다. nums2기준으로 모두 정렬되어 있기 때문에, 최솟값을 기준으로 루프할 때 반복문을 아래와 같이 작성할 수 있었다.
//2. nums2 기준 최소값 계산
for(int i=0; i<length-k; i++){//종료조건: 그 이상은 최솟값이 될 수 없다.
int nums2_min=nums2[i];
int nums2_sum=nums1[i];
for(int j=i; j<length; j++){//초기값: j가 i미만일 때는 이미 최솟값 기준일 때 고려를 한 경우의 수이다.
//j~length에서 k-1개를 추출하면 된다.
}
}오늘 이 문제의 끝을 찍자. 배열에서 n개를 추출하는 경우를 검색해보니
백트레킹
에 대해서 알게되었다.
DFS와 BFS와 비슷한 개념으로, 가지를 내려가다 해가 없을 것 같으면 빠져나오는 알고리즘으로 가지치기라고 부른다.
또한 조합의 경우를 재귀를 이용해 계산하는 방법에 대하여 검색해보았다.
코드 예시는 아래와 같다.
import java.util.ArrayList;
import java.util.List;
public class CombinationExample {
// 배열에서 n개의 요소를 추출하는 모든 경우의 수를 구하는 함수
public static List<List<Integer>> getCombinations(int[] arr, int n) {
List<List<Integer>> result = new ArrayList<>();//결과를 저장할 리스트를 생성
backtrack(arr, n, 0, new ArrayList<>(), result);//재귀함수 인자로 전달
return result;
}
// 백트래킹을 사용하여 조합을 구하는 함수
private static void backtrack(int[] arr, int n, int start, List<Integer> current, List<List<Integer>> result) {
if (current.size() == n) {//원하는 조합의 개수가 채워졌다면
result.add(new ArrayList<>(current)); // n개가 선택되면 결과 리스트에 추가
return;
}
for (int i = start; i < arr.length; i++) {//시작 지점으로부터 최대 길이까지(맨 처음 시작 원소 루프)
current.add(arr[i]); // 현재 요소를 선택
backtrack(arr, n, i + 1, current, result); // 다음 인덱스로 넘어가며 재귀 호출. 시작 원소로부터 나머지를 i+1로 접근..
current.remove(current.size() - 1); // 선택을 취소하고, 다음 선택을 시도(재활용)
}
}
public static void main(String[] args) {
int[] arr = {1, 2, 3, 4};
int n = 2; // 추출할 원소의 개수
// 조합을 구하고 출력
List<List<Integer>> combinations = getCombinations(arr, n);//n개 만큼의 리스트가 들어있다.
for (List<Integer> combination : combinations) {
System.out.println(combination);
}
}
}아직은 이해하기 많이 어렵다.. 대략적인 흐름은 알겠지만 저 재귀에서 어떻게 i, i+1, i+7, 과 같이 떨어져서 골라지는지는 잘 이해되지 않았다. 하지만 활용은 할 수 있다. 이 방법을 사용한다면 굳이 정렬도 필요없다.
현재 nums1과 nums2를 같은 위치 접근해야하기 때문에, Combination을 indexes에 적용하여 indexes의 조합을 추출한 후 접근해서 값을 계산하는 코드이다.
class Solution {
public List<List<Integer>> getCombinations(int[] arr, int n){
List<List<Integer>> result=new ArrayList<>();
backtrack(arr, n, 0, new ArrayList<>(), result);
return result;
}
public void backtrack(int[] arr, int n, int start, List<Integer> current, List<List<Integer>> result){
if(current.size()==n){
result.add(new ArrayList<>(current));
return;
}
for(int i=start; i<arr.length; i++){
current.add(arr[i]);
backtrack(arr, n, i+1, current, result);
current.remove(current.size()-1);
}
}
public long maxScore(int[] nums1, int[] nums2, int k) {
final int length=nums1.length;
//1. Combination에 사용할 index 리스트 초기화
int[] indexes=new int[length];
for(int i=0; i<length; i++){
indexes[i]=i;
}
List<List<Integer>> combinations=getCombinations(indexes, k);//k개의 인덱스 조합 리스트
int score=0, max_score=0;
int min=10000, sum=0;
for(List<Integer> combination: combinations){
min=10000; sum=0;
for(int i: combination){
sum+=nums1[i];
if(min>nums2[i])
min=nums2[i];
}
score=sum*min;
if(score>max_score)
max_score=score;
}
return max_score;
}
}
ㅎㅎ.. 몇가지 돌려본 결과 올바른 답이 나오지만 MLE가 떠버렸다.
현재 방식은 모든 combinations을 list에 저장하기 때문으로 추정된다. 그렇다면 combination을 구할 때 마다 score를 계산하게끔 공간복잡도 최적화를 진행해보겠다.
class Solution {
private int[] nums1, nums2;
private int max_score=0;
public void getCombinations(int[] arr, int n){
backtrack(arr, n, 0, new ArrayList<>());
}
public void backtrack(int[] arr, int n, int start, List<Integer> current){
if(current.size()==n){
calculate_score(current);
return;
}
for(int i=start; i<arr.length; i++){
current.add(arr[i]);
backtrack(arr, n, i+1, current);
current.remove(current.size()-1);
}
}
public void calculate_score(List<Integer> combination){
int min=10000;
int sum=0;
int score;
for(int i: combination){
sum+=nums1[i];
if(min>nums2[i])
min=nums2[i];
}
score=sum*min;
if(score>this.max_score)
this.max_score=score;
}
public long maxScore(int[] nums1, int[] nums2, int k) {
final int length=nums1.length;
this.nums1=nums1;
this.nums2=nums2;
//1. Combination에 사용할 index 리스트 초기화
int[] indexes=new int[length];
for(int i=0; i<length; i++){
indexes[i]=i;
}
getCombinations(indexes, k);//k개의 인덱스 조합 리스트
return this.max_score;
}
}공간복잡도를 낮추기 위해 List<List>의 result를 없앴는데, 이번엔 TLE가 떴다. 12번 테스트 케이스.. 만만치 않다.
불필요한 함수 호출을 없애고 min계산에 Math.min()을 사용하였다.
class Solution {
private int[] nums1, nums2;
private int max_score=0;
public void backtrack(int[] arr, int n, int start, List<Integer> current){
if(current.size()==n){
calculate_score(current);
return;
}
for(int i=start; i<arr.length; i++){
current.add(arr[i]);
backtrack(arr, n, i+1, current);
current.remove(current.size()-1);
}
}
public void calculate_score(List<Integer> combination){
int min=10000;
int sum=0;
int score;
for(int i: combination){
sum+=nums1[i];
min=Math.min(min, nums2[i]);
}
score=sum*min;
if(score>this.max_score)
this.max_score=score;
}
public long maxScore(int[] nums1, int[] nums2, int k) {
final int length=nums1.length;
this.nums1=nums1;
this.nums2=nums2;
//1. Combination에 사용할 index 리스트 초기화
int[] indexes=IntStream.range(0, length).toArray();
backtrack(indexes, k, 0, new ArrayList<>());
return this.max_score;
}
}여전히 TLE가 발생한다.
min과 sum계산을 더 최적화해보았다.
public void calculate_score(List<Integer> combination){
int min=combination.stream().mapToInt(i->nums2[i]).min().orElse(Integer.MIN_VALUE);
int sum=combination.stream().mapToInt(i->nums1[i]).sum();
int score=sum*min;
if(score>this.max_score)
this.max_score=score;
}여전히 TLE가 발생한다.
관련해서 검색하다가 전역변수가 지역변수보다 딜레이가 있다는 글을 발견했다.
https://straw961030.tistory.com/187
전역변수를 지역변수로 전부 수정하였다.
class Solution {
private int[] nums1, nums2;
public int backtrack(int[] nums1, int[] nums2, int[] arr, int n, int start, List<Integer> current){
int max_score=0;
if(current.size()==n){
int score=calculate_score(nums1, nums2, current);
if(max_score<score)
max_score=score;
return max_score;
}
for(int i=start; i<arr.length; i++){
current.add(arr[i]);
int score=backtrack(nums1, nums2, arr, n, i+1, current);
if(max_score<score)
max_score=score;
current.remove(current.size()-1);
}
return max_score;
}
public int calculate_score(int[] nums1, int[] nums2, List<Integer> combination){
int min=combination.stream().mapToInt(i->nums2[i]).min().orElse(Integer.MIN_VALUE);
int sum=combination.stream().mapToInt(i->nums1[i]).sum();
return sum*min;
}
public long maxScore(int[] nums1, int[] nums2, int k) {
final int length=nums1.length;
//1. Combination에 사용할 index 리스트 초기화
int[] indexes=IntStream.range(0, length).toArray();
//2. backtracking
return backtrack(nums1, nums2, indexes, k, 0, new ArrayList<>());
}
}여전히 TLE가 발생한다.
이유는 사실 모든 경우를 탐색하기보다 문제에 주어진 힌트와 같이 nums2를 기준으로 잡으면 경우의 수가 줄어들기 때문으로 보여진다.
(24.11.25)
TLE 발생을 해결하기 위해, 지금까지 접근했던 방법 두 가지를 섞으려고 한다. 첫 번째로 MLE, TLE외에 답이 정상적으로 출력된 backtrack기반 조합의 방법을 사용할 것이다. 두 번째로 nums2의 최솟값을 기반으로 nums1을 고르는 방법이다.
우선 nums2를 정렬하고 nums1을 정렬된 nums2를 기준으로 정렬시킨다. nums2에서 최솟값 후보들을 순회하며 하나씩 고른다면, 추가적으로 골라야 하는 index개수는 k-1개가 된다. 이때 최솟값보다 후보들은 크거나 같아야 한다. 또한 최솟값 후보들을 정렬된 nums2뒤에서부터 length-k번째는 생략 가능하다. 이를 코드상으로 구현해보자.
class Solution {
private int[] nums1, nums2;
public int backtrack(int[] nums1, int[] nums2, int[] arr, int n, int start, List<Integer> current){
int max_score=0;
if(current.size()==n){
int score=calculate_score(nums1, nums2, current);
if(max_score<score)
max_score=score;
return max_score;
}
for(int i=start; i<arr.length; i++){
current.add(arr[i]);
int score=backtrack(nums1, nums2, arr, n, i+1, current);
if(max_score<score)
max_score=score;
current.remove(current.size()-1);
}
return max_score;
}
public int calculate_score(int[] nums1, int[] nums2, List<Integer> combination){
int min=combination.stream().mapToInt(i->nums2[i]).min().orElse(Integer.MIN_VALUE);
int sum=combination.stream().mapToInt(i->nums1[i]).sum();
return sum*min;
}
public long maxScore(int[] nums1, int[] nums2, int k) {
final int length=nums1.length;
int max_score=0;
//1. nums2 정렬 및 nums2 기준 nums1 정렬. nums2에서 최솟값을 기준으로 연산하기 위함
int[][] sorted_nums2=IntStream.range(0, length)
.mapToObj(i->new int[]{nums2[i], i})
.sorted(Comparator.comparingInt(a->a[0]))
.toArray(int[][]::new);//[i][0]에 정렬된 값을, [i][1]에 그 값의 원래 인덱스를 저장
int[] sorted_nums1=new int[length];
for(int i=0; i<length; i++)
sorted_nums1[i]=nums1[sorted_nums2[i][1]];//nums1[i][1] 기준으로 nums2 정렬
//2. 최솟값 후보 선정
for(int i=0; i<=length-k; i++){
//i+1~length-1까지가 후보군(조합)
int[] indexes=IntStream.range(i,length).toArray();//combination을 계산한 nums2기준 index 리스트
int score=backtrack(nums1, nums2, indexes, k, 0, new ArrayList<>());//backtracking
if(score>max_score)//update max
max_score=score;
}
return max_score;
}
}여전히 TLE가 발생한다. 생각가능한 최선의 방법이기에 위 코드를 기반으로 최적화해보자.
GPT를 이용해보았다. 이를 기반으로 정리 해보자.
현재 k개의 조합을 구하기 위해 O(nCk)복잡도를 가지고, 각 조합마다 O(k)의 연산을 수행하기에 매우 비효율적이라는 지적을 받았다. 현재 코드는 nums2의 최솟값을 기반으로 k-1개를 추출하여 배열을 만든 후 그 인덱스에 해당하는 num1의 최대합과 nums2의 최솟값을 이용해 값을 계산하고 있었다. 이를 지적한 것이다.
GPT에서 제안한 최적화 방법은 크게 2가지이다. 정렬된 nums2를 적극적으로 활용하는 것, nums1의 합을 관리하는 데에 Heap(Priority Queue)를 활용하는 것이다. 후자의 방법에서 nums2에서 최솟값 후보를 고정한 상태에서 nums1에서 가장 큰 값을 포함하는 방식으로 최솟값 별, 가장 큰 값만 탐색하자는 아이디어다. 맨 처음에 접근했던 방법과 유사한데 초기에 nums1의 합 최댓값 x num2의 최솟값에서 각각이 최대일 때를 비교하여 계산했었다. 이때 nums1의 합이 최대는 아닌 값 x nums2의 최소가 아닌 값이 오히려 더 큰 예외경우가 발견됐었다. GPT의 의견은 둘 중 하나의 값을 고정한 뒤 다른 하나의 값을 순회하여 찾는 방식을 선택한 것 같다.
추가적으로 정렬된 nums2를 뒤쪽에서부터 탐색하여 불필요한 탐색을 줄일 것이라고 한다.
이러한 방법을 이용해 기존에 O(nCk)복잡도인 내 코드를 O(n logn)으로 향상시켰다고 한다. 코드를 살펴보자.
import java.util.*;
class Solution {
public long maxScore(int[] nums1, int[] nums2, int k) {
int n = nums1.length;
long maxScore = 0;
// Step 1: nums2를 기준으로 nums1과 nums2 정렬
int[][] sortedNums = new int[n][2];
for (int i = 0; i < n; i++) {
sortedNums[i][0] = nums2[i];//nums2의 원소를 [i][0]에 저장
sortedNums[i][1] = nums1[i];//nums1의 원소를 [i][1]에 저장
}
Arrays.sort(sortedNums, Comparator.comparingInt(a -> -a[0]));//nums2를 기준으로 모두 내림차순 정렬
// Step 2: 우선순위 큐를 사용해 nums1에서 최대합 유지
PriorityQueue<Integer> minHeap = new PriorityQueue<>();//이는 k개의 원소를 담는 공간인데, min값을 바로 추출할 수 있게끔 우선순위큐를 사용(TLE방지)
long currentSum = 0;
for (int i = 0; i < n; i++) {//모든 값을 차례로 순회(현재 nums2 기준 내림차순 정렬)
int num1 = sortedNums[i][1];//nums2에 대응되는 인덱스 nums1값
int num2 = sortedNums[i][0];//시작은 nums2 최댓값
// nums1의 값을 추가하고 currentSum 업데이트(더 작은 새로운 값을 합과 최솟값에 반영. nums2는 정렬에 참고했을 뿐 실질적인 계산은 nums1을 사용)
currentSum += num1;
minHeap.add(num1);
//(처음 k개가 차기 전에는 아래의 if문들이 실행되지 않음)
// k개의 요소를 유지하기 위해 최소값 제거( 새로 추가된 값이 아닌 가장 작은 값을 빼어 nums1의 최대합 유지 )
if (minHeap.size() > k) {
currentSum -= minHeap.poll();
}
/*
* 값을 갱신할 때, nums1의 합이 최대가 되어야 계산 점수가 최대가 될 수 있다.
* 고로 k+1개의 원소 중 minHeap을 이용해 가장 작은 값을 제외시켜 nums1의 합이 최대가 되게끔 유도한다
* 문제 해결의 포인트는 nums2정렬기준 nums1정렬이 아니라,
* 새로운 값을 순회시키면서 k개의 원소 중 가장 작은 num1값을 빼어 nums1의 합이 최대가 되게 만드는 것이다.
*
* 현재 위의 for루프는 k개가 다 찰 때 까지 계속 sum과 min이 업데이트만 되고 k의 크기에 따라 계산을 수행하므로써 최적화 수행
* nums2의 최솟값을 루프시키지 않고 정렬함으로써 단순히 인덱스에 접근하여 이용한다.
* nums1은 최솟값 관리를 위해 minHeap을 사용한다.
*
* 루프는 nums2의 최솟값을 기준으로 순회된다. 여기서 nums2는 추가적으로 수행할 작업이 없다. nums1만 처리하면 된다.
* 근데 이러면 nums2의 최솟값 인덱스에 대응되는 num1의 원소가 포함되어 있다는 것을 보장할 수 있는가?
* */
// 현재 선택된 요소가 k개인 경우 점수 계산
if (minHeap.size() == k) {
maxScore = Math.max(maxScore, currentSum * num2);
}
}
return maxScore;
}
}
최대한 이해해보려 했으나, 전반적인 접근 방식은 이해가 가지만 nums2의 최솟값인 num2에 해당하는 원소 인덱스에 대응되는 nums1의 원소가 priority queue에 포함되어 있다는 것이 보장되는지 이해가 되지 않는다.
nums1은 nums2 기준으로 인덱스가 대응되어있고, nums2는 내림차순 정렬되어 있다...
현재 궁금한걸 코드에서 표시하면
아래와 같이 num2에 대응되는 num1의 값이 add되었다가 k가 초과되어 다시 삭제될 경우..면 삭제가 되더라도 num1과 num2쌍을 같이 삭제하고 같이 추가하므로서 삭제될 때 대응되지 않는 이상한 쌍을 삭제할 일이 없겠네..어쩌면 전체 순회에 대해 잘 이해를 못한 것일 수도 있겠다.
정리. nums2기준 정렬 n만큼 루프돌며 nums1과 nums2의 원소 하나씩 쌍으로 빼서 k개를 채운다. 초과될 시 nums1에서 가장 작은 값을 가진 원소를 대응되는 nums2의 원소와 함께 쌍으로 제거한다. 즉, 이미 nums2를 기준으로 접근하고 있기 때문에 순회를 돌면서는 nums1이 최대가 되게끔 접근시켜 둘 다 고려한다.
비슷한 문제가 나올 경우 이를 바로 떠올릴 수 있을지는 아직 미지수이지만, 둘 사이가 꼭 같이 대응된 상태로 계산되어야 하는 경우에 아래와 같이 정렬시킬 수 있고
int[][] sortedNums=new int[n][2];
for(int i=0; i<n; i++){
sortedNums[i][0]=nums2[i];
sortedNums[i][1]=nums1[i];
}//현재 순서대로 하나의 이차원으로 표현
Arrays.sort(sortedNums, Comparator.comparingInt(a->a[0]));
//모두를 정렬시킬건데 기준(Comparator)을 a가 아닌 a[0]으로 설정값의 삭제와 추가를 동시에 하므로써 문제를 단순화 시킬 수 있다. 는 점을 기억하면 좋을 듯 하다.
