[프로그래머스] Lv.2 요격시스템 JAVA 풀이

문제 Lv.2 요격시스템

:  여러 개구간 x좌표가 있다

   이들을 모두 한번씩 관통해야 한다

   최소한으로 쏠 수 있도록 최대한 겹쳐 미사일을 쏜다

 

▶ targets = [ 1, 4 ], [ 3, 7 ], [ 4, 5 ], [ 4, 8 ], [ 5, 12 ], [ 10, 14 ], [ 11, 13 ] 

 

:  targets 는 미사일 좌표 범위

   좌표는 x좌표로만 이루어져 있고 [s,e] 로 표현 가능

   이때, [s,e]는 개구간이다 (즉, 시작지점과 끝지점 미포함)

 

 [문제 방식]

1. 끝지점을 기준으로 잡아서 오름차순으로 정렬하고 시작

2. 현재 구간의 끝지점과 다음 타겟의 시작점이 겹치지 않는 순간 count

    더 이상 겹칠게 없기 때문에 다음 좌표들의 미사일 쏘고 구간 계산

    (이해중요! 일단은 미사일 먼저 쏴놓고 구간 계산 하는 것)

 

[EX]                                        현재 내가 보고있는 좌표 [1,3], 새롭게 들어올 타겟 좌표 [2,4] 일 때

         ------------                       끝지점인 3이 다가오기 전에 새롭게 들어온 시작지점 2는 서로 겹치기 때문에

-------------       -------               뒤에 또 겹칠 타겟이 있을 수도 있으므로 아직은 카운트 하지 않는다

1      2     3      4      5              다음 타겟 [4,5]의 시작지점 4를 보고 더 이상 겹치는 것이 없음을 확인
                                                그때 미사일 [4,5] 사이에 쏠 미사일 1발을 count

 

<여기서, 의문점>     

 

그렇다면 [1,3]과 [2,4] 사이에 쏠 미사일은 언제 count 하는거죠?

일단 미리 미사일을 먼저 쏘고 구간을 계산하는 방식이므로

아래 코드를 보면 알겠지만 맨처음 끝지점을 0으로 초기화해서

무조건 count 하고 시작할 수 있게끔 설정한다 

 

[알고 가야할 함수]

 

-  Array.sort 2차원 배열 정렬

  (2차원 배열인 [ A, B ] 에서 A는 0번째 B는 1번째라고 표현가능)

 
 (EX)          arr =  [ 5, 40 ], [ 4, 20 ], [ 1, 30 ] 라면

-  (o1, o2) -> o1[0]-o2[0]   :  0번째 숫자 기준 오름차순   ▶ [ 1, 30 ] - [ 4, 20 ] - [ 5, 40 ] 

-  (o1, o2) -> o2[0]-o1[0]   :  0번째 숫자 기준 내림차순   ▶ [ 5, 40 ] - [ 4, 20 ] - [ 1, 30 ]   

-  (o1, o2) -> o1[1]-o2[1]   :  1번째 숫자 기준 오름차순   ▶ [ 4, 20 ] - [ 1, 30 ] - [ 5, 40 ] 

-  (o1, o2) -> o2[1]-o1[1]   :  1번째 숫자 기준 내림차순   ▶ [ 5, 40 ] - [ 1, 30 ] - [ 4, 20 ]

 

 [코드]

import java.util.*;
class Solution {
    public int solution(int[][] targets) {
        int result = 0;
        int now = 0;
        Arrays.sort(targets, (o1, o2) -> o1[1]-o2[1]);
        for(int i=0; i<targets.length; i++) {
        	if(targets[i][0] >= now) {
        		now = targets[i][1];
        		result++;
        	}
        }
        return result;
    }
}

       

:   int result = 0;  결과로 출력할 result 지정

    int now;  현재 좌표

        
:   Arrays.sort(targets, (o1, o2) -> o1[1]-o2[1]);  1번째 자리(끝지점) 숫자 기준으로 오름차순 정렬

 

:  for(int i=0 ; i<targets.length ; i++) {  targets 개수 만큼 반복
           if(targets[i][0] >= now) {  0번째 열을 행 바꿔가며 비교 (즉 시작지점만 비교) 

                                                  현재 좌표의 끝지점과 다음 올 targets 좌표의 시작지점을 비교
                                                  끝지점 보다 시작지점이 더 크면 그때는 더이상 겹치는 부분이 없기 때문에
                                                  미사일 쏘고 다음 타겟으로 넘어간다

                now = targets[i][1];    1번째 열을 행 바꿔가며 비교 (즉 끝지점만 비교) 

                                                   카운트 될 때마다 비교대상 now도 새롭게 갱신

                result++;  결과 카운트

           }                                       
   }                                               
        
:  return result;  결과 출력

 

 

 

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

프로그래머스

 

 

* 독학으로 익히는 코딩이라 틀린 것이 있을 수 있습니다. 오류가 있다면 댓글을 통해 알려주세요. 감사합니다. *