알고리즘(단체사진 찍기, 올바른 괄호, 다음 큰 숫자)

[단체사진 찍기]

 

* 로직

• 8명을 일렬로 세우는 경우의 수를 구한다
• 경우의 수가 구해질 때마다 data[] 질문에 대해 모두 만족하는지를 판단한다
• 만족 한다면 답을 카운팅한다

 

// 단체사진 찍기
import java.util.LinkedList;

public class Problem_GroupPhoto {
    static int Size = 8;    // 줄을 서는 캐릭터의 수
    static String[] Members = {"A", "C", "F", "J", "M", "N", "R", "T"};
    static boolean[] checked;
    static int result;

    public static void main(String[] args) {
        int n = 2;
        String[] data = {"N~F=0", "R~T>2"};
        int answer = solution(n, data);
        System.out.println(answer);
    }

    public static int solution(int n, String[] data) {
        int answer = 0;
        result = 0;

        // 순열 구하기
        checked = new boolean[Size];
        int r = Size;
        LinkedList<String> pathList = new LinkedList<>();
        doProcess(r, n, data, pathList);

        return answer = result;
    }

    private static void doProcess(int r, int n, String[] data, LinkedList<String> pathList) {
        if(r == 0) {
            // 질문에 모두 만족하는지 판별
            StringBuilder sb = new StringBuilder();
            for(String list : pathList) {
                sb.append(list);
            }

            if(isPossible(n, data, sb)) {
                result++;
            }
            return;
        }

        for(int i=0; i<Size; ++i) {
            if(!checked[i]) {
                checked[i] = true;
                pathList.add(Members[i]);

                doProcess(r-1, n, data, pathList);

                pathList.removeLast();
                checked[i] = false;
            }
        }
    }

    private static boolean isPossible(int n, String[] data, StringBuilder sb) {
        for(String input : data) {
            String member1 = input.substring(0, 1);
            String member2 = input.substring(2, 3);
            String operation = input.substring(3, 4);
            int num = Integer.parseInt(input.substring(4, 5));

            int idx_member1 = sb.indexOf(member1);
            int idx_member2 = sb.indexOf(member2);
            int sub = idx_member1 >= idx_member2 ? (idx_member1 - idx_member2)-1 : (idx_member2 - idx_member1)-1;

            if(operation.equals("=")) {
                if(sub != num) return false;
            }
            else if(operation.equals(">")) {
                if(sub <= num) return false;
            }
            else if(operation.equals("<")) {
                if(sub >= num) return false;
            }
        }

        return true;
    }
}

 

 

[올바른 괄호]

 

* 로직

• 주어진 문자열 길이만큼 탐색하면서
  • 열린 괄호라면 -> cnt++
  • 닫힌 괄호라면
    • 만약 cnt가 0인 경우에는 닫힌 괄호가 먼저 나왔다는 의미이기 때문에 false
    • cnt가 1 이상인 경우에는 -> cnt--
• 탐색이 끝난 후 cnt가 1개 이상 있다면 괄호의 짝이 맞지 않기때문에 false
• 모두 만족한다면 true를 리턴한다

 

// 올바른 괄호
public class Problem_CorrectBracket {

    public static void main(String[] args) {
        String s = "(())()";
        boolean answer = solution(s);
        System.out.println(answer);
    }

    private static boolean solution(String s) {
        boolean answer = true;

        int cnt = 0;
        for(int i=0; i<s.length(); ++i) {
            if(s.substring(i, i+1).equals("(")) {
                cnt++;
            }
            else if(s.substring(i, i+1).equals(")")) {

                // 여는 괄호가 존재하지 않는다면
                if(cnt == 0) return false;

                cnt--;
            }
        }

        // 스택에 여는 괄호가 남아있다면
        if(cnt > 0) return false;

        return answer;
    }
}

 

[다음 큰 숫자]

 

* 로직

• n을 이진수로 변환했을 때 1의 개수를 구해놓는다
• 마찬가지로 n+1부터 1000000까지 수를 이진화 및 1의 개수를 구해나간다
• 만약 1의 개수가 서로 같아진 경우에는 답을 출력한다

 

// 다음 큰 숫자 
public class Problem_NextBigNum {

    public static void main(String[] args) {
        int n = 78;
        int answer = solution(n);
        System.out.println(answer);
    }

    public static int solution(int n) {
        int answer = 0;
        int cnt_n = getCount(n);

        for(int num=n+1; num<=1000000; ++num) {
            int cnt_num = getCount(num);
            if(cnt_n == cnt_num) {
                answer = num;
                break;
            }
        }

        return answer;
    }

    private static int getCount(int n) {
        int cnt=0;
        while (n != 0) {
            if(n % 2 == 1){
                cnt++;
            }
            n /= 2;
        }
        return cnt;
    }
}