[BJ]1342. 행운의 문자열

BJ S1 1342 행운의 문자열

 

 

문제링크

https://www.acmicpc.net/problem/1342

1342번: 행운의 문자열

* 일단 문제를 정독 하고 1시간 이상 반드시 고민이 필요합니다.

 

동영상 설명

1시간 이상 고민 했지만 아이디어가 떠오르지 않는다면 동영상에서 약간의 힌트를 얻어봅시다.

https://youtu.be/LIBUyTyZ-F0

 

 

소스보기

동영상 설명을 보고도 전혀 구현이 안된다면 연습 부족입니다.
소스를 보고 작성해 본 후 스스로 백지 상태에서 3번 작성해 볼 의지가 있다면 소스를 살짝 보세요.

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

/**
 * @author 은서파
 * @since 2022/08/14
 * @see https://www.acmicpc.net/problem/1342
 * @git 
 * @youtube  
 * @performance  11756	236  12628	148
 * @category #
 * @note 
 */

public class BJ_S1_01342_행운의문자열{
    private static BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
    private static StringBuilder output = new StringBuilder();
    private static StringTokenizer tokens;

    private static char [] chars;
    private static int A;
    private static int [] cnts;
    private static int [] facts;
    public static void main(String[] args) throws IOException {
        input = new BufferedReader(new StringReader(src));
        chars = input.readLine().toCharArray();
        //byNormalPermutation();

        Arrays.sort(chars);
        do{
            if(isLucky()){
                A++;
            }
        }while(nextPermutation());
        System.out.println(A);
    }

    static boolean isLucky(){
        for(int i=0; i<chars.length-1; i++){
            if(chars[i]==chars[i+1]){
                return false;
            }
        }
        return true;
    }

    static boolean nextPermutation(){
        // 최초의 하향 변곡점을 찾는다. - 뒤의 값이 앞의 값보다 더 커야 한다.
        int firstPeak = chars.length-1;
        while(firstPeak>0 && chars[firstPeak-1]>=chars[firstPeak]){
            firstPeak--;
        }
        // firstPeak==0인 상황은 맨 마지막 위치
        if(firstPeak==0){
            return false;
        }
        // 하향 변곡점의 앞에 있는 요소(firstPeak-1)와 위치를 바꿀 녀석 찾기. firstPeak-1의 값보다 큰 녀석
        int gtBeforeFirstBeak = chars.length-1;
        while(chars[firstPeak-1]>=chars[gtBeforeFirstBeak]){
            gtBeforeFirstBeak--;
        }
        swap(firstPeak-1, gtBeforeFirstBeak);
        // firstPeak에서 맨 뒤까지 뒤집어주기
        for(int l=firstPeak, r=chars.length-1; l<r; l++, r--){
            swap(l, r);
        }
        return true;
    }

    static void swap(int a, int b){
        char temp = chars[a];
        chars[a] = chars[b];
        chars[b] = temp;
    }

    static void byNormalPermutation(){
        cnts = new int[26];
        for(int i=0; i<chars.length; i++){
            cnts[chars[i]-'a']++;
        }
        facts = new int[chars.length+1];
        facts[1]=1;
        for(int i=2; i<facts.length; i++){
            facts[i] = facts[i-1]*i;
        }

        makePermutation(0, new boolean[chars.length], 'A');

        for(int i=0; i<cnts.length; i++){
            if(cnts[i]>1){
                A/=facts[cnts[i]];
            }
        }

        System.out.println(A);
        //long total = Runtime.getRuntime().totalMemory();
        //long free = Runtime.getRuntime().freeMemory();
        //System.out.println("used: " +((total-free)/1024/1024));
    }

    static void makePermutation(int nth, boolean [] visited, char pre){
        if(nth==chars.length){
            //System.out.println(Arrays.toString(choosed));
            //set.add(String.valueOf(choosed)); // 메모리 초과 발생 : 생성한 문자열이 너무 많다.
            A++;
            return;
        }

        for(int i=0; i<chars.length; i++){
            if(!visited[i]){
                visited[i]=true;
                if(pre!=chars[i]){
                    makePermutation(nth+1, visited, chars[i]);
                }
                visited[i]=false;
            }
        }
    }

    // REMOVE_START
    private static String src = "abcdefghij";
    // REMOVE_END
}