프로그래머스(올바른 괄호의 개수, 줄 서는 방법) - Java

[올바른 괄호의 개수]

https://programmers.co.kr/learn/courses/30/lessons/12929

코딩테스트 연습 - 올바른 괄호의 갯수

 

* 조건

• 괄호에 대한 쌍의 개수(n)이 주어진다
• 올바른 괄호 형태로 만들 수 있는 경우의 수를 출력한다

 

* 알고리즘

• DP

 

* 로직

• n이 하나씩 증가된다는 것은 ( )를 중심으로 크게 2가지 경우를 나눌 수 있다
  • 괄호 안에 들어가는 경우 ex. (0)
  • 괄호 밖에 있는 경우 ex. ( )0, 0( )
• ex) n=3
  • (f(2)) => f(2)*f(0)
  • (f(1))() => f(1)*f(1)
  • ()f(2) => f(1)*f(2)
• dp[0] = 1로 설정한다 (어차피 곱셈이기 때문에)
• 즉, n의 경우의 수는 서로의 합이 n-1쌍이 되게 성립시키면 구할 수 있게된다
• 이항계수의 개념과 유사하다고 보면 이해하기가 좀 더 나을 수 있다

 

public class Problem_CorrectBracket {

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

    public static int solution(int n) {
        int answer = 0;
        int[] dp = new int[n+1];

        dp[0] = 1;
        dp[1] = 1;
        for(int i=2; i<=n; ++i){
            for(int j=1; j<=i; ++j){
                dp[i] += (dp[i-j] * dp[j-1]);
            }
        }

        return answer = dp[n];
    }
}

 

---

[줄 서는 방법]

https://programmers.co.kr/learn/courses/30/lessons/12936

코딩테스트 연습 - 줄 서는 방법

 

* 조건

• n명의 사람이 줄을 서고 있다
• 줄 서는 방법을 구하고 k 번째에 나열된 경우를 출력한다
• 나열하는 방법은 사전 순이다
  
  

* 알고리즘

• next-permutation은 시간 초과를 유발한다
• permutation을 이용한다
  
  

* 로직

• n명이 존재한다고 할 때, 첫 위치에 숫자를 넣고 해당 숫자가 가질 수 있는 경우의 수는 (n-1)! 이다
• k / (n-1)! 계산 결과가 만약 1이라면, 첫 번째 숫자(사람)에서 고려되는 경우는 모두 지나쳤다는 말이 된다
• 즉, 두 번째 숫자(사람)의 경우에 답이 존재하게 되는 것이고 두 번째 숫자를 첫째 자리에 배치한다
• 배치가 끝나면 해당 숫자를 제거한다
• k = k % (n-1)! 를 통해 그 다음 자리에서 알고 싶은 답안의 위치를 갱신한다
• 위를 반복한다
  
  

 

import java.util.ArrayList;
import java.util.LinkedList;

public class Problem_HowToLineUp_ {
    public static void main(String[] args) {
        int n = 3;
        int k = 5;
        int[] answers = solution(n, k);
        for(int ans : answers)
            System.out.print(ans + " ");
    }

    public static int[] solution(int n, long k) {
        int[] answer;
        LinkedList<Integer> lists = new LinkedList<>();
        for(int i=1; i<=n; ++i){
            lists.add(i);
        }

        k--;
        int size = n;
        ArrayList<Integer> arrayList = new ArrayList<>();
        while (size > 0){
            long factorial = doFactorial(size - 1);
            int index = (int) (k / factorial);
            Integer value = lists.remove(index);
            arrayList.add(value);

            k = k % factorial;
            size--;
        }

        answer = new int[arrayList.size()];
        for(int i=0; i<answer.length; ++i){
            answer[i] = arrayList.get(i);
        }

        return answer;
    }

    private static long doFactorial(int n) {
        if(n <= 1){
            return 1;
        }
        return n * doFactorial(n-1);
    }
}

 

 

조금씩 dp 문제인지 무엇을 요구하는지를 알아가는 것 같다. 특히 [올바른 괄호 개수] 문제의 경우, 접근은 유사하게 했지만 같이 문제를 푼 형이 이항 정리에서 착안하여 규칙을 만들어 냈던 순간은 인상적이었다. 형은 항상 그 다음 상황에서 어떤 상황이 추가되는지를 먼저 생각하고 거꾸로 풀어나가는 방식을 고민했는데 이번에도 이를 통해 도출해냈다.

 

나는 형의 접근방식을 생각해보면서 풀려고 노력하지만 아직 많이 부족해 보인다. 그래도 계속 반복하고 풀어보면서 조금씩 감이 생기는거 같지만 접근만 한다고 문제를 푸는 것은 아니니까 좀 더 노력해서 규칙을 찾고 짜릿함도 좀 더 느끼고 싶다.