[JAVA] 백준 이진탐색 - 실버모음2(19637 IF문 좀 대신 써줘, 1654 랜선 자르기)

 

 

 

 

19637 IF문 좀 대신 써줘 - 실버3

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

19637번: IF문 좀 대신 써줘

 

• 칭호는 전투력 상한값의 비내림차순으로 주어진다고 하였다 -> 중복 발생 가능
• 칭호가 여러 개인 경우 가장 먼저 입력된 칭호 하나만을 출력한다고 하였다 -> 중복값이 나오면 그냥 씹으면 됨
• 칭호와 전투력상한선은 100000개까지 나올 수 있기 때문에 순차적으로 탐색하면 시간초과가 날 확률이 높다
  • 이진탐색을 수행함
  • 리스트와 정확히 일치하는 값을 찾기도 힘드니, 리스트에 내가 포함되지 않을 경우에 대한 처리도 필요함
• 직접 구현하는 방식과 Arrays.binarySearch를 이용하는 방식으로 풀어보려고 한다

 

이진탐색 직접구현 풀이

class Main {
  public static void main(String[] args) throws Exception {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer st= new StringTokenizer(br.readLine());

    int nameCnt = Integer.parseInt(st.nextToken());
    int charCnt = Integer.parseInt(st.nextToken());

    List<String> name = new ArrayList<>();
    List<Integer> power = new ArrayList<>();
    int prev = -1;
    for (int i =0; i<nameCnt; i++) {
      st = new StringTokenizer(br.readLine());
      String currName = st.nextToken();

      int currPower = Integer.parseInt(st.nextToken());
      if (currPower != prev) {
        name.add(currName);
        power.add(currPower);
        prev = currPower;
      }
    }

    StringBuffer sb= new StringBuffer();
    for (int i =0; i<charCnt; i++) {
      int current = Integer.parseInt(br.readLine());

      int idx = binarySearch(current, power);
      sb.append(name.get(idx));
      sb.append("\n");
    }

    System.out.println(sb);
  }

  private static int binarySearch(int current, List<Integer> power) {
    int start = 0;
    int end = power.size();

    while (start < end) {
      int mid = (start + end)/2;

      if (power.get(mid) == current)
        return mid;

      if (power.get(mid) >= current)
        end = mid;
      else
        start = mid+1;
    }

    if (power.get(start) >= current)
      return start;
    else
      return start-1;
  }
}

• 전투력이 중복될 경우 씹어야하기 때문에 ArrayList를 사용하여 칭호와 전투력 상한선을 받았다
• 전투력을 받아 바이너리서치 함수를 호출하여 인덱스를 받는다
• 해당 인덱스에 대한 칭호를 출력
• 바이너리 서치 함수
  • 일단 이진탐색을 수행한다
  • 만약 값이 같을 경우에는 해당 인덱스를 return할 것인데, 대부분은 그렇지 않음
  • 대부분은 start가 end와 같아져서 while문을 빠져나올 것이다
  • 빠져나온 값은 원하는 전투력보다 값이 크거나 작을 수 있음 -> 크거나 같으면 해당 인덱스를, 작으면 인덱스-1을 return해준다 
  • (start가 클 경우 start-1이 0미만이 되는 경우는 입력으로 들어오지 않음)

 

컬렉션 함수 사용

class Main {
  public static void main(String[] args) throws Exception {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer st= new StringTokenizer(br.readLine());

    int nameCnt = Integer.parseInt(st.nextToken());
    int charCnt = Integer.parseInt(st.nextToken());

    List<String> name = new ArrayList<>();
    List<Integer> power = new ArrayList<>();
    int prev = -1;
    for (int i =0; i<nameCnt; i++) {
      st = new StringTokenizer(br.readLine());
      String currName = st.nextToken();

      int currPower = Integer.parseInt(st.nextToken());
      if (currPower != prev) {
        name.add(currName);
        power.add(currPower);
        prev = currPower;
      }
    }

    StringBuffer sb= new StringBuffer();
    for (int i =0; i<charCnt; i++) {
      int current = Integer.parseInt(br.readLine());

      int idx = Collections.binarySearch(power, current);

      if (idx >= 0)
        sb.append(name.get(idx));
      else
        sb.append(name.get(-idx-1));
      sb.append("\n");
    }

    System.out.println(sb);
  }
}

• binarySearch 메서드는 값을 발견한 경우 해당 값의 인덱스를 출력하고, 값이 없을 경우 -(내가 삽입될 인덱스)-1 의 값이 return된다
• 이 점을 이용하여 원하는 인덱스에 맞는 칭호를 호출하면 되겠다! 

 

• 둘 다 시간과 메모리 비슷하게 나오는듯

 

 

 

 

1654 랜선 자르기 - 실버2

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

1654번: 랜선 자르기

 

• 이진탐색에서 lowerbound와 upperbound라는 게 있는데, 지금까지는 헷갈려서 익숙해지는 것에만 집중했다
• 이제는 알 때가 와서 블로그에 정리를 했다
  • 정리한 글: https://fladi.tistory.com/335
  • 참고한 블로그: https://st-lab.tistory.com/267
• 이 문제는 이진탐색을 활용한 문제이다
• 원하는 값의 위치를 제대로 특정해야하기 때문에 lowerbound와 upperbound를 머리에 제대로 정리해둬야 풀기 쉬울 것 같다

 

풀이법 생각

1. 랜선의 최대 길이를 받아 maxLen에 저장 (= 만들 수 있는 랜선 최대길이)
2. 0부터 maxLen까지 이진탐색으로 가능한 랜선길이를 구함 (이진탐색 대상은 0~maxLen 랜선길이)
3. 이진탐색은 upperbound를 사용하였다
   • 만들 수 있는 경우가 다음과 같이 나올 것이기 때문 
   • [가능, 가능, 가능, 가능, 불가능, 불가능, ...]
   • upperbound는 (가능한 마지막 길이) + 1 가 나오기 때문에 결과에 -1을 해주면 가능하면서 가장 긴 값을 얻을 수 있다

 

class Main {
  public static void main(String[] args) throws Exception {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer st= new StringTokenizer(br.readLine());

    int wireCnt = Integer.parseInt(st.nextToken());
    int requiredCnt = Integer.parseInt(st.nextToken());
    int[] wire = new int[wireCnt];

    long maxLen = 0;
    for (int i =0; i<wireCnt; i++) {
      wire[i] = Integer.parseInt(br.readLine());
      if (maxLen < wire[i])
        maxLen = wire[i];
    }

    maxLen++;
    long minLen = 0;

    while (minLen < maxLen) {
      long midLen = (minLen+maxLen)/2;

      long cnt = 0;
      for (int w: wire)
        cnt += (w/midLen);

      if (cnt >= requiredCnt)  //upperbound
        minLen = midLen + 1;
      else
        maxLen = midLen;
    }

    System.out.println(minLen-1);
  }
}

 

 

 

 

 

 

 

이진탐색에 대해 꽤 많이 알게된 것 같다!!ㅎㅎ 

용액문제에서 이진탐색 하나 구현못해서 절망했는데, 익숙해지니 어렵지 않고 재미있다.

조금 더 응용해보고 다른 유형으로 넘어가야겠당