피로도

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

접근

• 24시간 동안 피로도 M을 넘기지 않고 최대한 많이 일을 할 수 있는지 구하는 문제
• 24번 반복문을 돌리면서 현재 피로도 + A ≤ M 인지 파악하면서 가능하면 일하고(+ A) 아니면 쉬게한다(- C)
• 일할때마다 총 일하는 크기를 더해간다(+ B)
• 피로도가 음수로 내려가면 0으로 바꿔준다

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Scanner;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int A, B, C, M;
        int tiredness = 0;
        int answer = 0;
        A = Integer.parseInt(st.nextToken());
        B = Integer.parseInt(st.nextToken());
        C = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        for (int i = 0; i < 24; i++) {
            if (tiredness + A <= M) {
                tiredness += A;
                answer += B;
            } else {
                tiredness -= C;
                if (tiredness < 0) {
                    tiredness = 0;
                }
            }
        }

        System.out.println(answer);
    }
}

회고

• 문제를 잘 읽도록 하자. 다소 쉬운 문제지만 문제를 꼼꼼히 읽지 않아서 생기는 오류가 많았다. 예를 들면 피로도가 음수일때 0으로 한다, 피로도가 M을 넘기면(≤) 번아웃이다.
• 시간 복잡도 : O(1)
• 공간 복잡도 : O(1)

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

• 접근

처음에는 while 반복문 돌리면서 3으로 나누기, 2로 나누기, 1빼기 순으로 각 조건을 확인해서 count를 세는 간단한 문제인줄 알았다.

하지만 두번째 테스트 케이스를 보면 10의 경우 10 -> 9 -> 3 -> 1 순으로 3번 만에 만들 수 있지만 위 방식으로 풀게되면 10 -> 5 -> 4 -> 2 -> 1 (2로 나누기 부터 적용되기 때문에) 4번으로 최소 횟수가 안되는 함정이 있다.

다시 접근해보면 메모이제이션을 이용한 재귀를 떠올려볼 수 있다.

• 코드

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        Integer[] arr = new Integer[1000001];
        arr[0] = arr[1] = 0;
        System.out.println(recur(arr, N));
    }

    public static int recur(Integer[] arr, int N) {
        if (arr[N] == null) {
            if (N % 6 == 0) {
                arr[N] = Math.min(recur(arr, N - 1), Math.min(recur(arr, N / 3), recur(arr, N / 2))) + 1;
            } else if (N % 3 == 0) {
                arr[N] = Math.min(recur(arr, N / 3), recur(arr, N - 1)) + 1;
            } else if (N % 2 == 0) {
                arr[N] = Math.min(recur(arr, N / 2), recur(arr, N - 1)) + 1;
            } else {
                arr[N] = recur(arr, N - 1) + 1;
            }
        }
        return arr[N];
    }

}

• 해설

6으로 나눠떨어지는 경우 3가지 연산 방법 중 최소값을 찾아가야한다.

3으로 나눠떨어지는 경우는 2로 나눌수 없으니 2 나누기를 제외한 2가지 연산 방법 중 최소값을 재귀호출!

2으로 나눠떨어지는 경우도 3으로 나누는 것과 마찬가지!

이외에 나눠떨어지지 않으면 1을 빼는 연산 방법을 마지막으로 재귀호출한다.

• 다른 풀이

재귀 함수 매개변수를 통해 count 값을 넘겨주면서 진행하는 방법이 있다.

• 회고

메모이제이션까지 방법을 생각해냈지만 구현까지 성공하지 못했다.

계속 문제를 풀면서 구현 능력을 키우면 쉽게 구현할 수 있을 것 같다.

시간 복잡도 O(N)...?

공간 복잡도 O(N)

바텀 - 업 방법으로도 구현해보자

• 참고

https://st-lab.tistory.com/133

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

문제 분석

• 명령어로 동작하는 정수를 저장하는 스택 구현기

접근

• 각 명령어에 대한 함수 만들고
• 클래스 만들고 멤버 변수로 스택명령어 입력 받는 함수 만들기

오류

• 시간초과 오류났는데 입력받는 시간이 오래걸린다고 함 Scanner -> BufferedReader 사용
  • Scanner는 원시타입과 String 파싱 등 정규 표현식 적용, 입력값 분할, 파싱 과정을 거치기 때문에 낮은 퍼포먼스
  • BufferedReader는 입력을 버퍼에 모아두었다가 한번에 그 내용을 전달하기 때문에 빠른 속도
  • 왜 더 빠를까?
  • Scanner도 버퍼로 입력받는걸로 이해했는데...?

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Scanner;
import java.util.Stack;

