https://school.programmers.co.kr/learn/courses/30/lessons/12941
프로그래머스
SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프
programmers.co.kr
풀이과정
내 생각에는 일단 최솟값을 만들기 위해서는 극단적 예시로 배열이
A : [ 1, 2, 3 ]
B : [ 1, 2, 3 ]
이렇게 주어졌을때 오름차순 * 오름차순보다는 (결과 1*1 + 2*2 + 3*3 = 14)
A : [ 1, 2, 3 ]
B : [ 3, 2, 1 ]
이렇게 오름차순*내림차순을 곱했을때 최솟값일거라는 생각이었고, (결과 1*3 + 2*2 + 3*1 = 10)
그 생각이 맞았다.
1. 코드
import java.util.*;
class Solution
{
public int solution(int []A, int []B)
{
int answer = 0;
Arrays.sort(A);
Integer[] b = Arrays.stream(B).boxed().toArray(Integer[]::new);
Arrays.sort(b,Collections.reverseOrder());
for(int i = 0 ; i < A.length; i++){
answer+=A[i]*b[i];
}
return answer;
}
}
이렇게 작성했고, 테케는 다 맞았다.
근데 이 자식이 효율성에서 밀리네?
아마 B를 내림차순하는 과정에서 B를 Integer 배열로 변환할때 효율성이 떨어지나보다. ( O( nlogn) )
그래서 A를 내림차순하고 B를 오름차순 했더니 테스트1,4번이 시간초과 뜸ㅋㅋ
2. 수정코드
import java.util.*;
class Solution
{
public int solution(int []A, int []B)
{
int answer = 0;
Arrays.sort(A);
Arrays.sort(B);
int n = B.length;
for (int i = 0; i < n / 2; i++) {
int temp = B[i];
B[i] = B[n - 1 - i];
B[n - 1 - i] = temp;
}
for(int i = 0 ; i < A.length; i++){
answer+=A[i]*B[i];
}
return answer;
}
}
그래서 그냥 B를 오름차순 한 후에 내가 친절히 앞뒤를 바꿔서 내림차순으로 만들어줬다.
그리고 성공은 했다.
회고
lv2로 넘어오니까 시간복잡도를 이제는 슬슬 챙겨야할때가 왔구만,,
'알고리즘' 카테고리의 다른 글
[ 누적합 ] 백준 - 2차원 배열의 합 (0) | 2024.11.26 |
---|---|
[ Java ] 프로그래머스 - 3진법 뒤집기 (0) | 2024.10.16 |
[ 알고리즘 ] 이진탐색 Binary Search (0) | 2024.07.30 |
[ 알고리즘 ] 그래프 (1) | 2024.07.26 |
[ 알고리즘 ] DFS & BFS (7) | 2024.07.23 |