[1주차] Coding Test 그리디/ 정렬/ 이분탐색/ 시뮬레이션

1. 기지국 설치 

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

  Sol 1) 기본형 이용- 정확성: 0.02ms, 효율성: 1.19ms

<hide/>
// 기지국 설치
// https://programmers.co.kr/learn/courses/30/lessons/12979

import java.util.*;
public class T3 {

    public static int solution(int n, int[] stations, int w) {  // 16, [9], 2

       int cnt = 0;         // 기지국 개수
       int position  = 1;   // 1동부터 시작
       int idx = 0;         // stations[] 내의 idx

        // 위치의 개념 position
        // 등호가 꼭 필요하다.
        while(position <= n){

            // 기지국 설치 하지 않아도 되는 상황
            // 현 위치 position은 station[idx]으로부터 전파가 터지는 상황이다.
            if(idx < stations.length && stations[idx] - w <= position){

                // position에 2w + 1만큼 온전히 더할 수 없는 상황이니까 position을 변경한다.
                position = stations[idx] + w + 1;
                ++idx;
                System.out.println("position: " + position + ", idx: "+ idx);
                continue;
            }
            // 기지국 설치해야하는 상황
            ++cnt;
            position += 2 * w + 1;
            System.out.println("position: " + position + ", cnt: " + cnt);
        }
        return  cnt;
    }
    
    public static void main(String[] args){

        int[] stations = {4, 11};
        System.out.println(solution(11, stations, 1));  // 3

        stations = new int[]{9};
        System.out.println(solution(16, stations, 2));  // 3

        stations = new int[]{3, 7, 9};
        System.out.println(solution(16, stations, 1));  // 4
    }
}

  - 그리디(greedy) 알고리즘을 이용한다.

  - 루프는 효율성 테스트에서 시간을 많이 잡아 먹는다. 

  - primitive 타입을 사용하는 게 Objects타입( ex) stack, queue ) 사용 보다 빠르다.

  - 그런데 while문에  등호가 빠지면 점수가 깎인다..

 

  

 

  Sol 2) Queue 이용 - 정확성:  , 효율성: 

 

  Sol 3) 제출 답안

<hide/>
class Solution {
public int solution(int n, int[] stations, int w) {     // 11,  [4, 11] , 1
        
        int left = 0;   //기지국 범위 외 왼쪽    
        int right = 0; //기지국 범위 외 오른쪽
        int baseL = 0;  //기지국 범위 내 왼쪽
        int baseR = 0;  //기지국 범위 내 오른쪽
        int result = 0;

        for(int i = 0; i < stations.length; ++i){
            int base = stations[i];     // 4, 11
            left = baseR;   // 왼쪽 값은 기지국 내의 오른쪽 값, 나중에 개수를 구하기위해 굳이 +1하지않는다.

            baseL =  base - w;
            baseR = base + w;   // 너비 w에 따른 기지국의 범위 baseL ~ baseR

            if(baseL < 0 ) baseL = 0;
            if(baseR > n ) baseR = n;   // 배열의 범위를 초과할 때 한정시켜준다.
            
            right = baseL - 1;
            if(right < 0)  continue;        
            if(left == right) continue;     // 같다면 기지국 사이가 커버 되었을 때이다. ??
            if(left > right) continue;

            double temp = (double) (right - left) / ((2 * w) + 1);
            if(temp % 1 == 0)   result += (int) temp;   // temp가 정수 일 때
            else result += (int) temp + 1;

        }
        if(baseR != n){     // 모두 처리한 후, baseR은 n이 되어야 한다.
            double temp = (double) (n - baseR) / ((2 * w) + 1);
            if(temp % 1 == 0) result += (int) temp;
            else result += ((int) temp) + 1 ;

        }
        return result;
     }
}

 

 

2. 가장 큰 수

  Sol) 

  - 배열

  - 숫자로 생각해서 풀지 않고 문자열을 다룬다 생각하고 푼다. 

  - 숫자 -> 문자 -> 내림차순 정렬 -> 조합

  - 정확성 테스트에서 시간 초과되는 경우: 무한 루프가 돌거나 연산이 느린 경우

  - 간결한 버전

