코딩테스트 합격자 되자 4주차 과제

1번문제

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();// 괄호의 수

        for (int i = 0; i < n; i++) {
            Stack<Character> stack = new Stack<>(); // 캐릭터타입 
            String s = scan.next();

            for (int j = 0; j < s.length(); j++) {
                char currentChar = s.charAt(j);

                if (currentChar == '(' || currentChar == '{' || currentChar == '[') {
                    stack.push(currentChar); //괄호에  (,{,[이면 무조건 삽입한다
                } else if (currentChar == ')' || currentChar == '}' || currentChar == ']') {
                    if (!stack.isEmpty() && isMatchingPair(stack.peek(), currentChar)) {
                        stack.pop();//그렇지않으면 삭제
                    } else {
                        stack.push('f');
                        break;
                    }
                }
            }

            if (stack.isEmpty()) {
                System.out.println("YES");
            } else {
                System.out.println("NO");
            }
        }
    }

    private static boolean isMatchingPair(char opening, char closing) {
        return (opening == '(' && closing == ')') ||  //여기는 괄에서 사이 없으면 true리턴해주는 합수이다
                (opening == '{' && closing == '}') ||
                (opening == '[' && closing == ']');
    }
}

2번

import java.util.*;

public class Main {

    public static  int[] dailyTemperatures(int [] temperatures){
      int n = temperatures.length;
      int[] result = new int[n];
      Stack <Integer> stack = new Stack<>();

      for (int i =0;i<n;i++){
          while(!stack.isEmpty() && temperatures[i]> temperatures[stack.peek()]){
            int idx =stack.pop();
            result[idx] = i -idx;
          }
          stack.push(i);
      }


       return result;
    }

    public static void main(String[] args){

        Scanner scanner =  new Scanner(System.in);

        int length = scanner.nextInt(); // 배열의 길이

        int [] temperatures = new int[length];
         for (int i =0; i<length;i++){
             temperatures[i] = scanner.nextInt();
         }
        int [] output =dailyTemperatures(temperatures);


         for (int value :output){
             System.out.print(value+"");
         }

    }


}

3번

import java.util.*;



public class Main {



    public static void main(String[] args){

        System.out.println("큐의 크기를 입력하세요:");
        Scanner scanner = new Scanner(System.in);
        int Queuesize = scanner.nextInt();
        Queue<Integer> q = new ArrayDeque<>(Queuesize);

        // 먼저 들어온 원소부터 추출
      while (true){

          System.out.println("1. 큐에 추가");
          System.out.println("2. 큐 출력");
          System.out.print("원하는 작업을 선택하세요: ");
          int choice = scanner.nextInt();

          switch (choice){
              case 1:
                  int Element  =scanner.nextInt();
                  if (q.size() < Queuesize) {

                      q.add(Element);
                  }else {
                     q.poll(); //큐에서 가장오래된 원소 제거
                     q.add(Element);
                  }
                  break;
              case 2:
                  System.out.println("큐의 원소 출력: " + q);
                  break;

              default:
                  System.out.println("유효하지 않은 선택입니다. 올바른 옵션을 선택하세요.");
                  break;

          }
      }



    }


}

 

 

4번문제

import java.util.*;



public class Main {



    public static void main(String[] args){
        System.out.println("원소입력");
        Scanner scanner = new Scanner(System.in);
        Queue<Integer> q  = new LinkedList<>();  //자바에서 큐를 링크드 리스트통해서 구현해준다
       while(true){
            int element = scanner.nextInt();// 입력할원소
             //Queue
           q.add(element);  //입력할원소를 출력해준다
           List<Integer> list = new ArrayList<>(q); //입력한원소를 어레이 리스트에 넣어준다 정렬를하기위해서
           Collections.sort(list ,Collections.reverseOrder()); // 제네릭에서 컬렉션으로 정렬 함수가 JVM 내장되어있다 그걸로 내림차순을 구현해준다


           q.clear();  //비우기


           q.addAll(list); //리스트에 있는것을듯 큐에 넣은다



           System.out.println(q);
       }


      }






}

