• 카테고리

    질문 & 답변
  • 세부 분야

    알고리즘 · 자료구조

  • 해결 여부

    미해결

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

24.03.03 22:20 작성 조회수 83

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

를 입력해서 테스트해보세요.

박주영님의 프로필

박주영

질문자

2024.03.21

감사합니다!

0

인프런 AI 인턴님의 프로필

인프런 AI 인턴

2024.03.05

안녕하세요, 인프런 AI 인턴입니다.

님의 질문에 대한 답변입니다.

순열 문제를 푸는 방식은 다양하며, 님께서 공유해주신 DFS를 활용한 접근 방식도 유효한 풀이 방법 중 하나입니다. 다만, 제시된 코드는 중복을 허용하지 않는 순열을 구할 때 사용할 수 있는 방식이며, 더 정확한 순열 구하기를 위해서는 선택한 번호를 체크하고 체크를 해제하는 과정이 포함되어야 합니다.

제시된 코드에는 prev라는 변수를 사용하여 이전 값과 다른 값을 선택하는 조건을 달아줌으로써 중복을 방지하고 있습니다. 이 방법은 간단하게 순열을 구현하는 데 도움이 될 수 있지만, 모든 순열을 정확하게 생성하는지는 입력된 배열의 순서와 값에 따라 결과가 달라질 수 있습니다. 예를 들어, 순서가 정렬된 상태의 배열이나 모든 원소가 서로 다를 때에는 원하는 결과를 얻을 수 있지만, 그렇지 않은 경우에는 일부 순열을 놓칠 가능성이 있습니다.

더 포괄적이고 정확한 순열 생성을 위해서는 방문 여부를 체크하는 별도의 배열을 사용하거나, prev 값을 확인하지 않고 순서에 따라 모든 가능성을 탐색하며 중복을 제거하는 방식으로 접근할 수 있습니다.

프로그래밍에서는 다양한 접근 방법이 존재하며, 풀이의 정확성과 효율성을 바탕으로 견고하고 최적화된 코드를 작성하는 것이 중요합니다. 님의 방식이 해당 문제 상황에 적절하게 작동한다면 좋은 접근이 될 수 있습니다. 다만, 위에서 언급한 점들을 고려하여 코드를 개선할 여지가 있는지 확인해 보시길 추천드립니다.