boj1342 행운의 문자열

dgh03207·2022년 5월 25일
0

알고리즘

목록 보기
39/45

링크

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

문제

민식이와 준영이는 자기 방에서 문자열을 공부하고 있다. 민식이가 말하길 인접해 있는 모든 문자가 같지 않은 문자열을 행운의 문자열이라고 한다고 한다. 준영이는 문자열 S를 분석하기 시작했다. 준영이는 문자열 S에 나오는 문자를 재배치하면 서로 다른 행운의 문자열이 몇 개 나오는지 궁금해졌다. 만약 원래 문자열 S도 행운의 문자열이라면 그것도 개수에 포함한다.

입력

첫째 줄에 문자열 S가 주어진다. S의 길이는 최대 10이고, 알파벳 소문자로만 이루어져 있다.

출력

첫째 줄에 위치를 재배치해서 얻은 서로 다른 행운의 문자열의 개수를 출력한다.

나의 풀이

  • https://chosh95.tistory.com/486 참고코드
  • 계속해서 메모리초과가 떠서 코드를 참고하였다. 알파벳만 나오기 때문에 int 배열로 a부터 z까지의 알파벳의 아스키 코드 순서대로 개수를 체크하였고, 이 조합을 dfs로 N개의 조합을 만들었고, 만들어진 개수를 세어 마지막에 출력시켰다.
  • 핵심 코드
        private static void dfs(int cnt,String result){
            if(cnt==N){
                answer+=1;
                return;
            }
    
            for (int i = 0; i < 26; i++) {
                if(chars[i]==0) continue;
                if(result!=""&&result.charAt(cnt-1)==(char)('a'+i)) continue;
    
                chars[i]-=1;
                dfs(cnt+1,result+(char)(i+'a'));
                chars[i]+=1;
            }
        }
  • 전체 코드
    package Baekjoon.java.silver;
    
    import java.io.BufferedReader;
    import java.io.InputStreamReader;
    import java.nio.Buffer;
    import java.util.ArrayList;
    import java.util.List;
    
    public class boj1342 {
        static int N;
        static int answer;
        static int[] chars;
        static List<String> answers;
        public static void main(String[] args) throws Exception{
            BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
            char[] S = br.readLine().toCharArray();
            N = S.length;
            chars = new int[26];
            answers = new ArrayList<>();
            for (int i = 0; i < S.length; i++) {
                chars[S[i]-'a']+=1;
            }
    
            dfs(0,"");
            System.out.println(answer);
        }
        private static void dfs(int cnt,String result){
            if(cnt==N){
                answer+=1;
                return;
            }
    
            for (int i = 0; i < 26; i++) {
                if(chars[i]==0) continue;
                if(result!=""&&result.charAt(cnt-1)==(char)('a'+i)) continue;
    
                chars[i]-=1;
                dfs(cnt+1,result+(char)(i+'a'));
                chars[i]+=1;
            }
        }
    
    }

결과

profile
같이 공부하자!

0개의 댓글