5번문제

import java.util.Scanner;
import java.util.Stack;

class TreeNode {
    int val;
    TreeNode left, right;

    public TreeNode(int val) {
        this.val = val;
    }
}

public class Main {
    public static TreeNode buildTree(Scanner scanner) {
        System.out.print("Enter the root value (enter -1 for null): ");
        int value = scanner.nextInt();

        if (value == -1) {
            return null;
        }

        TreeNode root = new TreeNode(value);
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);

        while (!stack.isEmpty()) {
            TreeNode current = stack.pop();

            System.out.print("Enter right child for " + current.val + " (enter -1 for null): ");
            int rightValue = scanner.nextInt();
            if (rightValue != -1) {
                current.right = new TreeNode(rightValue);
                stack.push(current.right);
            }

            System.out.print("Enter left child for " + current.val + " (enter -1 for null): ");
            int leftValue = scanner.nextInt();
            if (leftValue != -1) {
                current.left = new TreeNode(leftValue);
                stack.push(current.left);
            }
        }

        return root;
    }

    public static int findHeight(TreeNode root) {
        if (root == null) {
            return 0;
        }

        Stack<TreeNode> stack = new Stack<>();  //트리노드의 대한 스텍
        Stack<Integer> heights = new Stack<>();  //높이에대한 스텍
        stack.push(root);
        heights.push(1);
        int maxHeight = 0;

        while (!stack.isEmpty()) {
            TreeNode current = stack.pop();
            int currentHeight = heights.pop();
            maxHeight = Math.max(maxHeight, currentHeight);

            if (current.right != null) {
                stack.push(current.right);
                heights.push(currentHeight + 1);
            }

            if (current.left != null) {
                stack.push(current.left);
                heights.push(currentHeight + 1);
            }
        }

        return maxHeight;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        System.out.println("Enter the root value: ");
        TreeNode root = buildTree(scanner);

        int height = findHeight(root);
        System.out.println("Binary Tree Height: " + height);

        scanner.close();
    }
}

6번 문제 bfs사용

import java.util.*;


public class Main {

    public static int[][] calculateMinDistances(int[][] room) {
        int rows = room.length; // 행
        int cols = room[0].length; //열
        int[][] distances = new int[rows][cols];// 도착지

        int[][] directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

        Queue<int[]> queue = new LinkedList<>();  // 큐를 링크드리스트 구현한다


        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                distances[i][j] = Integer.MAX_VALUE; 
                if (room[i][j] == 1) {
                    distances[i][j] = 0;
                    queue.add(new int[]{i, j});
                }
            }
        }

        while (!queue.isEmpty()) {
            int[] current = queue.poll();

            for (int[] direction : directions) {
                int ni = current[0] + direction[0];
                int nj = current[1] + direction[1];

                if (ni >= 0 && ni < rows && nj >= 0 && nj < cols && distances[ni][nj] > distances[current[0]][current[1]] + 1) {
                    distances[ni][nj] = distances[current[0]][current[1]] + 1;
                    queue.add(new int[]{ni, nj});
                }
            }
        }

        return distances;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        System.out.println("Enter the number of rows: ");
        int rows = scanner.nextInt();

        System.out.println("Enter the number of columns: ");
        int cols = scanner.nextInt();

        int[][] room = new int[rows][cols];

        System.out.println("Enter the room elements (0 for empty, 1 for wall): ");
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                room[i][j] = scanner.nextInt();
            }
        }

        // Calculate minimum distances
        int[][] minDistances = calculateMinDistances(room);

        // Display the minimum distances
        System.out.println("Minimum distances from walls:");
        for (int[] row : minDistances) {
            for (int distance : row) {
                System.out.print(distance + " ");
            }
            System.out.println();
        }

        scanner.close();
    }
}