[카카오 기출 문제]단체사진찍기- 레벨 2, BFS + 순열 + 문자열

https://school.programmers.co.kr/learn/courses/30/lessons/1835

프로그래머스

 

이번 문제는 다양한 함수를 겪어서 정리할게 많습니다.

 

기억해야할점들

-순열구하는공식은 이전에 배운적이 있어서 바로 적용했습니다.

 

-String.indexOf를 사용하여 문자에서 해당 위치를 찾은뒤 기준 단어와 비교할 단어의 거리를 계산하면 몇배는 빠르게 코딩할 수 있습니다. 이전에는 for문으로 직접 다 셌는데 무조건 이렇게 해야 빠르게합니다.

그리고 여기서 distance + 1을 하는 이유는 칸이 1개 차이라면 A _ F 입니다. 즉 Math.abs(standard-compare)을 하면 한칸차이라도 index 상으로는 2칸차이이니 distnace+1을 하는 것입니다. 

 

-Arrays.toString(String[]) 배열을 사용할때

{"A", "B", "C"} 가 있다면 return 값은 [A , B , C ] 이렇게 리턴됩니다.. 이걸 그냥 출력형식이라고 생각한것이 잘못입니다.

String output_str = Arrays.toString(output).replaceAll(",| |\\]|\\[",""); 이렇게 해야 ABC 가 나오는데 이렇게하면 40000건에 대하여 모두 replaceAll을 시전하므로 시간초과가 나서 String[] 배열을 함수 인자에 넣고 돌리거나 마지막에 배열값만큼 새로 추가하는 방법밖에 없습니다.

와.. 이걸 몰라서 몇시간을;;

 

 

 

import java.io.*;
import java.util.*;
import java.util.Map.*;
class Solution {
    
    String[] teammember = {"A", "C", "F", "J", "M", "N", "R", "T"};
    String[] output = new String[8];
    boolean[] visited = new boolean[8];
        int answer = 0;
    String[] datatemp;
    public int solution(int n, String[] data) {
        datatemp = data;
        permutation(8, 0);
        return answer;
    }
    
    public boolean solve(String permutation_str){
        for(int i=0;i<datatemp.length;i++){
            //data값 정리
            String operand = String.valueOf(datatemp[i].charAt(3));
            int distance = Integer.parseInt(String.valueOf(datatemp[i].charAt(4)));
 
            //실제연산시작
            int standardposition = permutation_str.indexOf(datatemp[i].charAt(0));
            int compareposition = permutation_str.indexOf(datatemp[i].charAt(2));
            
            if(operand.equals("=")){
                if( (Math.abs(standardposition - compareposition) == distance+1) == false ) return false;
            }else if(operand.equals(">")){
                if( (Math.abs(standardposition - compareposition) > distance+1) == false) return false;           
            }else if(operand.equals("<")){
                if( (Math.abs(standardposition - compareposition) < distance + 1) == false) return false;          
            } 
      
                
            }   
        return true;
    }
    
    public void permutation(int r, int current){
        if(r == current){
            //여기서 output을 string으로 변환한뒤?? data의 조건들을 만족시킨다면 continue, 하나라도 만족안한다면 바로 boolean return false;
            // String output_str = Arrays.toString(output).replaceAll(",| |\\]|\\[","");
            
            String str = "";
            for(int i=0;i<8;i++)
                str += output[i];
            if(solve(str) == true){
                answer+=1;
            }
            return ;
        }
        for(int i=0;i<r;i++){
            if(visited[i] == false){
                visited[i] = true;
                output[current] = teammember[i];
                permutation(r, current+1);
                visited[i] = false;
            }
        }
    }
    
    // public void permutation(int r, int current, String str){
    //     if(r == current){
    //         //여기서 output을 string으로 변환한뒤?? data의 조건들을 만족시킨다면 continue, 하나라도 만족안한다면 바로 boolean return false;
    //         // String output_str = Arrays.toString(output).replaceAll(",| |\\]|\\[","");
    //         if(solve(str) == true){
    //             answer+=1;
    //         }
    //         return ;
    //     }
    //     for(int i=0;i<r;i++){
    //         if(visited[i] == false){
    //             visited[i] = true;
    //             // output[current] = teammember[i];
    //             permutation(r, current+1, str + teammember[i]);
    //             visited[i] = false;
    //         }
    //     }
    // }
}