[99클럽 코테 스터디 TIL#3일차] 프로그래머스 입국심사

문제

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

 

 

문제 풀기

 

1. 이분 탐색

이분 탐색을 사용해 검사 시간의 최솟값을 찾는 문제였다. 이분 탐색 알고리즘 자체는 간단하지만, 이렇게 응용하니 어렵다고 생각되는 지점이 몇 개 있었다.

 

2. 실수 줄이기

코드 제출을 했을 때, 통과하는 케이스도 있었지만 실패하는 케이스도 있었다. 작성된 코드의 잘못된 부분이 어딨는지 찾는 건 어려운 일이라 처음부터 꼼꼼하게 코딩하는게 중요하다는 생각이 들었다. 아직 코테 준비를 시작한지 3일차라 그런지 기본적인 부분에서 같은 실수를 하기도 했다. 아래의 세 개를 신경 쓰면서 코드를 작성해야겠다.

1.   숫자 타입 제대로 맞게 쓰여있는지 (이번 경우는 int끼리 계산하고 long에 넣었다. 하나는 long으로 형변환 해서 계산 해야하는데)
2.   for문 돌릴 때 끝 값 / 첫번째 값 잘 돌게 적혀 있는지 확인
3.   문자열이나 배열 다룰 때 크기가 같은 조건이면 예외처리가 필요할 수 있다.

 

3. 문제 풀면서 고민 했던 부분

이분 탐색 문제는 이번으로 세번째 푼다. 세번째 풀다보니 감이 잡히는 것 같다. 아래의 두가지를 고민하며 문제를 풀었다.

 

1.   어떤 걸 탐색 공간으로 잡아야할지 
2.   어떤 걸 기준으로 left와 right에 조작을 줄 지

→ 무엇의 최소 / 최대 값을 찾는가 ?

 

 

작성한 코드

import java.util.Arrays;

class Solution {
    public long solution(int n, int[] times) {
        long answer = Long.MAX_VALUE;
        Arrays.sort(times);
        long left = times[0];
        long right = (long) times[times.length - 1] * n;
        
        
        while(left <= right) {
            long mid = (left + right) / 2;
            long guessN = 0;
            
            for(int time : times) {
                guessN += mid / time;
            }
            
            if(guessN < n) {
                left = mid + 1;
            } else {
                answer = Math.min(answer,mid);
                right = mid - 1;
            }
        }
        
        return answer;
    }
}