알고리즘(숫자 게임, 지형 편집)

[숫자 게임]

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

코딩테스트 연습 - 숫자 게임

 

* 로직

• A와 B 모두 오름차순 정렬한다
• A의 값을 기준으로 B가 이기는 경우를 찾으면 카운팅 하고 A의 그 다음 값을 비교한다
• 이때 B의 인덱스는 이전에 발견한 인덱스 다음부터 진행함으로써 시간을 단축시킨다

 

import java.util.Arrays;

class Solution {
    public int solution(int[] A, int[] B) {
        int answer = 0;
        int idx = 0;

        Arrays.sort(A);
        Arrays.sort(B);

        for(int i=0; i<A.length; ++i){
            for(int j=idx; j<B.length; ++j){
                if(A[i] < B[j]){                    
                    answer++;                                        
                    idx=++j;                    
                    break;
                }
            }
        }

        return answer;
    }
}

 

 

[지형 편집]

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

코딩테스트 연습 - 지형 편집

 

* 알고리즘

• 이분탐색

 

* 로직

• 지형의 높이를 기준으로 이분 탐색을 진행한다
  (ex. 높이를 기준으로 오른쪽 범위의 비용이 더 크다면, 이후의 높이에서도 비용이 크기 때문에 해당 범위는 제외시켜버릴 수 있게된다)
• 만약 현재 높이를 기준으로
  • 왼쪽에 있는 비용 <= 오른쪽에 있는 비용
    => rear = mid-1, answer = cost(왼쪽)
  • 왼쪽에 있는 비용 > 오른쪽에 있는 비용
    => front = mid+1, answr = cost(오른쪽)
• 최소 비용을 출력한다

 

public class Solution {
	public long solution(int[][] land, int P, int Q) {
		long answer = -1;
        long maxHeight = 0;
        long minHeight = Long.MAX_VALUE;

        for(int i=0; i<land.length; ++i){
            for(int j=0; j<land[i].length; ++j){
                maxHeight = Math.max(maxHeight, land[i][j]);
                minHeight = Math.min(minHeight, land[i][j]);
            }
        }

        long front = minHeight;
        long rear = maxHeight;                
        while (front <= rear){
            long mid = (front + rear) / 2;                    

            long cost1 = getCost(land, mid, P, Q);
            long cost2 = getCost(land, mid+1, P, Q);            

            //왼쪽 범위에 최소 비용이 존재한다
            if(cost1 <= cost2){                        
                answer = cost1;                
                rear = mid-1;
            }

            else {
                answer = cost2;                
                front = mid+1;
            }
        }

        return answer;
	}
    
    private static long getCost(int[][] land, long height, int P, int Q) {
        long cost = 0;
        for(int i=0; i<land.length; ++i){
            for(int j=0; j<land[i].length; ++j){
                if(land[i][j] < height) cost += (height - land[i][j])*P;
                else if(land[i][j] > height) cost += (land[i][j] - height)*Q;
            }
        }

        return cost;
    }
}