CODEKATA 81 ~ 85

81번 N개의 최소공배수

/*
문제 분석
1. 정보
    - 두 수의 최소공배수란 입력된 두 수의 배수중 공통이 되는 가장 작은 숫자를 의미함.
        - 예를 들어 2와 7의 최소 공배수는 14가 된다.
    - N개의 수의 최소공배수는 N 개의 수들의 배수 중 공통이 되는 가장 작은 숫자가 됨.
2. 목표
    - N개의 숫자가 배열로 입력되었을 때, 이 수들의 최소공배수를 return
3. 제약 조건
    - 1 <= N <= 15
    - 수 <= 100

풀이
1. 아이디어
    - 두 수의 최소 공배수 = 두 숫자의 곱 / 최대 공약수
    - 들어온 배열은 arr
    - arr[0]과 arr[1]의 최소 공배수를 구함
    - 이후 arr[2]부터 이전에 구한 최소 공배수와 최대 공약수를 구하여 최소 공배수를 업데이트함
    - 배열 끝까지 업데이트 한 후 마지막 최소 공배수를 return
        - EX) 2 6 8 14
            - 1. 2와 6의 최소 공배수 = 2 * 6 / 2 = 6
            - 2. 6과 8의 최소 공배수 = 6 * 8 / 2 = 24
            - 3. 24와 14의 최소 공배수 = 24 * 14 / 2 = 168
            - 168 return
*/

class Solution {
        public int solution(int[] arr) {
            int answer = 0;
            if (arr.length == 1) {
                return arr[0];
            }
            answer = arr[0] * arr[1] / GCD(arr[0], arr[1]);
            for (int i = 2; i < arr.length; i++) {
                answer = answer * arr[i] / GCD(answer, arr[i]);
            }
            return answer;
        }

        public int GCD(int a, int b) {
            if (b == 0) {
                return a;
            }
            return GCD(b, a % b);
        }
    }

82번 멀리 뛰기

/*
문제 분석
1. 정보
    - 효진이는 한번에 1칸 또는 2칸을 뛸 수 있음.
        - 예를 들어, 칸이 4개 있을 경우
            - 1,1,1,1
            - 1,2,1
            - 1,1,2
            - 2,1,1
            - 2,2
            - 총 5가지의 방법으로 도달 가능

2. 목표
    칸의 수 N이 주어질 때, 끝에 도달하는 방법의 수를 1234567로 나눈 나머지를 return

3. 제약 조건
    - 1 <= N <= 2000

풀이
1. 아이디어
    - DP 사용
        - dp[i] : i번째 칸에 도착하는 경우의 수
        - dp[i] = dp[i - 1] + dp[i - 2] 임
        - 마지막에 dp[N]을 출력

*/

class Solution {
        public long solution(int n) {
            if (n == 1) {
                return 1;
            }
            long dp[] = new long[n + 1];
            dp[0] = 0;
            dp[1] = 1;
            dp[2] = 2;
            for (int i = 3; i <= n; i++) {
                dp[i] = (dp[i - 1] + dp[i - 2]) % 1234567;
            }
            return dp[n];
        }
    }

83번 귤 고르기

/*
문제 분석
1. 정보
    - 수확한 귤 중 K개를 골라 상자 하나에 담아 판매하려고 함
    - 하지만 수확한 귤의 크기가 일정하지 않아 귤을 크기별로 분류했을 때 서로 다른 종류의 수를 최소화 하고 싶음
        - 예를들어
            - 수확한 귤 8개의 크기가 1,3,2,5,4,5,2,3 이라고 가정
            - 귤 6개를 판매하고 싶다면, 크기가 1, 4인 귤을 제외한 6개의 귤을 상자에 담으면 귤의 크기의 종류가 2,3,5로 총 3가지가 되며, 이때가 서로 다른 종류가 최소가 되는 경우
2. 목표
    - 귤 k를 고를 때 서로 다른 종류의 수의 최솟값을 return

3. 제약 조건
    - 1 <= k <= 귤의 개수 <= 100000
    - 1 <= 귤의 크기 <= 10,000,000

풀이
1. 아이디어
    - 입력 받은 tangerine을 사용해 Map<Integer,Integer>생성
        - 해당 Map에는 귤의 크기와 해당 귤의 개수를 저장
    - 모든 귤을 저장하고, 귤의 개수 내림차순으로 정렬
    - k개가 될때 까지 귤을 뽑고, k개보다 크거나 같아진다면
        - 귤의 종류의 개수를 return
*/

import java.util.*;

class Solution {

        public int solution(int k, int[] tangerine) {
            Map<Integer, Integer> list = new HashMap<>();
            for (int cur : tangerine) {
                if (list.containsKey(cur)) {
                    list.compute(cur, (key, amount) -> amount + 1);
                }else{
                    list.put(cur, 1);
                }
            }

            List<Integer> listKeySet = new ArrayList<>(list.keySet());

            Collections.sort(listKeySet, (v1, v2) -> list.get(v2).compareTo(list.get(v1)));
            int sum = 0;
            int answer = 0;
            for (Integer cur : listKeySet) {
                if (sum >= k) {
                    break;
                }
                sum += list.get(cur);
                answer++;
            }
            return answer;
        }
    }

