프로그래머스LV2_4

카펫

접근 과정

1. 안쪽 노란색의 가로와 세로 길이로 갈색 색깔을 구하면 w 2 + h 2 + 4인 것을 알 수 있다.
2. 가로가 세로보다 길어야 하므로 가로를 안쪽 최대 길이 세로를 1부터 하여 시작
3. 반복문으로 안쪽 가로, 세로 길이로 갈색 타일 개수가 같아지면 멈춘다.
4. 같지 않다면 가로를 노란색 개수와 나머지가 없을 때까지 1씩 빼고 세로를 노란색을 갱신된 가로로 나눠 갱신한다.
5. 결과로 나온 가로와 세로에 +2씩 하여 반환하여 해결

시행착오

• 시행착오 없이 접근 과정대로 해결
  

해결 코드

• 접근 과정대로 해결하였는데 좀 더 빠른 방법을 다른 사람의 풀이를 참고하여 찾았다.
• 높이를 1부터 시작하여 가로가 세로보다 길거나 같으므로 yellow의 제곱근까지 반복하여 탐색하면서 갈색 타일 개수와 같아지는 순간을 캐치하면 된다. → O(sqrt(Y))
  

    class Solution {
        public int[] solution(int brown, int yellow) {
            int w = yellow, h = 1;
            while(true){
                int b = w * 2 + h * 2 + 4;
                if(b == brown) break;
                else{
                    w--;
                    while(yellow % w != 0){
                        w--;
                    }
                    h = yellow / w;
                }
            }
            return new int[]{w + 2, h + 2};
        }
    }
    
    // 개선
    class Solution {
        public int[] solution(int brown, int yellow) {
            for (int h = 1; h <= Math.sqrt(yellow); h++) {
                if (yellow % h == 0) {
                    int w = yellow / h;
                    if ((w + h) * 2 + 4 == brown) {
                        return new int[]{w + 2, h + 2};
                    }
                }
            }
            return new int[]{0, 0};
        }
    }

시간복잡도

구명보트

접근 과정

1. 적은 구명보트를 사용하려면 최대한 많은 짝을 만들어야 한다.
2. 가벼운 사람과 무거운 사람을 같이 태울 수 있으면 가장 적은 구명보트 수가 된다.
3. 배열을 정렬하고 제일 가벼운 사람과 제일 무거운 사람의 인덱스를 시작
4. 왼쪽 인덱스가 오른쪽보다 크거나 같을 때까지 반복하며 매 반복마다 구명보트 수를 늘린다.
5. 만약 두 명의 무게 합이 제한보다 작거나 같으면 두 인덱스를 갱신
6. 아니라면 오른쪽만 갱신하는 방식으로 해결

시행착오

• 처음에 이중 for문으로 풀어서 시간 초과를 겪었다. → O(N^2)
  

    import java.util.*;
    
    class Solution {
        public int solution(int[] people, int limit) {
            int answer = 0;
            Arrays.sort(people);
            boolean[] check = new boolean[people.length];
            for(int i = 0; i < people.length; i++){
                if(check[i]) continue;
                check[i] = true;
                for(int j = people.length - 1; j >= i + 1; j--){
                    if(check[j]) continue;
                    if(people[i] + people[j] <= limit){
                        check[j] = true;
                        break;
                    }
                }
                answer++;
            }
            return answer;
        }
    }

해결 코드

• 시행착오를 겪고 시간복잡도를 개선하였다.
• 정렬하는 시간은 O(NlogN)이고 반복문은 O(N)으로 총 시간복잡도는 O(NlogN)이다.
  

    import java.util.*;
    
    class Solution {
        public int solution(int[] people, int limit) {
            int answer = 0;
            Arrays.sort(people);
            int l = 0; int r = people.length - 1;
            while(l <= r){
                answer++;
                if(people[l] + people[r] <= limit){
                    l++;
                    r--;
                }
                else r--;
            }
            return answer;
        }
    }

시간복잡도