순열 관련 문제

김민지·2023년 1월 5일

코딩테스트

목록 보기

12/31

순서가 다르면 다른것

 public static void func(int n, int m, int idx, int depth, String str){
        if(depth == m){
            System.out.println(str);
            return;
        }
        for(int i=1;i<=n;i++){
            if(!isPrinted[i]){
                isPrinted[i] = true;
                if(!str.isEmpty()) func(n,m,i+1, depth+1, str + " " + i);
                else func(n,m,i+1, depth+1, "" + i);
                isPrinted[i] = false;
            }

        }

    }

출력문

1 2
1 3
1 4
2 1
2 3
2 4
3 1
3 2
3 4
4 1
4 2
4 3

순서가 달라도 숫자가 같으면 같은것

오름차순으로 고르기만 하는것

 public static void func(int n, int m, int idx, int depth, String str){
        if(depth == m){
            System.out.println(str);
            return;
        }
        for(int i=idx;i<=n;i++){
                if(!str.isEmpty()) func(n,m,i+1, depth+1, str + " " + i);
                else func(n,m,i+1, depth+1, "" + i);


        }

    }

출력문

1 2
1 3
1 4
2 3
2 4
3 4

차이

isPrinted[i] 의 유무
for문이 1부터 시작하느냐 idx부터 시작하느냐의 차이

조합관련문제 16439

import java.io.*;
import java.lang.reflect.Array;
import java.util.*;
import java.util.stream.Collectors;

public class Main{
    static int n;
    static int m;
    static int favorites[][];
    static boolean visited[];
    static ArrayList<Integer> list = new ArrayList<>();
    static int max = 0;
    public static int getFavorites(ArrayList<Integer> list){
        int sum = 0;
        for(int i=0;i<n;i++){
            int personMax = 0;
            for(Integer item:list){
                personMax = Math.max(personMax,favorites[i][item]);
            }
            sum+= personMax;
        }
        return sum;
    }
    public static void dfs(int depth, int idx){
        if(list.size()==3) {
            max = Math.max(max, getFavorites(list));
            return;
        }
        for(int i=idx;i<m;i++){
            list.add(i);
            int idx1 = list.size()-1;
            dfs(depth+1, i+1);
            list.remove(idx1);
        }

    }
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        String str[] = br.readLine().split(" ");
        n = Integer.parseInt(str[0]);
        m = Integer.parseInt(str[1]);
        favorites = new int[n][m];
        visited = new boolean[m];
        for(int i=0;i<n;i++){
            String input[] = br.readLine().split(" ");
            for(int j=0;j<m;j++){
                favorites[i][j] = Integer.parseInt(input[j]);
            }
        }
        for(int i=0;i<m;i++){
            visited = new boolean[m];
            list.clear();
            dfs(0,i);
        }
        bw.write(max+"");
        bw.flush();
        bw.close();
    }
}

중복포함한 조합 - 17626

Four Squares

왜 이런차이만 두면 다른 코드를 만들 수 있을까?

for문이 idx부터 시작하고, idx는 매번 재귀호출때 +1을해준다. 그렇기때문에 1부터 n까지 재귀호출을 할때 매번 자기보다 큰 것들에 대해서만 출력한다. 이 말은 자기보다 이전것은 보지 않겠다는 의미이다. 자기보다 큰값만을 선택하게 된다면, 자연스럽게 하나의 출력문에 들어있는 숫자를 모두 다르게 선택할 수 있게 된다. 이부분이 그렇게 잘 이해가는 부분이 아니긴 하다.
isPrinted는 한번씩만 선택돼야한다는 순열의 조건을 맞춰준다
-> 이를 도와주기위해서는 이미 출력되었다는것을 알려줄 변수가 필요하다
isPrinted는 재귀함수를 끝내고서는 false를 넣어준다. 이 이유는 무엇인가?
parameter인 str은 i가 없는 str이다. 그러니까 결국 다음for문이 동작하고, i=2로 들어가서 재귀함수를 호출할떄 그 재귀함수에서는 지금 i에 접근할 수 있어야한다. 왜냐면 지금 str은! i를 출력하지 않았으니까! 그런부분을 고려하여 false처리를 해주었다