인프런 커뮤니티 질문&답변
작성한 질문수
8-6 순열구하기 이러한 방식으로 풀어도 괜찮을까요?
작성
·
226
0
이전 값을 DFS 매개변수로 넘겨서 이전값이 아니면 더 깊이 들어가는 방식으로 풀이를 혼자 했었습니다. 괜찮은 풀이 방법일까요?
public class P6_순열 {
static int n, m;
static int[] arr;
public static void DFS(int L, int prev, String answer) {
if(L==m){
System.out.println(answer);
}else{
for(int i=0; i<n; i++){
if(arr[i]!=prev) DFS(L+1, arr[i], answer+arr[i]+" ");
}
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
n=sc.nextInt();
m=sc.nextInt();
arr=new int[n];
for(int i=0; i<n; i++){
arr[i]=sc.nextInt();
}
DFS(0,0,"");
}
}
답변 2
1
안녕하세요^^
순열이 만들어지지 않는 코드입니다.
위 코드는 바로 전 레벨에서 선택된 값의 중복만 제거하지 그 전전 레벨들에서 선택한 값의 중복을 체크하지 못합니다.
5 3
1 2 3 4 5
를 입력해서 테스트해보세요.
0
안녕하세요, 인프런 AI 인턴입니다.
님의 질문에 대한 답변입니다.
순열 문제를 푸는 방식은 다양하며, 님께서 공유해주신 DFS를 활용한 접근 방식도 유효한 풀이 방법 중 하나입니다. 다만, 제시된 코드는 중복을 허용하지 않는 순열을 구할 때 사용할 수 있는 방식이며, 더 정확한 순열 구하기를 위해서는 선택한 번호를 체크하고 체크를 해제하는 과정이 포함되어야 합니다.
제시된 코드에는 prev라는 변수를 사용하여 이전 값과 다른 값을 선택하는 조건을 달아줌으로써 중복을 방지하고 있습니다. 이 방법은 간단하게 순열을 구현하는 데 도움이 될 수 있지만, 모든 순열을 정확하게 생성하는지는 입력된 배열의 순서와 값에 따라 결과가 달라질 수 있습니다. 예를 들어, 순서가 정렬된 상태의 배열이나 모든 원소가 서로 다를 때에는 원하는 결과를 얻을 수 있지만, 그렇지 않은 경우에는 일부 순열을 놓칠 가능성이 있습니다.
더 포괄적이고 정확한 순열 생성을 위해서는 방문 여부를 체크하는 별도의 배열을 사용하거나, prev 값을 확인하지 않고 순서에 따라 모든 가능성을 탐색하며 중복을 제거하는 방식으로 접근할 수 있습니다.
프로그래밍에서는 다양한 접근 방법이 존재하며, 풀이의 정확성과 효율성을 바탕으로 견고하고 최적화된 코드를 작성하는 것이 중요합니다. 님의 방식이 해당 문제 상황에 적절하게 작동한다면 좋은 접근이 될 수 있습니다. 다만, 위에서 언급한 점들을 고려하여 코드를 개선할 여지가 있는지 확인해 보시길 추천드립니다.
감사합니다!