백준 싫은데요

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

    }
}

후기

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

12755번 수면 장애

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

Comment
진짜 처음엔 별거 없을거라 생각했는데 생각보다 난이도가 높았던 문제
좀 애먹으면서 문제를 풀었던 것 같다. 메모리 제한이 생각보다 너무 컸고, 정답숫자 위치에서 인덱스 범위 잡는 것에 대한 고민...

hint
for문의 범위는 상관없고 번호와 길이를 따로 저장해서 확인하면 좀 편하다.

Solution
temp 인트를 선언해서 길이를 계속 저장해준다! 길이 저장 후 length가 n과 같거나 커졌을 때 for문을 탈출, 해당 i의 값이 n의 범위에 걸친 i이고, for문의 증강연산으로 인해 i-1이 정답번호이다. 여기서 값 추출은 length-n을 통해 0 ~ i.length()-1 까지 위치를 잡아서 출력하는데, 인덱스를 통해 출력하기 때문에 StringBuilder를 만들어서 reverse메서드로 먼저 뒤집어줬다.

솔직히 깔끔하지는 못한 코드지만 그래도 어떻게든 해결했단 것에 만족..!

1680번 쓰레기 수거

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

Comment

일반 시뮬레이션 구현문제라서 평소처럼 풀까하다가 자바스럽게 풀어보고싶어서 객체지향(?)적으로 설계를 하기 위해 노력하면서 구현해보았다.

알고리즘을 풀 때 클래스를 잘 활용하지 않아서 생각보다 많이 오래걸렸던 문제

hint

문제를 잘 읽고 테스트케이스 또한 해당 지문에 맞춰서 잘 이해해야한다.

Solution

메모리나 시간이나 상관없이 구현만 잘하면 되는 문제였다. 때문에 클래스를 만들어서 써보기에 더 좋았던 것 같다.

일단 해당 문제의 1, 2, 3번 조건을 항상 잘 생각해서 염두에 두고 조건을 넣는다면 쉽게 풀리는 문제일 것이다.

1번의 시점은 다음 지점으로 이동하기 전이고, 2번의 시점은 쓰레기를 싣기 전, 3번은 가장 마지막. 이렇게 해당 분기를 잘 확인해서 조건처리만 잘 해준다면 문제 해결은 쉽게 될 것이다.

클래스 활용해서 구현하면 속도가 안나온다....

1417번 국회의원 선거

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

Comment

자료구조를 활용하는 문제중에서 난이도가 쉬웠기에 여러가지 시도해보기 좋았던 문제같다.

처음엔 그냥 자료구조 클래스만 활용할까 하다가 객체도 같이 써보면 재밌지 않을까 해서 같이 사용해봤다

hint

우선순위 큐를 활용했다.

객체를 사용한다면 해당 객체에 Comparable를 상속받아야함

Solution

전체 입력값 자체가 적어서 시간은 볼 필요 없긴 할듯하다

우선순위 큐를 써봤는데 객체에서는 자동정렬을 계속 해주지 않는건지 처음 입력된 우선순위 큐 객체에서만 투표수를 가져가고 있었다. 때문에 이를 해결하기 위해 우선순위 큐에서 득표 수에 변경이 있을 때마다 큐에서 꺼냈다가 다시 넣어주는 형식으로 반복을 했다.

그래도 객체를 기준으로 우선순위 큐를 다루는게 은근 재밌었던 문제

다들 각잡고 준비하면 금방들 찍으시는거 같던데 저는 약 3개월이 걸렸네요...

안좋은 공부머리 억지로 풀어가면서 꾸준히 진행해서 도달했다는거에 만족하고 더 노력해야겠습니다.

참 기분좋은날 이네요

2644번 촌수 계산

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

Comment

 DFS, BFS를  첫 입문할 때 하기 좋은 그래프 문제이다. 해당 문제는 DFS적으로 접근하면 Depth를 잘 활용할 수 있었는데, BFS를 활용해서 풀어볼 때 문제가 생겼었다. 직면했던 문제는 BFS에서는 Depth를 어떤 기준으로 체크할 수 있을까? 라는 고민을 많이 하게 한 문제였다.

hint

DFS, BFS 두가지 방법 모두 풀린다.

하지만 체감 난이도는 BFS가 더 어려웠던 것 같다.

Solution

• DFS

재귀호출할 때 매개변수를 통해서 해당 깊이를 더해가며 풀어보니 잘 해결되었다.

• BFS

내가 만질 때는 null을 Queue에 넣어서 구분자로 생각하고 null을 만날 때마다 count가 1씩 증가하도록 구현했었는데, 좀 더 직관적인 방법이 좋았을거라 생각했고, 스터디를 진행하는 다른 사람이 푼 것을 봤을 때 distance라는 배열을 만들어서 해당 값을 누적되게 구현했는데 더 좋은 방법 같았다.

어쨌든 그래프에서 DFS, BFS를 둘 다 사용해보기에 좋은 문제였던 것 같다!