CODEKATA 76 ~ 80

76번 JadenCase 문자열 만들기

/*
문제 분석
1. 정보
    - JadenCase란 모든 단어의 첫 문자가 대문자이고, 그 외의 알파벳은 소문자인 문자열을 말함
    - 단, 첫 문자가 알파벳이 아닐 때에는 이어지는 알파벳은 소문자로 쓰면 됨

2. 목표
    - JadenCase로 변환한 값을 return

3. 제약 조건
    - 1 <= s의 길이 <= 200
    - s는 알파벳, 숫자, 공백문자로 이루어져 있음
        - 숫자는 단어의 첫 문자로만 나옴
        - 숫자로만 이루어진 단어는 존재 X
        - 공백 문자가 연속해서 나올 수 있음.

풀이
1. 아이디어
    - s의 길이가 짧으므로 0 ~ s의 길이까지 반복문 수행
        - 만약 현재문자가 공백이라면 그대로 진행
        - 만약 이전문자가 공백이었다면
            - 현재 문자가 숫자 or 알파벳 대문자라면 그대로 진행
            - 현재 문자가 알파벳 소문자라면 대문자로 변환
        - 만약 이전문자가 공백이 아니라면
            - 현재 문자가 알파벳 대문자라면 소문자로 변환
    - 변환한 결과 값 return
*/

class Solution {
        public String solution(String s) {
            boolean flag = true;
            char[] tmp = s.toCharArray();
            for (int i = 0; i < tmp.length; i++) {
                if (tmp[i] == ' ') {
                    flag = true;
                    continue;
                }

                if(flag){
                    if(tmp[i] >= 'a' && tmp[i] <= 'z') {
                        tmp[i] -= 32;
                    }
                    flag = false;
                }else{
                    if(tmp[i] >= 'A' && tmp[i] <= 'Z'){
                        tmp[i] += 32;
                    }
                }
            }
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < tmp.length; i++) {
                sb.append(tmp[i]);
            }
            return sb.toString();
        }
    }

77번 이진 변환 반복하기

/*
문제 분석
1. 정보
    - 0과 1로 이루어진 문자열 x에 대한 이진 변환을 다음과 같이 정의
        - 1. x의 모든 0을 제거
        - 2. x의 길이를 c라고 하면, x를 "c를 2진법으로 표현한 문자열"로 바꿈
        - 예를 들어 x = "0111010" 일 경우
            - "1111" 로 바뀐뒤, 해당 길이가 4 이므로
            - "100"으로 바뀜
2. 목표
    - s가 1이 될 때까지 계속 이진 변환을 가했을 때, 이진 변환 과정에서 제거된 모든 0의 개수를 배열에 담아 return

3. 제약 조건
    - 1 <= s의 길이 <= 150000
    - s에는 1이 최소 하나 이상 포함되어 있음

풀이
1. 아이디어
    - 단순 구현
    - while문 통해 s가 1이 나올때까지 반복
        - 현재 길이와, replaceAll을 하고 난 이후의 길이를 각각 구함
        - list에 현재 길이 - 이후 길이 값을 더해줌 -> 0의 개수
        - 이후 길이가 위 정보의 c가 됨
        - c를 이진법으로 변환 후 s와 바꿔줌
*/

import java.util.*;

class Solution {
        public int[] solution(String s) {
            int[] answer = new int[2];
            while(true){
                if (s.equals("1")) {
                    break;
                }
                answer[0]++;
                int curLen = s.length();
                s = s.replaceAll("0", "");
                int changeLen = s.length();
                answer[1] += (curLen - changeLen);
                StringBuilder sb = new StringBuilder();
                while(true){
                    sb.append(changeLen % 2);
                    changeLen /= 2;
                    if(changeLen == 0){
                        break;
                    }
                }
                sb.reverse();
                s = sb.toString();
            }
            return answer;
        }
    }

78번 피보나치 수

/*
문제 분석
1. 정보
    - 피보나치 수는 F(0) = 0, F(1) = 1일때, 1이상의 N에 대하여 F(N) = F(N - 1) + F(N - 2)가 적용되는 수

2. 목표
    - 2이상의 N이 입럭되었을 때, N번째 피보나치 수를 1234567로 나눈 나머지를 return
3. 제약 조건
    - 2 <= N <= 100,000


풀이
1. 아이디어
    - dp 배열 사용
        - dp[N + 1]을 생성해 해당 숫자의 피보나치 수 값을 구함
        - dp[n]은 (dp[n - 1] + dp[n - 2]) % 1234567 가 됨
*/

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

