백준 싫은데요

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

    }
}

후기

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

백준 29812 아니 이게 왜 안돼

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

접근 방식

문자열 자체를 입력받은 후 문자열의 위치를 저장하는 Queue에 담았다.

queue를 통해 각 요소를 소비하며 문자가 2개 이상일때는 그리디의 조건인 드래그 없는 문자만 삭제하는게 저렴한지, 드래그한 후에 삭제하는 것이 저렴한지 구분하며 각 에너지를 더해주고, 이후 HYU의 개수를 기준으로 H,Y,U중 수가 적은 것을 기준으로 HYU묶음 개수를 출력

묶음이 있어서 이번에 배워본 groupingBy를 활용했는데, 아마 더 상세하게 바꿀 수 있을 것 같은데 아직 많이 헷갈려서 제대로 활용은 못해봤다 아직은 사용하면서 익숙해지는데 더 힘을 써봐야겠다.

구현 방법

• 그리디 조건을 위한 문자 길이체크 count
• HYU가 아닌 인덱스 위치를 담아둔 Queue
• 각 스트림 매핑 후 H,Y,U를 담기위한 Map

⇒

Queue의 값을 계속 체크하면서 인덱스 차이가 1 이상이면 범위가 벗어난 것
벗어난 범위 기준으로 {카운트 * d(각 문자를 개별딜리트)} vs {d + m} 비교 후 저렴한 것 선택 후 energe에 합치기

→ HYU매핑은 입력받은 문자열 그대로 다시사용해서 굳이 스트림 .chars로 변환 후 각 요소의 H,Y,U를 각각 맵에 담는 형식으로 구현

기존의 문자열에 .append로 HYU를 굳이 추가했는데 이유는 stream으로 매핑할때
아래의 반례는 Map 안에 H관련한 값만 생기기 때문이였다.
1
H
1 3

풀이

package Baekjoon.silver;

import java.io.*;
import java.util.*;
import java.util.stream.Collectors;

public class p29812 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int energy = 0;
        int n = Integer.parseInt(br.readLine());

        StringBuilder sb = new StringBuilder();
        sb.append(br.readLine()).append("HYU");
        StringTokenizer st = new StringTokenizer(br.readLine());
        int d = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        ArrayList<Map<Integer, int[]>> removeRange = new ArrayList<>();

        Queue<Integer> noHYUList = new LinkedList<>();
        for (int i = 0; i < n; i++) {
            if (!isHYU(sb.charAt(i))){
                noHYUList.add(i);
            }
        }

        boolean flag;

        while(!noHYUList.isEmpty()){
            flag = false;
            final int firstIndex = noHYUList.poll();
            int prevIndex = firstIndex;
            int count = 1;

            while(!noHYUList.isEmpty()){
                int isContinuousIndex = noHYUList.peek();
                if(isContinuousIndex-prevIndex == 1){
                    prevIndex = noHYUList.poll();
                    flag = true;
                    count++;
                }else {
                    break;
                }
            }
            if(!flag || count * d < m+d){
                energy+= d*count;
            }else{
                energy += d + m;
            }
        }

        Map<Integer, List<Integer>> result = sb.toString().chars()
                .boxed()
                .filter(c -> isHYU(c))
                .collect(Collectors.groupingBy(c -> c));

        int min = Integer.MAX_VALUE;
        for(int num : result.keySet()){
            min = Integer.min(result.get(num).size(), min);
        }

        sb = new StringBuilder();
        if(energy == 0){
            sb.append("Nalmeok");
        }else{
            sb.append(energy);
        }
        sb.append(System.lineSeparator());
        if(min == 1 || Integer.MAX_VALUE == min){
            sb.append("I love HanYang University");
        }else{
            sb.append(min-1);
        }
        System.out.println(sb);

    }

    static boolean isHYU(int a) {
        switch (a) {
            case 'H', 'Y', 'U':
                return true;
            default:
                return false;
        }
    }
}

package Baekjoon.silver;

import java.io.*;
import java.util.*;
import java.util.stream.Collectors;

