쏚쏚스포이드

백준 문자열 잘라내기

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

접근 방식

문제 이해가 엄청 오래 걸렸던 문제..

1000의 범위이기에 Set만 사용해서 처리해도 풀리는 문제 But 공부하기 위해 이분탐색으로 구현!
각 행을 지울 때 마다 바뀌는 세로문자열에 중복값을 있는지 없는지 찾는 문제

구현 방법

• 세로 문자열 전체를 크게 저장할 StringBuilder[] 배열
• 중복체크를 위한 Set자료구조
• 중복에 걸린 것을 확인하기 위한 boolean값 flag

⇒ center는 행의 수라는 ****점을 확실하게 인지하고 진행한다면 할만할 것
행의 수를 center로 잡고 중복 값이 걸렸다면 행이 잘리기 이전 값도 똑같이 중복이란 점을 생각 →

flag 작동 시 right = center - 1;

flag 미작동 시 중복이 걸리지 않았기 때문에 left = center + 1;

풀이

package Baekjoon.gold;

import java.io.*;
import java.util.*;

//행을 지울때 마다 그 때의 세로문자열들 중에 중복값이 있느냐
public class p2866 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer st = new StringTokenizer(br.readLine());
        int r = Integer.parseInt(st.nextToken());
        int c = Integer.parseInt(st.nextToken());

        char[][] a = new char[r][c];

        for (int i = 0; i < r; i++) {
            a[i] = br.readLine().toCharArray();
        }

        StringBuilder[] sb = new StringBuilder[c];

        for (int i = 0; i < c; i++) {
            sb[i] = new StringBuilder();
        }
        for (int i = 0; i < c; i++) {
            for (int j = 0; j < r; j++) {
                sb[i].append(a[j][i]);
            }
        }

        if (r == 2) {
            System.out.println(0);
            return;
        }

        int left = 0;
        int right = r;
        int minValue = Integer.MAX_VALUE;
        boolean flag;
        //center는 행의 수
        while (left <= right) {
            flag = false;
            int center = (left + right) / 2;
            Set<String> set = new HashSet<>();
            for (int i = 0; i < c; i++) {
                String s = sb[i].substring(center, r);
                if (!set.add(s)) {
                    minValue = center;
                    flag = true;
                }
            }

            if (flag) {
                right = center - 1;
            } else {
                left = center + 1;

            }
        }
        if (minValue == Integer.MAX_VALUE) {
            System.out.println(0);
        } else {
            System.out.println(minValue - 1);
        }
    }
}

후기

의외로 이분탐색의 아이디어보다 문제 이해하는데 더 힘들었던 문제… 이분탐색인걸 알고 풀어서 그런 것 같긴 하다. 또 Set만을 사용해도 풀리는 것을 확인했는데 효율이 매우 좋지 않았었음

백준 2805번 나무 자르기
https://www.acmicpc.net/problem/2805

접근 방식

나무 m미터가 필요
절단기의 높이를 이분탐색의 요소
범위가 20억 => long범위로 잡아야할듯? 마지막에 실험해보자

구현 방법

• 이분탐색을 위한 나무 요소중 max값 찾기
• 나무 윗동을 center값으로 잡고 자르기
• 잘랐을 때의 길이를 count로 체크
• count가 m보다 크다면 height 최신화
• count는 길이를 더해줘야하는데 길이의 범위가 20억이기 때문에 20억 이상이되는 수가 나올 것임. count ⇒ long선언

⇒

나무를 아껴서 가장 최소의 m만 챙겨야하기 때문에!!! 절단기 설정 높이는 높아야 하는 것
가장 높은 것을 기준으로 이분탐색

4 7
20 15 10 17

이 테스트케이스에서는 20이 가장 높다
->
이분탐색의 범위를 1 ~ 20까지로 정함
중간부터 시작해서 쭉 돌려
만약에 범위안에 갯수가 맞다면 10
틀리면 왼쪽으로 가야겠지 => 이 높이에선 최소나무길이가 안맞기때문
맞으면 오른쪽으로 가야겠지 => 가장 조금 나무를 잘라야하니까

풀이

import java.io.*;
import java.util.*;

public class p2805 {
    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 m = Integer.parseInt(st.nextToken());

        int[] a = new int[n];
        st = new StringTokenizer(br.readLine());
        int right = Integer.MIN_VALUE;
        for(int i = 0; i < n; i++){
            a[i] = Integer.parseInt(st.nextToken());
            right = Integer.max(right, a[i]);
        }

        int left = 1;
        long height = 0;
        while(left <= right){
            long count = 0;
            int center = (left + right) / 2;
            //나무 윗동을 center값 기준으로 자르기
            for(int i = 0; i < n;i++){
                if(a[i] >= center){
                    count += a[i] - center;
                }
            }

            if(count >= m){
                height = center;
                left = center + 1;
            }else{
                right = center -1;
            }

        }

        System.out.println(height);

    }
}

후기

전형적인 이분탐색 문제 조금만 익숙해진다면 쉬운 이분탐색은 금방 풀 수 있을 것 같다.

1920번 수 찾기

1920번: 수 찾기 (acmicpc.net)

첫째줄 n입력
둘째줄 n갯수 입력
셋째줄 m입력
넷째줄 m갯수 입력

m이 n에 있는지 탐색 후 1(true) 0(false)출력

일단 그냥 구현했을 때 실패했음 원인은 시간초과

알고리즘쪽 보니까 이분탐색하는 부분이 있더라...
이분탐색 구현해보고있는데 배열로 탐색하는 버전은 너무 어색하더라...
내일 for문으로 다시 구현해봐야할듯

for문 통해서 이분탐색 했는데 nextint로는 속도가 안나옴. 또 첫 구현에서는 탐색하는 수들도 전부 배열로 넣어서그런지
시간이 압도적으로 부족한 느낌이 들었음...
때문에 결국 bufferedReader, StringTokenizer를 사용해서 입출력속도를 많이 올렸다.

이제부턴 무조건 써야하나... 타입에 익숙해져야할듯
실버 4 문제인데 이틀을 썼다... 그래도 풀었을 때 상당히 기뻤음.
시간초과 -> 출력초과 -> 틀렸습니다 무한반복... 이분탐색 구현에 자꾸 빼먹는게 생겨서 그런가 참 힘들었다...
반례찾는것도 어렵고... 본인이 반례를 생각하려 노력해야하는데 쉽지않음
탐색이 주 문제니까 sort는 그냥 array.sort를 사용했고, 탐색을 직접 구현해봤다. 이분탐색 어려워징징징

--------

hint
이분탐색을 잘 구현해내면 된다.
내가 헷갈린 부분은 시간이 중요하니까
처음엔 배열 두개를 만들었는데
두개 만들 필요가 없는 걸 잘 생각해서 하면 될듯

--------

solution

실행시간 - 1272ms (이거맞냐....) 자바라 봐준거같은데 sort 직접 구현했으면 시간초과 걸렸을듯

약 2일 소요.... ㅜㅜㅜㅜ 실버가 이런데 더 올라갈 수 있을까...