1292번, 14888번 - 스택, 큐, 재귀

실버에서 조금 고티어 문제들도 풀어보았다.

자료구조가 크게 달라지지는 않았지만, 좀더 정확한 이해가 필요했다.

• 1292번 쉽게푸는 문제
  

  import java.util.*;
  
  public class 쉽게푸는문제_1292번 {
      public static void main(String[] args) {
          Scanner sc = new Scanner(System.in);
          int start = sc.nextInt();
          int end = sc.nextInt();
          Queue<Integer> queue = new LinkedList<>();
          Stack<Integer> stack = new Stack<>();
          int num = 0;
          int count = 1;
          int sum = 0;
  
          while (count <= end) {
              num++;
              for (int i = 0; i < num; i++) {
                  queue.add(num);
                  stack.add(num);
                  sum += num;
                  count++;
              }
          }
          for (int i = 1; i < start; i++) {
              sum -= queue.poll();
          }
          for (int i = count-1; i > end; i--) {
              sum -= stack.pop();
          }
          System.out.println(sum);
      }
  }

  그렇게 어려운 문제는 아니었지만,
  배열에 저장하는 것 보다 스택과 큐를 이용하는 것이 더 빠르다는 점을 알 수 있었고, 이유는 아래와 같다.
  배열을 사용하면, 특정 위치에 값을 삽입하거나 삭제할 때 시간 복잡도가 O(n)이 될 수 있다. 반면, 큐와 스택은 일반적으로 삽입과 삭제가 O(1)의 시간 복잡도를 가지므로 더 효율적이다.
  
  
• 14888번 연산자 끼워 넣기
  

  import java.util.*;
  
  public class 연산자끼워넣기_14888번 {
      public static void main(String[] args) {
          Scanner sc = new Scanner(System.in);
          int N = sc.nextInt();
          int[] A = new int[N];
          for (int i = 0; i < N; i++) {
              A[i] = sc.nextInt();
          }
          int[] operatorNum = new int[4];
          for (int i = 0; i < 4; i++) {
              operatorNum[i] = sc.nextInt();
          }
          int[] maxMin = {-1000000000, 1000000000};
  
          recursion(A, 0, N, operatorNum, A[0], maxMin);
  
          System.out.println(maxMin[0]);
          System.out.println(maxMin[1]);
      }
  
      private static void recursion(int[] A, int count, int N, int[] operatorNum,
                                    int sum, int[] maxMin) {
          if (count == N-1) {
              maxMin[0] = Math.max(maxMin[0], sum);
              maxMin[1] = Math.min(maxMin[1], sum);
          }
          else {
              for (int i = 0; i < 4; i++) {
                  if (operatorNum[i] > 0) {
                      int[] copyOfOperatorNum = Arrays.copyOf(operatorNum, operatorNum.length);
                      copyOfOperatorNum[i] -= 1;
                      recursion(A, count + 1, N, copyOfOperatorNum, calculation(i, A[count + 1], sum), maxMin);
                  }
              }
          }
      }
  
      private static int calculation(int operatorNum, int num, int sum) {
          if (operatorNum == 0) {
              return sum + num;
          } else if (operatorNum == 1) {
              return sum - num;
          } else if (operatorNum == 2) {
              return sum * num;
          } else {
              return sum / num;
          }
      }
  }

   재귀를 이용한 점 말고는 크게 특이하지 않았지만, 여러 요소를 포함시키면서 시간이 조금 걸렸다.
  실제로 동작시켜보니 재귀가 빠른 알고리즘은 아니란 것을 알 수 있었다.
  그래도 위와 같은 상황에서는 그 중 빠른 방법인 것 같다.

실버도 위 티어로 가니 자료구조와 알고리즘에 대한 어느정도의 이해가 필요한 듯 하다.

꾸준히 알고리즘 문제를 풀어 실력을 정진 시켜야겠다.