84번 괄호 회전하기

/*
문제 분석
1. 정보
    - 다음 규칙을 지키는 문자열을 올바른 괄호 문자열이라고 정의
        - (), [], {} 는 모두 올바른 괄호 문자열
        - [()] 도 올바른 괄호 문자열이 될 수 있음
        - {}([]) 도 올바른 괄호 문자열이 될 수 있음
2. 목표
    - 대괄호 중괄호 소괄호로 이루어진 문자열 S가 매개변수로 주어짐
    - S를 왼쪽으로 X 칸 만큼 회전시켰을 때, S가 올바른 괄호 문자열이 되게 하는 X의 개수를 return
3. 제약 조건
    - 1 <= s의 길이 <= 1000

풀이
1. 아이디어
    - 최대 길이는 1000
        - 1000번 * 1000의 길이 = 100만
        - for문 사용해도 시간초과 안날 것이라 생각
    - for문을 사용해 시작 지점을 정함
        - while문을 사용해 다시 시작지점이 될때 까지 stack에 해당 값을 집어 넣음
            - 이때, stack에 집어 넣으면서, 이전 괄호와 현재 넣은 괄호가 짝이라면 stack에서 제거
        - while문 이후에 stack에서 모두 제거를 했는데도 값이 남아 있다면, 만들 수 없는 것.
        - stack이 비어있다면 만들 수 있으므로 1 추가
*/

import java.util.*;

class Solution {
        public int solution(String s) {
            int answer = 0;
            for (int i = 0; i < s.length(); i++) {
                int idx = (i + 1) % s.length();
                Stack<Character> stack = new Stack<>();
                stack.push(s.charAt(i));
                while (idx != i) {
                    stack.push(s.charAt(idx));

                    if (stack.size() >= 2) {
                        char right = stack.get(stack.size() - 1);
                        char left = stack.get(stack.size() - 2);
                        if (left == '(' && right == ')') {
                            stack.pop();
                            stack.pop();
                        }else if(left == '{' && right == '}'){
                            stack.pop();
                            stack.pop();
                        }else if(left == '[' && right == ']'){
                            stack.pop();
                            stack.pop();
                        }
                    }

                    idx = (idx + 1) % s.length();
                }

                if (stack.size() >= 2) {
                    char right = stack.get(stack.size() - 1);
                    char left = stack.get(stack.size() - 2);
                    if (left == '(' && right == ')') {
                        stack.pop();
                        stack.pop();
                    } else if (left == '{' && right == '}') {
                        stack.pop();
                        stack.pop();
                    } else if (left == '[' && right == ']') {
                        stack.pop();
                        stack.pop();
                    }
                }

                if (stack.isEmpty()) {
                    answer++;
                }
            }
            return answer;
        }
    }

85번 연속 부분 수열 합의 개수

/*
문제 분석
1. 정보
    - 자연수로 이루어진 원형 수열의 연속하는 부분 수열의 합으로 만들 수 있는 수가 몇가지인지 궁금함
    - 원형 수열이란 처음과 끝이 연결된 형태의 수열을 말함
        - 따라서, 연속하는 부분 수열도 일반적인 수열보다 많아짐
2. 목표
    - 수열이 주어질 때, 원형 수열의 연속 부분 수열 합으로 만들 수 있는 수의 개수를 return
3. 제약 조건
    - 3 <= 수열의 길이 <= 1000
    - 1 <= 수열의 원소 <= 1000

풀이
1. 아이디어
    - Set을 사용하여 합의 중복 제거
    - 길이가 1인 수열부터 길이가 elements.length()인 부분 수열까지 모든 수열의 합을 구함
    - 원형 수열이므로, elements를 두배로 잡아 부분 합을 계산
    - 이때, 부분 합을 사용하여 계산
        - 첫번째 원소 부터 현재 원소까지의 부분합을 각 인덱스에 저장
        - 해당 부분합을 사용한다면 예를들어, elements 길이가 3일 경우
            - 길이가 2인 부분수열의 합을 찾는 방법
                - 시작 : 0, 끝 : 1
                    - 부분합[1]
                - 시작 : 1, 끝 : 2
                    - 부분합[2] - 부분합[0]
                - 시작 : 2, 끝 : 3
                    - 부분합[3] - 부분합[1]
                - 시작 : 3, 끝 : 4
                    - 부분합[4] - 부분합[2] ...
    - 해당 값들을 set에 저장한 후 모두 끝나면 set의 크기를 return
*/

import java.util.*;

class Solution {
        public int solution(int[] elements) {
            int[] sum = new int[elements.length * 2 + 1];
            sum[0] = 0;
            for (int i = 1; i <= elements.length * 2; i++) {
                sum[i] = sum[i - 1] + elements[(i - 1) % elements.length];
            }
            Set<Integer> set = new HashSet<>();
            for (int element : elements) {
                set.add(element);
            }

            for (int len = 2; len <= elements.length; len++) {
                for (int i = 1; i <= elements.length; i++) {
                    int j = i + len - 1;
                    int tmp = sum[j] - sum[i - 1];
                    set.add(tmp);
                }
            }
            return set.size();
        }
    }