[JAVA] 백준 이진탐색 - 골드모음(2467 용액, 2866 문자열 잘라내기, 8983 사냥꾼)

 

2467 용액 - 골드5

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

2467번: 용액

 

• 이전에 비슷한(같은) 문제를 푼 적이 있는데, 그 때는 포인터 2개를 이용하여 문제를 풀었다
• 이번에는 이진탐색으로 풀어보려고 한다

 

• 산성과 알칼리 용액 모두 합쳐 오름차순 정렬한다
• 알칼리 용액들을 하나씩 빼면서 배열에서 내 절댓값과 가장 가까운 값을 찾는다
  • [작음, 작음, (같거나)큼, 큼, 큼, ...] 이런 꼴로 나올 것이기 때문에 lowerbound를 구해준다
  • lowerbound값과 lowerbound-1 값과 절댓값과의 차이를 구한 뒤, 차이가 작은 값을 min으로 갱신해준다
  • 산성용액(양수) 2개가 빠질 때까지 반복함

 

풀이

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

    for (int i=0; i<cnt; i++)
      water[i] = Integer.parseInt(st.nextToken());

    Arrays.sort(water);

    int min = Integer.MAX_VALUE;

    int resultMin = -1;
    int resultMax = -1;

    int firstPlus = 0;
    for (int i =0; i<cnt; i++) {
      int w = water[i];

      //양수값 처리
      if (w > 0) {
        if (firstPlus == 0) {
          firstPlus = w;
          continue;
        } else {
          int sum = w + firstPlus;
          if (sum < min) {
            min = sum;
            resultMin = firstPlus;
            resultMax = w;
          }
          break;
        }
      }

      //절댓값과 가장 가까운 값 찾기
      if (i+1 < cnt) {
        int val = binarySearch(w, i+1, water);
        if (Math.abs(val+w) < min) {
          min = Math.abs(val+w);
          resultMin = w;
          resultMax = val;
        }
      }
    }

    System.out.println("" + resultMin + " " + resultMax);
  }

  //합의 최솟값 구하기
  private static int binarySearch(int val, int idx, int[] water) {
    int endIdx = water.length;
    int target = -val;
    int startIdx = idx;

    while (startIdx < endIdx) {
      int midIdx = (startIdx + endIdx)/2;

      //lowerbound구해주기
      if (water[midIdx] < target)
        startIdx = midIdx+1;
      else
        endIdx = midIdx;
    }

    //startIdx가 범위를 벗어났을 때 처리
    if (startIdx >= water.length)
      return water[startIdx-1];

    //작은 값과도 비교
    if (startIdx-1 >= idx && Math.abs(target-water[startIdx-1]) < Math.abs(water[startIdx] -target))
      return water[startIdx-1];
    else
      return water[startIdx];
  }
}

• 모든 값을 water[] 배열에 받고 오름차순 정렬한다
• 배열에서 음수값들을 하나씩 빼서 idx+1 ~ water.length-1 범위에서 나의 절댓값과 가장 가까운 값을 찾는다 (binarySearch 함수 호출)
  • 구한 값과 나의 합의 절댓값이 min보다 절댓값에 가깝다면 min을 갱신하고, resultMin과 resultMax를 저장한다
  • 만약 배열에서 양수값이 2개 이상 빠졌을 경우엔 두 합을 min과 비교&갱신하고 for문을 끝낸다
    • 양수값은 자기 다음으로 큰 양수 외에는 답이 될 수 없기 때문에 계산할 필요가 없음
• 마지막에 남은 min을 출력한다

 

 

2866 문자열 잘라내기 - 골드5

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

2866번: 문자열 잘라내기

• 행마다 동일한 문자열이 발견되는 꼴은 다음과 같다
• [x, x, x, o, o, o, ...]
  • 이렇게 어느 시점부터 동일한 문자열이 절대 나오지 않을 것이다
  • 가능한 lowerbound를 찾고 -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 rowCnt = Integer.parseInt(st.nextToken());
    int colCnt = Integer.parseInt(st.nextToken());

    List<StringBuffer> list = new ArrayList<>();

    for (int i=0; i<colCnt; i++)
      list.add(new StringBuffer());

    for (int i=0; i<rowCnt; i++) {
      StringBuffer sb = new StringBuffer(br.readLine());
      for (int j =0; j<colCnt; j++)
        list.get(j).append(sb.charAt(j));
    }

    int startIdx = 0;
    int endIdx = rowCnt+1;

    while (startIdx < endIdx) {
      int midIdx= (startIdx + endIdx)/2;

      if (hasEqualString(midIdx, list))
        endIdx = midIdx;
      else
        startIdx = midIdx+1;
    }

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

  private static boolean hasEqualString(int midIdx, List<StringBuffer> list) {
    for (int i=0; i<list.size()-1; i++) {
      for (int j=i+1; j<list.size(); j++) {
        if (list.get(i).substring(midIdx).equals(list.get(j).substring(midIdx)))
          return true;
      }
    }

    return false;
  }
}

