[코딩테스트] 23-11-28 프로그래머스

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

프로그래머스

import java.util.Arrays;

class Solution {
    public int solution(int[] people, int limit) {
        Arrays.sort(people);  
        int answer = 0;  
        int left = 0;  
        int right = people.length - 1;  

        while (left <= right) {
            if (people[left] + people[right] <= limit) {
            	left++;
            }
            right--; 
            answer++;
        }

        return answer;
    }
}

 

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

프로그래머스

class Solution {
    public int solution(int N) {
        int battery = 0;

        while (N > 0) {
            if (N % 2 == 0) {
            	N /= 2;
            } else {
                N -= 1;
                battery += 1;
            }
        }

        return battery;
    }
}

 

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

프로그래머스

class Solution
{
    public int solution(int n, int a, int b)
    {
        int answer = 0;

        while(a != b){
            int[] arr = nextGroup(a,b);
            a = arr[0];
            b = arr[1];
            answer++;
        }

        return answer;
    }

    public int[] nextGroup(int A, int B){
        int[] array = new int[2];

        array[0] = A/2 + A%2;
        array[1] = B/2 + B%2;

        return array;
    }
}

처음 이 문제를 접했을 때, 참가자가 승리하며 올라갔을 때, 어떻게 추적하는지 때문에 고민이 많았습니다.
그 때문에 머리가 복잡해서 엑셀에 정리를 하며 세 가지 사실을 깨달았습니다.
첫번째, 대결하는 사람끼리 그룹을 지었을 때, 그룹에게 참가자처럼 번호 부여하면 그 것이 바로 다음 라운드 때의 번호와 같다는 것을 알았습니다.
두번째, 다음 그룹의 번호가 같다면 그 때가 바로 라이벌 둘의 만남입니다.
세번째, 그룹 번호는 참가자의 번호를 2로 나눴을 때의 몫과 나머지의 합과 같다는 것입니다. 이는 다음 그림과 같습니다.

그래서 nextGroup 메소드를 만들고 위와 같이 코딩을 할 수가 있었습니다.

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

프로그래머스

import java.util.Arrays;

class Solution {
    public int solution(int[] arr) {
        int answer = findLCM(arr);

        return answer;
    }

    private static int findGCD(int a, int b) {
        if(b == 0) return a;
        return findGCD(b, a%b);
    }

    private static int findLCM(int[] arr) {
        int lcm = arr[0];

        for (int i = 1; i < arr.length; i++) {
        	lcm = (lcm * arr[i]) / findGCD(lcm, arr[i]);
        }

        return lcm;
    }
}

이번에는 나름 손으로 최소공배수를 구하듯이 코드를 짜봤지만 너무 오래 걸려서 실패하는 바람에 검색을 안 할 수가 없었습니다. 찾아보니 유클리드 호제법이라는 것이 나오더군요. 효과적이고 시간이 적게 걸리는 방법으로 최대공약수, 최소공배수에 꼭 이용해야 할 것 같았습니다. 
이를 이용해 문제를 풀 수 있게 됐습니다. 사람에게 좋은 방식과 기계에게 좋은 방식이 서로 다르다는 것을 절실히 느낄 수 있었습니다.