링크 → https://www.acmicpc.net/problem/1342

• 아영

  • 코드

  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;
          }
      }
  
  }
  

  • 시간,메모리

  

• 은영

  • 코드

  import java.io.BufferedReader;
  import java.io.IOException;
  import java.io.InputStreamReader;
  
  public class baekjoon1342 {
  
  	static char[] c;
  	static String str;
  	static boolean visit[];
  	static int N,answer=0;;
  	public static void main(String[] args) throws IOException {
  		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
  		str = br.readLine();
  		N = str.length();
  		c = new char[N];
  		visit = new boolean[N];
  		
  		for (int i = 0; i < N; i++) {
  			c[i] = str.charAt(i);
  		}
  		
  		func(' ',0);
  		System.out.println(answer);
  		
  	}
  	private static void func(char start, int cnt) {
  		if(cnt==N) {
  			answer++;
  			return;
  		}
  		int bit=0;
  		for (int i = 0; i < N; i++) {
  			if(!visit[i]) {
  				if(c[i]!=start&& (bit&1<<(c[i]-'a')) == 0) {
  					visit[i] = true;
  					bit|=1<<(c[i]-'a');
  					func(c[i],cnt+1);
  					visit[i] =false;
  				}
  			}
  		}	
  	}
  }
  

  • 시간,메모리

• 건

  • 코드

  package day_0524;
  
  import java.io.BufferedReader;
  import java.io.IOException;
  import java.io.InputStreamReader;
  import java.util.HashSet;
  import java.util.Set;
  
  public class BOJ1342 {
  	
  	static int n;
  	static char[] arr;
  	static char[] isSelected;
  	static boolean[] isVisited;
  	static int answer;
  	
  	public static void main(String[] args) throws IOException{
  		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
  		
  		String input = br.readLine();
  		
  		n = input.length();
  		
  		if (n == 1) {
  			System.out.println(1);
  		}
  		else if (n == 2) {
  			if (input.charAt(0) == input.charAt(1)) {
  				System.out.println(0);
  			} else {
  				System.out.println(2);
  			}
  		} else {
  			arr = new char[n];
  			for (int i = 0; i < n; i++) {
  				arr[i] = input.charAt(i);
  			}
  			
  			isSelected = new char[n];
  			isVisited = new boolean[n];
  			
  			permu(0);
  			
  			System.out.println(answer);
  		}
  	}
  	
  	static void permu(int cnt) {
  		if (cnt == n) {
  			calc();
  			return;
  		}
  		
  		Set<Character> prevChar = new HashSet<>();
  		for (int i = 0; i < n; i++) {
  			if(!isVisited[i] && !prevChar.contains(arr[i])) {
  				isSelected[cnt] = arr[i];
  				isVisited[i] = true;
  				prevChar.add(arr[i]);
  				permu(cnt + 1);
  				isVisited[i] = false;
  			}
  		}
  	}
  	
  	static void calc() {
  		for (int i = 1; i < n - 1; i++) {
  			if (isSelected[i-1] == isSelected[i] || isSelected[i] == isSelected[i + 1]) {
  				break;
  			}
  			
  			if (i == n - 2) {
  				answer++;
  			}
  		}
  	}
  }
  

  • 시간,메모리

  

• 용문

  • 코드

  class BJ1324 {
      
      private var originalString = ""
      private var tempAnswer: [String] = []
      private var answer = 0
      
      private var alphabets: [String : Int] = [ : ]
      private var chars: [String] { originalString.map { String($0) } }
      private var N: Int { originalString.count }
      
      private let startValue = Unicode.Scalar("a").value
      
      func solve() {
          readComponents()
          calc()
          printAnswer()
      }
      
      private func readComponents() {
          originalString = readLine()!
          for char in chars {
              if let count = alphabets[char] {
                  alphabets[char] = count + 1
              } else {
                  alphabets[char] = 1
              }
          }
          tempAnswer = .init(repeating: "", count: N)
      }
      
      private func calc(count: Int = 0) {
          if count == N {
              answer += 1
              return
          }
          
          for key in alphabets.keys {
              let rest = alphabets[key]!
              if rest > 0 {
                  alphabets[key] = rest - 1
                  tempAnswer[count] = key
                  if count != 0, tempAnswer[count - 1] != tempAnswer[count] {
                      calc(count: count + 1)
                  } else if count == 0 {
                      calc(count: count + 1)
                  }
                  tempAnswer[count] = ""
                  alphabets[key] = rest
              }
          }
      }
      
      private func printAnswer() {
          print(answer)
      }
  }
  
  BJ1324().solve()
  

  • 코드 2

  #include <iostream>
  #include <string>
  #include <algorithm>
  using namespace std;
  string origin;
  int res;
  int p[27];
  
  void dfs(int idx, string cur) {
  
  	if (idx == origin.size()) {
  		res++;
  		return;
  	}
  
  	for (int i = 0; i < 26; i++) {
  		if (p[i] == 0) continue;
  		if (cur != "" && cur[cur.size() - 1] == (char)('a' + i)) continue;
  		p[i]--;
  		dfs(idx + 1, cur + (char)('a' + i));
  		p[i]++;
  	}
  }
  
  int main()
  {
  	cin >> origin;
  	for (int i = 0; i < origin.size(); i++)
  		p[origin[i] - 'a']++;
  	
  	dfs(0, "");
  
  	cout << res;
  }
  

  • 시간,메모리 응 시간초과 :) 너무 짜증 ㅎㅎ Swift가 느린가봄; C++ 같은 로직 통과 :)