• 열마다 만들어지는 문자열을 StringBuffer리스트에 저장한다
• 0행을 startIdx로, 마지막 행+1을 endIdx로 하여 이진탐색을 수행한다
• 만약 인덱스의 윗 행을 다 지웠을 때 동일한 문자열이 존재한다면 왼쪽을 탐색하고, 존재하지 않으면 오른쪽을 탐색한다
• 구해진 lowerbound에 -1을 한 값이 결과이다

 

저번에 문제를 풀다 String값을 너무 많이 만들었더니 메모리 초과가 발생한 적이 있었다. 그래서 최대한 StringBuffer를 썼는데, 이 방법이 맞는지는 모르겠다. 그래서 구글링을 해봤다!

 

 

다른 풀이

1. char[][] 배열에 저장하여 한 글자씩 비교하심
   • 비교할 때는 String[] 배열을 만들고, subString을 copyOfRange로 만드심
2. char[][] 배열에 마찬가지로 저장
   • HashSet의 contains메서드를 이용하여 String끼리 같은지 비교함
   • HashSet이 시간이 확실히 덜 걸렸다! 
   • ArrayList의 contains메서드를 사용할 수도 있었다. (이 경우 String 배열로 바꾸는 작업이 필요함)

 

 

교훈: 배열 내에서 전체 비교가 필요한 경우 HashSet을 쓰자! 3배 이상 빨라짐

 

 

 

8983 사냥꾼 - 골드4

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

8983번: 사냥꾼

 

풀이법 생각

• 동물과의 거리를 신기하게 계산한다 (가는 길이 4 이하 이런식으로 하는듯)
• 먹이들을 돌면서 나를 사냥할 수 있는 사대가 있는지 확인할 생각이다
• 먼저 사대를 오름차순 정렬한 후
• 먹이의 좌표가 (a,b)라면
  • b가 L이하인지 확인 후
  • 사대에서 a값과 가장 가까운 값의 lowerbound를 구한다 (크거나 같은 값이 나올거임)
  • 사대[lowerbound]와 사대[lowerbound-1]값을 보고, 나를 사냥할 수 있는지 확인한다 -> (a와 차이의 절댓값이 L-b인지 확인)
• 그림으로 그려보면 이런 느낌이다

 

풀이

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

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 shotCnt = Integer.parseInt(st.nextToken());
    int animalCnt = Integer.parseInt(st.nextToken());
    int range = Integer.parseInt(st.nextToken());

    int[] shot = new int[shotCnt];
    st =  new StringTokenizer(br.readLine());

    for (int i=0; i<shot.length; i++)
      shot[i] = Integer.parseInt(st.nextToken());

    Arrays.sort(shot);

    int result = 0;

    for (int i=0; i<animalCnt; i++) {
      st = new StringTokenizer(br.readLine());

      int a = Integer.parseInt(st.nextToken());
      int b = Integer.parseInt(st.nextToken());

      if (b > range)
        continue;

      int startIdx = 0;
      int endIdx = shot.length;

      //lowerbound구하기 - a와 같거나 큰 값이 나옴
      while (startIdx < endIdx) {
        int midIdx= (startIdx+endIdx)/2;

        if (shot[midIdx] >= a)
          endIdx = midIdx;
        else
          startIdx = midIdx+1;
      }

      boolean canCatch = false;

      //하나 작은 거도 비교
      if (startIdx > 0) {
        if (a - shot[startIdx-1] <= range-b)
          canCatch = true;
      }

      if (startIdx <= shot.length-1) {
        if (shot[startIdx] - a <= range-b)
          canCatch = true;
      }

      if (canCatch)
        result++;
    }

    System.out.println(result);
  }
}

• 사대의 배열을 오름차순 정렬한다 (shot[])
• 먹이 좌표를 받는다
  • 좌표 b(y축) 값이 사정거리보다 짧은지 확인한다
  • 사정거리보다 짧으면 사대배열에서 좌표 a(x축)와 가장 가까운 값을 이진탐색으로 찾아낸다(lowerbound)
  •  구한 lowerbound는 배열의 인덱스를 초과할 수 있기 때문에 확인한 후, lowerbound값과 a와의 차이가 (L-b)보다 짧거나 같다면 잡을 수 있는 먹이로 친다
  • lowerbound가 1보다 크거나 같다면 lowerbound-1 값과도 비교한다. (L-b)보다 짧거나 같으면 잡을 수 있는 먹이로 친다
  • 잡을 수 있으면 result를 +1해줌

 

• 서브테스크가 있는 문제는 처음 풀어본다! 

 

 

 

 

 

 

이진탐색에 대해서 많이 알게된 것 같다. 다음엔 dp문제들을 풀어볼 생각이다