8-6 순열구하기 이러한 방식으로 풀어도 괜찮을까요?

Question

이전 값을 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,""); } }

김태원 · Answer

안녕하세요^^ 순열이 만들어지지 않는 코드입니다. 위 코드는 바로 전 레벨에서 선택된 값의 중복만 제거하지 그 전전 레벨들에서 선택한 값의 중복을 체크하지 못합니다. 5 3 1 2 3 4 5 를 입력해서 테스트해보세요.

인프런 AI 인턴 · Answer

안녕하세요, 인프런 AI 인턴입니다. 님의 질문에 대한 답변입니다. 순열 문제를 푸는 방식은 다양하며, 님께서 공유해주신 DFS 를 활용한 접근 방식도 유효한 풀이 방법 중 하나입니다. 다만, 제시된 코드는 중복을 허용하지 않는 순열을 구할 때 사용할 수 있는 방식이며, 더 정확한 순열 구하기를 위해서는 선택한 번호를 체크하고 체크를 해제하는 과정이 포함되어야 합니다. 제시된 코드에는 prev 라는 변수를 사용하여 이전 값과 다른 값을 선택하는 조건을 달아줌으로써 중복을 방지하고 있습니다. 이 방법은 간단하게 순열을 구현하는 데 도움이 될 수 있지만, 모든 순열을 정확하게 생성하는지는 입력된 배열의 순서와 값에 따라 결과가 달라질 수 있습니다. 예를 들어, 순서가 정렬된 상태의 배열이나 모든 원소가 서로 다를 때에는 원하는 결과를 얻을 수 있지만, 그렇지 않은 경우에는 일부 순열을 놓칠 가능성이 있습니다. 더 포괄적이고 정확한 순열 생성을 위해서는 방문 여부를 체크하는 별도의 배열을 사용하거나, prev 값을 확인하지 않고 순서에 따라 모든 가능성을 탐색하며 중복을 제거하는 방식으로 접근할 수 있습니다. 프로그래밍에서는 다양한 접근 방법이 존재하며, 풀이의 정확성과 효율성을 바탕으로 견고하고 최적화된 코드를 작성하는 것이 중요합니다. 님의 방식이 해당 문제 상황에 적절하게 작동한다면 좋은 접근이 될 수 있습니다. 다만, 위에서 언급한 점들을 고려하여 코드를 개선할 여지가 있는지 확인해 보시길 추천드립니다.