99클럽 코테 스터디 18일차 TIL ✒️캠프가는 영식

✅ 오늘의 학습 키워드

• 이진 탐색

---

🔍 오늘의 문제 분석

↘️ 오늘의 문제 바로가기 ↘️

 

• 총 N개의 버스 정류장
• 버스가 처음 출발하는 시간 S, 간격 I, 버스의 대수 C
• 영식이가 버스 정류장에 도착하는 시간 T
• 영식이가 버스를 타기 위해 기다려야 하는 최소 시간을 출력
• 만약 버스를 탈 수 없으면 -1 출력
• 1 ≤ N ≤ 50
• 1 ≤ T ≤ 1,000,000
• 1 ≤ Si ≤ 1,000,000
• 1 ≤ Ii ≤ 10,000
• 1 ≤ Ci ≤ 100

---

✨ 오늘의 회고

📌내가 적은 답안📌

import java.io.IOException;
import java.util.Scanner;

public class Main {

  public static void main(String[] args) throws IOException {
    Scanner scanner = new Scanner(System.in);

    int N = scanner.nextInt();
    int T = scanner.nextInt();

    int sum = 0;
    int cnt = -1;
    int min = 1000000;

    for (int i = 0; i < N; i++) { //버스정류장의 개수만큼 반복
      int S = scanner.nextInt();
      int I = scanner.nextInt();
      int C = scanner.nextInt();

      sum = S; //버스의 도착 시간

      for (int j = 0; j < C; j++) { //버스의 대수만큼 반복
        if (T <= sum) { //영식이가 도착한 시간이 버스의 도착시간보다 작거나 같으면
          cnt = sum - T; //버스의 도착 시간 - 영식이가 도착한 시간 = 영식이가 기다린 시간
          break;
        }
        sum += I; //대기 시간 이후 다음 버스가 도착하는 시간
      }

      if (cnt <= min && cnt != -1) { //영식이가 기다린 시간이 최소 시간보다 작으면
        min = cnt; //최소 시간 재설정
      }
    }

    if (cnt == -1) { //영식이가 어떤 버스도 타지 못하면 -1 출력
      System.out.println(cnt);
    } else { //최소 시간 출력
      System.out.println(min);
    }
  }
}

레벨 5를 달성했다!

영식이가 도착한 시간 이후에 출발하는 버스의 도착시간을 찾기 위해서 반복문을 돌리면서 버스의 출발 시간을 sum 변수에 업데이트해주었다. 만약 영식이가 도착한 시간보다 버스의 출발 시간이 더 많거나 같으면 영식이가 기다린 대기 시간을 계산해서 변수 cnt에 저장했다. 반복문 종료 후에도 cnt 값이 초기값인 -1이라면 영식이가 도착한 시간에서 더 이상 출발하는 버스가 없다는 뜻이기 때문에 그대로 -1을 출력하도록 했다.

 

버스 정류장은 1개가 아니라 여러 개이고 모든 버스 정류장의 모든 버스에 대한 대기 시간 중에서 최솟값을 찾아야 하기 때문에 최솟값을 저장할 변수 min을 설정하고 cnt값과 비교하여 더 작은 값으로 min을 업데이트하도록 했다. 그리고 이 min값을 최종 출력했다. 

 

이 코드는 모든 버스에 대한 대기 시간을 구할 수 밖에 없어서 효율이 떨어진다. 그래서 버스의 도착시간 S보다 min이 더 작다면 반복문을 중단하는 코드로 수정했다.