public class p29812 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int energy = 0;
        int n = Integer.parseInt(br.readLine());

        StringBuilder sb = new StringBuilder();
        sb.append(br.readLine()).append("HYU");
        StringTokenizer st = new StringTokenizer(br.readLine());
        int d = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());

        Queue<Integer> noHYUList = new LinkedList<>();
        for (int i = 0; i < n; i++) {
            if (!isHYU(sb.charAt(i))) {
                noHYUList.add(i);
            }
        }

        boolean flag;

        while (!noHYUList.isEmpty()) {
            flag = false;
            final int firstIndex = noHYUList.poll();
            int prevIndex = firstIndex;
            int count = 1;

            while (!noHYUList.isEmpty()) {
                int isContinuousIndex = noHYUList.peek();
                if (isContinuousIndex - prevIndex == 1) {
                    prevIndex = noHYUList.poll();
                    flag = true;
                    count++;
                } else {
                    break;
                }
            }
            if (!flag || count * d < m + d) {
                energy += d * count;
            } else {
                energy += d + m;
            }
        }

        Map<HYU, Long> result = sb.toString().chars()
                .filter(c -> isHYU(c))
                .boxed()
                .collect(Collectors.groupingBy((Integer c) -> HYU.valueOf(changeHYU(c)), Collectors.counting()));

        int min = Integer.MAX_VALUE;
        for (Object num : result.keySet()) {
            min = Integer.min(Math.toIntExact(result.get(num)), min);
        }

        sb = new StringBuilder();
        if (energy == 0) {
            sb.append("Nalmeok");
        } else {
            sb.append(energy);
        }
        sb.append(System.lineSeparator());
        if (min == 1 || Integer.MAX_VALUE == min) {
            sb.append("I love HanYang University");
        } else {
            sb.append(min - 1);
        }
        System.out.println(sb);

    }

    static boolean isHYU(int a) {
        switch (a) {
            case 'H', 'Y', 'U':
                return true;
            default:
                return false;
        }
    }

    static String changeHYU(int c) {
        return String.valueOf((char) c);
    }

    private enum HYU {
        H,
        Y,
        U
    }
}

후기

스트림 없이 하면 참 쉽겠지만… 언젠가는 잘 써보고싶어서 계속 활용하면서 일단 익숙해져야할것같다.. 이번에는 스트림을 리팩토링 후에 성능이 더 느려졌는데 아마 boxing하는 비용이 더 많아지고, 중간에 changeHYU를 통해 계속 값을 더해줘서 그럴 것 같았다.

백준 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 반복

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

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

2310번 어드벤처 게임

Comment
문제 이해하는데 한참 걸렸던 문제 생각보다 구현은 엄청 어렵지는 않았다.
문제 이해를 돕자면 각 줄이 1, 2, 3, 4번 방으로 쭉 나열되는 것이고, E,L,T의 상태를 가진 방 으로 생각하면 편할 것 같다.
다들 쉽게 이해하겠지만 저는 좀 힘들었습니다..

Hint

• 기본적인 방의 번호와 상태를 담은 mapList
• 방문을 확인할 배열 visited
• n번방에 도달했는지 확인하는 success

Solution
문제 이해하기까지도 오래 걸리고, 아직 문해력이 부족한건지 모호했던 부분이 많았던 문제 그래도 직접 해결해서 뿌듯하다

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메서드로 먼저 뒤집어줬다.

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

14494번 다이나믹이 뭐예요?

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

Comment

DP문제의 기초격 문제

DP는 기초라고해도 왜이리 생각하기 어려운지 모르겠다..

hint

dp배열의 저장값 : 해당 지점에 도달하는 경우의 수

점화식 : 우측, 하단, 우하단 세가지 경우의 수를 활용

Solution

DP의 기초격 문제라 그런가 DP를 조금 맛본 상태에서 접했더니 점화식이 생각났던 얼마안되는 문제

먼저 dp배열을 만들고 해당 dp배열의 상단(우측으로만 진행하는 경우의 수) 하단(아래로만 진행하는 경우의 수)의 값은 도달하는 방법이 한가지 뿐이다. 때문에 먼저 초기화해서 쭉 1로 채워준 후에 해당 값을 가지고 남은 dp배열 모두를 채워나가면 되는데, 점화식은 위에 hint에 적었던 우측, 하단, 우하단 을 받는 이전dp배열을 가져오면 된다.

즉, dp[i][j] = dp[i - 1][j] + dp[i][j-1] + dp[i-1][j-1]; 로 해결이 된다

그림예시