백준 싫은데요

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

접근 방식

전형적인 투 포인터 형태로 햄스터의 몸집을 구멍을 막았을 때 구멍의 크기m에 최대한 가까운 수를 찾아 출력하는 문제

구현 방법

• 탐색 했을 때 최대값을 찾을 max값
• 누적합을 계산해 줄 count
• 투 포인터에 활용할 left, right

⇒ while문 안에서 count의 값이 m보다 크면 left의 값을 count에서 뺀 후 left++, count의 값이 m보다 작거나 같으면 right의 값을 count에 더한 후 right++ 이 때 max의 값와 카운트의 값을 비교해 최댓값을 갱신

풀이

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

public class p25916 {
    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());
        for (int i = 0; i < n; i++) {
            a[i] = Integer.parseInt(st.nextToken());
        }
        //8 10
        //2 2 2 2 11 2 5 2
        //9

        int left = 0;
        int right = 0;
        int max = Integer.MIN_VALUE;
        int count = 0;
        while (right < n) {
            if (count +a[right] <= m) {
                count += a[right];
                max = Integer.max(max, count);
                right++;
            }else{
                count -= a[left];
                left++;
            }
        }

        System.out.println(max);

    }
}

후기

투 포인터에 익숙해지기 좋은 문제였다

백준 계란으로 계란치기

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

백준 골드5 계란으로 계란치기

접근 방식

Egg 클래스를 선언해서 왼쪽부터 순서대로 들어서 해결

모든 경우의 수를 탐색해야 하기에, 백트래킹으로 진행

구현 방법

• Egg클래스
  • isBroken : 깨져있는지 확인
  • breakEgg : 대상이 깨져있는지 확인 후 공격
  • attackEgg : 서로 공격
• 깊은 복사를 위한 deepCopy 메서드
• 백트래킹

⇒

알을 꺼내는 방식은 순차적
꺼낸 알을 갖고 모든 알들에 시도해보기 (모든 경우의 수 탐색)
이후 최종 깊이에 도달하면 Egg의 깨져있는 수를 카운트

풀이

package Baekjoon.gold;

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

public class p16987 {

    static int n;
    static int max = 0;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        n = Integer.parseInt(br.readLine());
        ArrayList<Egg> eggList = new ArrayList<>();
        StringTokenizer st;

        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            eggList.add(
                    new Egg(
                            Integer.parseInt(st.nextToken()),
                            Integer.parseInt(st.nextToken())
                    )
            );
        }

        if (n == 1) {
            System.out.println(0);
            return;
        }
        boolean[] visited = new boolean[n];
        dfs(eggList, 0, 0);

        System.out.println(max);

    }

    public static void dfs(List<Egg> prevEggList, int index, int depth) {
        if (depth == n) {
            //전체 브로큰 횟수 출력
            max = Integer.max(brokenCount(prevEggList), max);
            return;
        }

        for (int i = 0; i < n; i++) {
            List<Egg> nowEggList = deepCopy(prevEggList);
            Egg nowEgg = nowEggList.get(depth);
            if (i != depth) {
                nowEgg.breakEgg(nowEggList.get(i));
                dfs(nowEggList, 0, depth + 1);
            }
        }

    }

    static int brokenCount(List<Egg> eggList) {
        int count = 0;
        for (int i = 0; i < n; i++) {
            if (eggList.get(i).isBroken()) {
                count++;
            }
        }
        return count;
    }

    static class Egg {
        int durability;
        int weight;

        Egg(int durability, int weight) {
            this.durability = durability;
            this.weight = weight;
        }

        public void breakEgg(Egg egg) {
            if (!egg.isBroken() && !this.isBroken()) {
                attackEgg(egg);
            }
        }

        private void attackEgg(Egg egg) {
            int a = this.weight;
            int b = egg.weight;
            this.durability -= b;
            egg.durability -= a;
        }

        private boolean isBroken() {
            if (durability <= 0) {
                return true;
            }
            return false;
        }

    }

    public static List<Egg> deepCopy(List<Egg> eggList) {
        ArrayList<Egg> tempList = new ArrayList<>();
        for (int i = 0; i < eggList.size(); i++) {
            Egg temp = eggList.get(i);
            tempList.add(new Egg(temp.durability, temp.weight));
        }
        return tempList;
    }
}

후기

문제 구현이 생각보다 어려웠는데 이유를 모르겠음…
굳이 이유를 꼽자면 Egg의 상태를 확인해줄 때 헷갈렸던 것 같다.

속도는 클래스를 활용해서 그런지 상당히 느림 매번 깨져있는지 확인하면서 더 돌아서 느린듯?

백준 문자열 잘라내기

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);

    }
}

후기

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

백준 16401 과자 나눠주기

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

접근 방식

길이를 기준으로 이분탐색, 과자의 개수에 따라서 m명의 조카에게 나눠줄 수 있는지 판단하는 것이 중요!

구현 방법

• 이분탐색을 위한 범위
• 과자를 활용할 배열

⇒

배열로 과자를 입력받은 후 받은 과자 배열의 요소를 모두 탐색 → 이분탐색의 중앙값을 기준으로 해당 과자의 갯수를 카운트하고, 카운트의 갯수와 입력받은 m의 수가 일치한다면 과자를 동일한 길이로 줄 수 있는 것이기 때문에 해당 값을 정답에 저장 → 길이가 포함된다면 이분탐색 피벗기준 우측, 포함되지않으면 피벗기준 좌측

풀이

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

public class p16401_2 {
    public static void main(String[] args) throws IOException{
        BufferedReader br =new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer st = new StringTokenizer(br.readLine());
        int m = Integer.parseInt(st.nextToken());
        int n = Integer.parseInt(st.nextToken());
        int[] a = new int[n];

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

        Arrays.sort(a);
        int maxCookieLength = 0;
        int left = 1;
        int right = a[n-1];
        while(left <= right){
            int count = 0;
            int center = (left + right) / 2;
            //m을 기준으로 몇개가 나오는지 카운트
            for(int i = 0; i <n; i++){
                count += a[i]/center;
            }

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

        System.out.println(maxCookieLength);

    }
}

후기

이분탐색임을 알고 시작했는데, 아직 익숙하지 않아서 접근이 어려웠다.

백준 11559 Puyo Puyo

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

Comment
기본적인 탐색 + 구현 시뮬레이션 문제
확실히 구현이 들어가니까 실수하는게 생기고 실수했을 때 원인찾기가 어렵다. 지금은 디버깅으로 가능하지만 코테에서는 신경을 많이 써서 해야할 듯?

Hint

• 기본적인 BFS이동을 담을 movePoint
• 방문체크 visited
• 게임판 puyoMap
• 연쇄횟수
• 매 라운드가 있어야하기에 puyoClear(boolean)
• 연쇄가 발생했을 때 뿌요를 지울 ArrayList

아직 깔끔하게 구현은 못하겠지만 어느걸 써야할지는 계속 생각하며 풀어야 함

Solution
1. 탐색하고 탐색된 좌표 저장
2. 탐색된 좌표가 4개 이상일 때 puyoClear = true, 실제로 지울 clearPuyoMap List에 추가
3. clearPuyoMap 기반으로 뿌요들을 아래로 내려줌
4. 한번 지워진 상태(puyoClear == true)라면 1~3 반복

큰 흐름은 위의 순서로 진행된다.
값 초기화 잘 신경써서 해주면 크게 어렵지는 않다.