<hide/>
import java.util.*;
import java.util.stream.*;
// 스트림 사용하기
class Solution {
    public String solution(int[] numbers) {
      String answer =  IntStream.of(numbers)
            .mapToObj(String::valueOf)
            .sorted((s1, s2) -> (s2 + s1).compareTo(s1 + s2))
            .collect(Collectors.joining());
            // 숫자를 문자로 바꾼다. 
            // 정렬된 문자열을 하나의 문자열로 합친다.
            // 최종 문자열은 answer
        if(answer.startsWith("0")) return "0";
        // startsWith로 비교하는 게 더욱 권장된다.
        return answer;
    }
}

<hide/>
import java.util.*;
class Solution {
    public String solution(int[] numbers) {
        String[] strNums = new String[numbers.length];
        for(int i = 0; i < numbers.length; ++i){
            strNums[i] = "" + numbers[i];
        }
        //strNums에 String이 들어 있기 때문에 s1, s2는 당연히 String
        Arrays.sort(strNums, (s1, s2) -> (s2+ s1).compareTo(s1 + s2)); 	// 내림차순
       
            
        String answer = "";
        for(String s: strNums){
            answer += s;
        }
        if(answer.startsWith("0")) return "0";
        // startsWith로 비교하는 게 더욱 권장된다.
        
        return answer;
    }
}

  - 참고

<hide/>
import java.util.*;
class Solution {
    public String solution(int[] numbers) {
        String[] strNums = new String[numbers.length];
        for(int i = 0; i < numbers.length; ++i){
            strNums[i] = "" + numbers[i];
        }
        Arrays.sort(strNums, new Comparator<String>(){
            public int compare(String s1, String s2){
                return (s2+ s1).compareTo(s1 + s2);
            }
        });
        String answer = "";
        for(String s: strNums){
            answer += s;
        }
        if(answer.charAt(0) == '0') return "0";
        return answer;
    }
}

 

 

3. 예산

  Sol)

  - 이분법을 이용하기 위해 최솟값, 최댓값을 구한다. 

  - Stream을 이용하면 간결하게 표현 가능하다.

  - final을 붙여야 효율성 테스트를 통과한다.

<hide/>
import java.util.stream.*;
class Solution {
    public int solution(int[] budgets, int M) {
        int min = 0;
        int max = IntStream.of(budgets).max().orElse(0);
        int answer = 0;
        while(min <= max){
            final int mid = (min + max) / 2;  // 상한값 
            int sum =  IntStream.of(budgets)
                .map(b -> Math.min(b, mid))
                .sum();
            if(sum <= M){
                min = mid + 1;  // 상향 조정
                answer = mid;
                continue;
            }              // 하향 조정
                max = mid - 1;
        }
        return answer;
    }
}

<hide/>
class Solution {
    public int solution(int[] budgets, int M) {
        int max = 0;
        int min = 0;
        for(int b : budgets){
            if(b > max) max = b;
        }
        int answer = 0;
        while(min <= max){
            int mid = (min + max) / 2;  // 상한값 
            int sum = 0;
            for(int b : budgets){
                if(b > mid) sum += mid;
                else sum += b;
            }
            if(sum <= M){
                min = mid + 1;  // 상향 조정
                answer = mid;
            }else{              // 하향 조정
                max = mid - 1;
            }
        }
        return answer;
    }
}

 

 

4. 숫자 게임

  Sol)

  - 루프를 거꾸로 돌면서 서로 가장 큰 값을 비교한다.

  - 단일 루트로 풀면 효율성 테스트 통과

  - A와 B를 먼저 정렬시킨 다음에 A와 B에 인덱스를 다르게 준다. 

  - A[i] < B[index] 를 만족하면 index를 마이너스하고 answer을 플러스한다.  

<hide/>
import java.util.*;
class Solution {
    public int solution(int[] A, int[] B) {
    Arrays.sort(A);    
    Arrays.sort(B);
    int index = B.length - 1;
    int answer = 0;
        for (int i = A.length -1; i >= 0 ; --i) {
              if (A[i] < B[index]) {
                --index;
                ++answer;
               }
         }
        return answer;
    }
}

 

출처: https://programmers.co.kr/learn/courses/13699