[백준][Java] 19637 IF문 좀 대신 써줘 - 실버3

문제 보기

https://www.acmicpc.net/problem/19637

 

 

풀이

실버 3인데 막혀서 다른 사람들의 풀이를 참고하면서 했다.

보통 30분 안에 끝내고 넘어 가는데 자존심과 자존감이 조금 상했다...

 

참고한 블로그

https://stdio-han.tistory.com/244

백준 19637: IF문 좀 대신 써줘 [JAVA]

 

아무래도 내가 알고리즘을 개념부터 공부한 게 아니라 무작정 코테를 풀어보며 감으로만 익혔다 보니 밑천이 드러난 게 아닌가 싶다 ㅋㅋ

 

1. 칭호를 저장하는 부분

BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] inputs = br.readLine().split(" ");
int N = Integer.parseInt(inputs[0]);
int M = Integer.parseInt(inputs[1]);

String[][] ranks = new String[N][2];
for(int i = 0; i < N; i++) {
  inputs = br.readLine().split(" ");
  ranks[i][0] = inputs[0];
  ranks[i][1] = inputs[1];
}

 

Java 기본 라이브러리에 tuple이 없어서 2차원 배열을 사용해 칭호와 커트라인을 저장하였다.

 

2. 이진 탐색

BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
for(int i = 0; i < M; i++) {
  int power = Integer.parseInt(br.readLine());

  int low = 0;
  int high = N - 1;
  while(low <= high) {
    int mid = (low + high) / 2;
    int midInt = Integer.parseInt(ranks[mid][1]);
    if(power <= midInt) {
      high = mid - 1;
    } else if(power > midInt) {
      low = mid + 1;
    }
  }

  bw.write(ranks[low][0] + "\n");

}

 

이 문제의 핵심은 이분 탐색이다.

원래 if문으로 모든 칭호를 대입해보며 캐릭터에 맞는 칭호를 찾는 방법도 있으나 최대 10^5 * 10^5시간이 걸리게 된다.

시간 제한이 엄격한 문제이기 때문에 정답은 아니다.

 

대신 이분 탐색은  O(logN)의 시간 복잡도를 가지고 있기 때문에 시간이 훨씬 줄어들게 된다.

 

정석적인 이분 탐색 예제에서는 mid가 해당 값과 일치했을 경우 반복문을 탈출하지만,

여기서는 특정 수보다 크거나 같은 수 중 제일 작은 수를 찾는 것이기 때문에 반복문이 끝나기를 기다려야 한다.

 

결과적으로 low 값은 key 값과 같아진다.

 

이렇게 이분 탐색 중에서도 특정한 제일 작은 수, 제일 큰 수를 찾는 것을 lower bound, upper bound라고 부른다.

https://yoongrammer.tistory.com/105

Lower bound & Upper bound 개념 및 구현

나도 아직 완벽하게 이해하지 못한 개념이기 때문에 대신 다른 사람의 블로그를 링크하였다.

 

 

전체 코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

public class Main {
  public static void main(String[] args) throws IOException {

    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    String[] inputs = br.readLine().split(" ");
    int N = Integer.parseInt(inputs[0]);
    int M = Integer.parseInt(inputs[1]);

    String[][] ranks = new String[N][2];
    for(int i = 0; i < N; i++) {
      inputs = br.readLine().split(" ");
      ranks[i][0] = inputs[0];
      ranks[i][1] = inputs[1];
    }

    BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    for(int i = 0; i < M; i++) {
      int power = Integer.parseInt(br.readLine());

      int low = 0;
      int high = N - 1;
      while(low <= high) {
        int mid = (low + high) / 2;
        int midInt = Integer.parseInt(ranks[mid][1]);
        if(power <= midInt) {
          high = mid - 1;
        } else if(power > midInt) {
          low = mid + 1;
        }
      }

      bw.write(ranks[low][0] + "\n");

    }

    bw.flush();
    bw.close();

  }
}

 

 

 GitHub 링크

https://github.com/MetroDefro/CodingTest_AutoSave/tree/main/%EB%B0%B1%EC%A4%80/Silver/19637.%E2%80%85IF%EB%AC%B8%E2%80%85%EC%A2%80%E2%80%85%EB%8C%80%EC%8B%A0%E2%80%85%EC%8D%A8%EC%A4%98

CodingTest_AutoSave/백준/Silver/19637. IF문 좀 대신 써줘 at main · MetroDefro/CodingTest_AutoSave