import java.io.IOException;
import java.util.Scanner;
public class Main {
  public static void main(String[] args) throws IOException {
    Scanner scanner = new Scanner(System.in);
    int N = scanner.nextInt();
    int T = scanner.nextInt();
    int sum = 0;
    int cnt = -1;
    int min = Integer.MAX_VALUE;
    
    for (int i = 0; i < N; i++) { //버스정류장의 개수만큼 반복
      int S = scanner.nextInt();
      int I = scanner.nextInt();
      int C = scanner.nextInt();
      sum = S; //버스의 도착 시간
      
      for (int j = 0; j < C; j++) { //버스의 대수만큼 반복
        if (T <= sum) { //영식이가 도착한 시간이 버스의 도착시간보다 작거나 같으면
          if (sum - T < min) { // 이 버스의 대기 시간이 현재 최소값보다 작으면
            min = sum - T;     // 최소값 업데이트
          }
          break;
        }
        sum += I; //대기 시간 이후 다음 버스가 도착하는 시간
      }
    }
    
    if (min == Integer.MAX_VALUE) { //영식이가 어떤 버스도 타지 못하면 -1 출력
      System.out.println(-1);
    } else { //최소 시간 출력
      System.out.println(min);
    }
  }
}

 

 

다른 방법도 찾아보기 위해서 검색해보았다. 아래 코드는 최소 대기 시간보다 버스의 출발 시간이 더 늦으면 바로 넘어가도록 while문 조건식을 설정해서 더 효율적인 탐색이 가능하다.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    private void solution() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int t = Integer.parseInt(st.nextToken());
        int answer = Integer.MAX_VALUE;
        while (n-->0) {
            st = new StringTokenizer(br.readLine());
            int s = Integer.parseInt(st.nextToken());
            int i = Integer.parseInt(st.nextToken());
            int c = Integer.parseInt(st.nextToken());
            while (s < t && --c>0 && s < answer) s+=i;
            if (s >= t) answer = Math.min(s, answer);
        }
        System.out.println(answer == Integer.MAX_VALUE ? -1 : answer-t);
    }

    public static void main(String[] args) throws Exception {
        new Main().solution();
    }
}

 

다음은 이진 탐색으로 구하는 방법이다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    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 T = Integer.parseInt(st.nextToken()); // 영식이가 도착하는 시간
        
        long minWaitingTime = Long.MAX_VALUE; // 최소 대기 시간
        
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            int S = Integer.parseInt(st.nextToken()); // 첫 버스 출발 시간
            int I = Integer.parseInt(st.nextToken()); // 버스 간격
            int C = Integer.parseInt(st.nextToken()); // 버스 대수
            
            // 첫 번째 버스와 마지막 버스의 출발 시간
            long firstBusTime = S;
            long lastBusTime = S + (long)(C-1) * I;
            
            // T 시간 이전에 모든 버스가 출발한 경우는 무시
            if (lastBusTime < T) {
                continue;
            }
            
            // T 시간 이후에 첫 번째 버스가 출발하는 경우는 바로 계산
            if (firstBusTime >= T) {
                minWaitingTime = Math.min(minWaitingTime, firstBusTime - T);
                continue;
            }
            
            // 이진 탐색으로 T 이상인 가장 빠른 버스 시간 찾기
            long waitingTime = binarySearch(S, I, C, T);
            if (waitingTime != -1) {
                minWaitingTime = Math.min(minWaitingTime, waitingTime);
            }
        }
        
        // 결과 출력
        if (minWaitingTime == Long.MAX_VALUE) {
            System.out.println(-1); // 버스를 탈 수 없는 경우
        } else {
            System.out.println(minWaitingTime);
        }
    }
    
    // 이진 탐색을 통해 T 이상인 가장 빠른 버스 시간을 찾고, 대기 시간을 반환
    private static long binarySearch(int S, int I, int C, int T) {
        int left = 0;
        int right = C - 1;
        long result = -1;
        
        while (left <= right) {
            int mid = left + (right - left) / 2;
            long currentTime = S + (long)mid * I;
            
            if (currentTime >= T) {
                result = currentTime;
                right = mid - 1; // 더 빠른 시간을 찾기 위해 왼쪽 탐색
            } else {
                left = mid + 1; // T 이상인 시간을 찾기 위해 오른쪽 탐색
            }
        }
        
        return result == -1 ? -1 : result - T; // 대기 시간 반환
    }
}