[BOJ] 9742. 순열 (python / java)

백준 9742. 순열 (파이썬 / 자바)

9742번: 순열

 

파이썬

EOF 어떻게하는지 아주 까먹었었다

입력이 정렬되어 주어져서 순열 구현만 하고 카운트만 제대로 해 주면 됨

def perm(r):
    global cnt
    if r == len(a):
        cnt += 1
        if cnt == int(b):
            print(''.join(selected))
            return

    for i in range(len(a)):
        if visited[i]:
            continue
        selected[r] = a[i]
        visited[i] = True
        perm(r + 1)
        visited[i] = False


while 1:
    try:
        a, b = input().split()
        selected = [''] * len(a)
        visited = [0] * len(a)
        cnt = 0

        maximum = 1
        for i in range(1, len(a) + 1):
            maximum *= i

        if int(b) > maximum:
            print(a, b,  '= No permutation')
        else:
            print(a, b, "= ", end="")
            perm(0)

    except:
        break

 

자바

split에 strinbuilder에 열심히 뜯고 붙임

알고리즘 풀때 타입 진짜 귀찮고 슬프다

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

public class Main {
    static String[] arr;
    static int cnt = 0;
    static int R;
    static int[] selected;
    static boolean[] isSelected;
    static void perm(int r, int N) {
        if (r == R) {
            cnt++;
            if (cnt == N) {
                for (int i = 0; i < R; i++) System.out.print(arr[selected[i]]);
                System.out.println();
                return;
            }
        }

        for (int i = 0; i < arr.length; i++) {
            if (isSelected[i]) continue;
            isSelected[i] = true;
            selected[r] = i;
            perm(r + 1, N);
            isSelected[i] = false;
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String input = "";

        while ((input = br.readLine()) != null && input.length() != 0) {
            StringBuilder stringBuilder = new StringBuilder();
            cnt = 0;
            String[] split = input.split(" ");
            arr = split[0].split("");
            for (String a : arr) {
                stringBuilder.append(a);
            }
            stringBuilder.append(" ");
            stringBuilder.append(split[1]);
            stringBuilder.append(" = ");
            int N = Integer.parseInt(split[1]); // n번째 순열 찾기
            R = arr.length;

            selected = new int[arr.length];
            isSelected = new boolean[arr.length];

            int fac = 1;
            for (int i = 1; i <= R; i++) {
                fac *= i;
            }

            System.out.print(stringBuilder);
            if (N <= fac) {
                perm(0, N);
            }
            else {
                System.out.println("No permutation");
            }
        }
        br.close();
    }
}