-
카테고리
-
세부 분야
알고리즘 · 자료구조
-
해결 여부
미해결
k번째 큰 수 문제에서 부분 수열의 합 처럼 풀어도 되나요?
23.01.07 18:50 작성 23.01.07 18:53 수정 조회수 386
1
안녕하세요!
저는 이 문제에서 부분 수열의 합을 떠올려서 풀었는데요!
이렇게 풀면 3중 for문의 비해 효율성이 떨어지나요?
이렇게 풀어도 괜찮은지 질문 남김니다.
package algorithmStudy;
import java.util.*;
public class Problem4_5 {
static int n;
static int k;
static int[] arr;
static Set<Integer> answerSet;
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
n= scan.nextInt();
k= scan.nextInt();
arr= new int[n];
for(int i=0;i<n;i++){
arr[i] = scan.nextInt();
}
solution(n,k,arr);
}
private static void solution(int n, int k, int[] arr) {
answerSet = new HashSet<>();
DFS(0,0, 0);
ArrayList<Integer>answer = new ArrayList<>(answerSet);
// System.out.println(answer);
if(answer.size()>k) {
Collections.sort(answer,Comparator.reverseOrder());
System.out.println(answer.get(k-1));
}else System.out.println(-1);
}
private static void DFS(int i, int j, int sum) {
if(j==3) {
answerSet.add(sum);
return;
}
if(i == n){
return;
}
DFS(i+1, j+1, sum+arr[i]);
DFS(i+1, j, sum);
}
}
답변을 작성해보세요.
1
김태원
지식공유자2023.01.08
안녕하세요^^
뽑는 원소가 3개로 정해진 문제같은 경우 굳이 재귀를 돌리기 보다는 3중 for문으로 했으면 합니다.
재귀도 반복문의 일종인데 재귀는 함수이기 때문에 stack에 함수의 지역변수, 매개변수, 복귀주소 등의 정보가 있는 스택프레임을 매 재귀함수마다 생성하는 과정을 거치므로 단순 반복문인 for문 보다 효율성이 좋지 않습니다.
답변 1