public class Main {
    static BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));

    public static void main(String[] args) throws IOException {
        StackClass stackClass = new StackClass();
        int totalCommandCount = Integer.parseInt(bf.readLine());

        for (int i = 0; i <= totalCommandCount; i++) {
            stackClass.execute(bf.readLine());
        }
    }

    private static class StackClass {
        private Stack<Integer> stack = new Stack<>();

        public StackClass() {
        }

        public void execute(String command) {
            if (command.startsWith("push")) {
                String[] split = command.split(" ");
                push(Integer.parseInt(split[1]));
            }

            if (command.equals("pop")) {
                pop();
            }
            if (command.equals("size")) {
                size();
            }
            if (command.equals("empty")) {
                empty();
            }
            if (command.equals("top")) {
                top();
            }
        }

        private void push(int x){
            stack.push(x);
        }

        private void pop() {
            if (stack.isEmpty()) {
                System.out.println(-1);
                return;
            }
            System.out.println(stack.pop());
        }

        private void size() {
            System.out.println(stack.size());
        }

        private void empty() {
            if (stack.isEmpty()) {
                System.out.println(1);
                return;
            }
            System.out.println(0);
        }

        private void top() {
            if (stack.isEmpty()) {
                System.out.println(-1);
                return;
            }
            System.out.println(stack.peek());
        }
    }
}

회고

• 이번 문제도 if문을 나열해서 풀었는데 가독성 면에서는 스위치문이 좋고 성능면에서는 else if가 좋을것 같다는 피드백을 받았다
• 확실히 스위치문으로 보니 가독성이 올라간다고 느껴졌다

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

public class Main {
    public static void printValue(Integer value) {
        System.out.println(value == null ? -1 : value);
    }

    public static void main(String[] args) throws IOException {
        Deque<Integer> deque = new LinkedList<>();
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        StringTokenizer st;
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            String command = st.nextToken();
            switch (command) {
                case "push_front":
                    deque.addFirst(Integer.parseInt(st.nextToken()));
                    break;
                case "push_back":
                    deque.addLast(Integer.parseInt(st.nextToken()));
                    break;
                case "pop_front":
                    printValue(deque.pollFirst());
                    break;
                case "pop_back":
                    printValue(deque.pollLast());
                    break;
                case "size":
                    printValue(deque.size());
                    break;
                case "empty":
                    printValue(deque.isEmpty() ? 1 : 0);
                    break;
                case "front":
                    printValue(deque.peekFirst());
                    break;
                case "back":
                    printValue(deque.peekLast());
                    break;
            }
        }
    }
}

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

분석

• 레이저는 반드시 인접한 () 쌍으로 표현
• 나머지 떨어진 괄호`()`가 쇠막대기로 표현됨
• 잘려진 쇠막대기는 총 몇조각인가? 를 구하는 문제

접근

• 스택으로 하는게 좋을 것 같음
• ( 나오면 스택에 넣고
• ) 나오면 pop() 하고 스택 사이즈 만큼 더해주면 될 것 같음
• 예시 시뮬레이션을 돌려보니 3 + 3 + 2 + 3 + 2 + 2 + 1 + 1 = 17 맞음

오류

• 두번째 예시 틀렸음
• )로 레이저 말고 쇠막대기를 닫을때는 stack size 만큼이 아니라 +1 해주면 된다

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String parentheses = br.readLine();
        Stack<Character> stack = new Stack<>();
        int count = 0;
        char prev = '(';
        for (char c : parentheses.toCharArray()) {
            if (c == '(') {
                stack.push(c);
            }
            if (c == ')') {
                if (prev == '(') {
                    stack.pop();
                    count += stack.size();
                } else {
                    count++;
                    stack.pop();
                }
            }
            prev = c;
        }

        System.out.println(count);
    }
}

회고

• if 문을 왜 나열했을까? -> else if()를 사용해서 하나만 체크하고 넘어가는 식으로 만드는 것이 오류를 줄일 수 있을 것 같다
• stack.pop()이 공통으로 중복되므로 하나로 빼서 중복을 줄여줄 수 있었다