79번 카펫

/*
문제 분석
1. 정보
    - 레오는 중앙에는 노란색으로 칠해져 있고, 테두리 1줄은 갈색으로 칠해진 격자 모양 카펫을 봤음
    - 집에와서 레오는 노란색과 갈색으로 색칠된 격자의 개수는 기억했지만, 전체 카펫의 크기는 기억을 하지 못함
    
2. 목표
    - 노란색과 갈색의 격자의 개수가 주어졌을때, 카펫의 가로 세로 크기를 순서대로 배열에 담아 return
3. 제약 조건
    - 8 <= 갈색 격자의 수 <= 5000
    - 1 <= 노란색 격자의 수 <= 2,000,000
    - 카펫의 가로 길이 >= 세로 길이

풀이
1. 아이디어
    - 갈색 카펫과 노란색 카펫의 개수를 더한 값의 약수를 구함
        - 해당 악수는 반드시 가로,세로 높이 중 일부
    - 즉 더한 값부터 2가 나올때까지 -- 반복
        - 만약 해당 값이 약수라면 -> 가로로 설정
            - 세로 = 전체 개수 / 가로 값
            - 해당 값을 이용해 다음을 도출 가능
                - 해당 노란색 개수 -> (가로 - 2) * (세로 - 2)
                - 해당 갈색 개수 -> 가로 * 세로 - 노란색 개수
                - 일치한다면 값 return
*/

class Solution {
        public int[] solution(int brown, int yellow) {
            int[] answer = new int[2];
            int sum = brown + yellow;
            for (int row = sum; row > 1; row--) {
                if (sum % row == 0) {
                    int col = sum / row;
                    int yellowSum = (row - 2) * (col - 2);
                    int brownSum = row * col - yellowSum;
                    if (brownSum == brown && yellowSum == yellow) {
                        answer[0] = row;
                        answer[1] = col;
                        break;
                    }
                }
            }
            return answer;
        }
    }

80번 예상 대진표

/*
문제 분석
1. 정보
    - 게임 대회에는 N명이 참가하고, 토너먼트 형식으로 진행 됨
    - N명의 참가자는 각각 1번부터 N번을 차례대로 배정 받음
        - 1 <-> 2, 3 <-> 4 식으로 게임을 진행
        - 게임에 이기면 다음 라운드에 진출
            - 다음 라운드에서도 위와 동일하게 1번부터 N / 2번을 배정 받고 경기
    - 이때, 처음 라운드에서 A번을 가진 참가자는 B번 참가자와 몇 번째 라운드에서 만나는지 궁금
2. 목표
    - A번을 가진 참가자와 B번을 가진 참가자가 몇 번째 라운드에서 만나는지 return하는 함수

3. 제약 조건
    - 2^1 <= N <= 2^20
    - A,B <= N

풀이
1. 아이디어
    - 이분 탐색 활용하여 구함
        - 처음은 전체 범위
            - mid = (left + right) / 2
                - 만약 A와 B가 mid를 기준으로 다른 곳에 있다면, 해당 라운드에 만나게 됨
                    - 즉, 전체 라운드에서 현재까지 구한 라운드 값을 빼준 값이 정답
                - 만약 A와 B가 mid를 기준으로 같은 곳에 있다면, 계속 탐색
    - 전체 라운드 개수 : N을 2의 지수승으로 표현했을 때 지수 값
*/

class Solution {
        public int solution(int n, int a, int b) {
            int totalRound = 0;
            int idx = 1;
            int cur = 2;
            while(true){
                if (cur == n) {
                    totalRound = idx;
                    break;
                }
                cur *= 2;
                idx++;
            }

            int left = 1;
            int right = n;
            idx = 0;
            int answer = 0;
            while(true){
                int mid = (left + right) / 2;
                if ((a <= mid) && (b <= mid)) {
                    right = mid;
                    idx++;
                } else if ((a > mid) && (b > mid)) {
                    left = mid;
                    idx++;
                } else{
                    answer = totalRound - idx;
                    break;
                }
            }
            return answer;
        }
    }