[JAVA] 11663번 - 선분 위의 점

문제 탐색하기

- 문제에서 구해야 하는 최종 정답은 무엇인지 탐색한 과정
- 그 정답을 구하기 위해 어떻게 코드를 구현해야 할지 고민한 과정
- 문제에 들어오는 범위를 파악하여 어떤 알고리즘을 쓸 수 있을지 고민해 가는 과정

 

지난달에 이분탐색을 풀면서 떠올렸던 lowerBound랑 upperBound의 개념을 떠올려서 풀었다.

아이디어는 이렇다.

1. 점들을 배열에 저장한다 

1 3 10 20 30

 

2. 선분의 시작점과 끝지점을 입력받아서 각각 start, end로 둔다.

3. lowerBound = 시작점보다 크거나 같은 첫번째 위치 찾는다

4. upperBound = 끝점보다 작거나 같은 마지막 위치 다음 위치 찾는다.

5. upperBound - lowerBound의 갯수가 정답이다.

 

예시를 들어보자면 2~15의 길이 선분이 있다고 하면

2보다 크거나 같은 첫번째 위치: 배열에서 3 = 인덱스 1
15보다 작거나 같은 마지막 위치 다음 위치: 배열에서 20 = 인덱스 3
정답: 3-1 = 2

 

 lowerBound를 구하는 메서드 하나, upperBound를 구하는 메서드 하나를 만들면 된다.

 

 

 

시간복잡도

1. 이진탐색을 하려면 정렬이 되어있어야한다. 점n개 좌표 배열 정렬 -> O(N log N)

2. 각 선분에 대한 lowerBound, upperBound수행

-> O(2 * log N), 즉 **O(log N), m개의 선분에 대해 수행하니까 O(MlogN)

3. 총 시간 복잡도: O(NlogN)+O(MlogN) = 500,000+500,000=1,000,000번이다 

 

 

코드 설계하기

위의 문제 탐색하기에서 고민한 과정을 토대로 문제 풀이에 대한 실마리를 잡았다면, 문제 풀이를 본격적으로 하기전, 문제를 풀이 위한 로드맵을 그려본다
어떤 순서로 코드를 작성해야 할지, 어떤 함수들을 작성해야 할지 등을 작성

1. 선분 m개를 입력받아서 StringBuilder에 저장

 for(int i=0; i<m; i++) {
        	st= new StringTokenizer(br.readLine());
        	int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());
            
            // 시작점보다 크거나 같은 첫 번째 점의 위치 찾기
            int lower = lowerBound(arr, start);
            
            // 끝점보다 작거나 같은 마지막 점의 위치 찾기
            int upper = upperBound(arr, end);
            
            // 선분 위에 있는 점의 개수: upper - lower
            sb.append(upper - lower).append("\n");
        }

 

2. 이분탐색을 각각 수행

 

 

 

시도 회차 수정 사항

- 무분별하게 "맞았습니다" 가 나올때까지 수정하는 형태의 문제 풀이를 반복하면, 내가 어떤 실수를 해서 해당 문제를 틀렸는지 모르게 된다
- 틀렸습니다를 받았다면 왜 틀렸는지 고민핸보고, 어떻게 수정할 수 있는지 고민하는 과정을 작성
- 위에 내가 세울 설계에서 어떤 부분이 틀렸는지도 함께 점검

 

1회차 시도

=> 이분탐색 if문에서 범위를 =을 빼먹어서 틀렸다.

 

 

정답 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.Deque;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Queue;
import java.util.Set;
import java.util.StringTokenizer;
import java.util.TreeSet;

public class Main {
	static int[] arr;
   public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));       
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        
        arr= new int[n];
        st = new StringTokenizer(br.readLine());
        for(int i=0; i<n; i++) {
        	arr[i] = Integer.parseInt(st.nextToken());
        }
        
        Arrays.sort(arr);
        StringBuilder sb = new StringBuilder();

        
        for(int i=0; i<m; i++) {
        	st= new StringTokenizer(br.readLine());
        	int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());
            
            // 시작점보다 크거나 같은 첫 번째 점의 위치 찾기
            int lower = lowerBound(arr, start);
            
            // 끝점보다 작거나 같은 마지막 점의 위치 찾기
            int upper = upperBound(arr, end);
            
            // 선분 위에 있는 점의 개수: upper - lower
            sb.append(upper - lower).append("\n");
        }
      
        System.out.println(sb);
        	     
    }

   // 이진 탐색으로 시작점보다 크거나 같은 첫 번째 위치 찾기
   private static int lowerBound(int[] arr, int target) {
       int low = 0;
       int high = arr.length;
       
       while(low<high) {
    	   int mid = (low+high)/2;
    	   if(arr[mid]>= target) {
    		   high = mid;
    	   }
    	   else {
    		   low = mid+1;
    	   }
       }
       
       return low;
   }
   
   // 이진 탐색으로 끝점보다 작거나 같은 마지막 위치 찾기
   private static int upperBound(int[] arr, int target) {
       int low = 0;
       int high = arr.length;
       
       while(low<high) {
    	   int mid = (low+high)/2;
    	   if(arr[mid] <= target) {
    		   low = mid+1;
    	   }
    	   else {
    		   high = mid;
    	   }
       }
       
       return low;
   }
}