💬 입출력 예시

📌 풀이(소스코드)

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

public class Main {

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());
        int[] status = new int[N + 1];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 1; i <= N; i++) {
            status[i] = Integer.parseInt(st.nextToken());
        }

        int M = Integer.parseInt(br.readLine());
        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int gender = Integer.parseInt(st.nextToken());
            int num = Integer.parseInt(st.nextToken());

            status[num] = Math.abs(status[num] - 1);    // 받은 번호의 위치는 항상 바뀐다.

            // 남학생일 경우
            if (gender == 1) {
                for (int j = 1; j <= N; j++) {
                    if (j % num == 0 && j != num) {
                        status[j] = Math.abs(status[j] - 1);
                    }
                }
            } else if (gender == 2) {
                // 여학생일 경우
                for (int j = 1; j <= N / 2; j++) {
                    int left = num - j;
                    int right = num + j;
                    if (left <= 0 || right >= N + 1) {
                        break;
                    }
                    if (status[left] != status[right]) {
                        break;
                    }
                    status[left] = Math.abs(status[left] - 1);
                    status[right] = Math.abs(status[right] - 1);
                }
            }
        }

        StringBuilder sb = new StringBuilder();
        for (int i = 1; i < status.length; i++) {
            sb.append(status[i]).append(" ");
            if (i % 20 == 0) {
                sb.append("\n");
            }
        }
        System.out.println(sb);
    }
}

📄 해설

접근

• 역시 구현 문제로 문제에서 주어진 조건을 충실히 이행하면 되는 문제
• 구현문제로 넘어오니, 실버 문제의 구현 자체에는 큰 어려움들이 없다. (아직 하위 단계라 그런 것 같긴하다 😂)
• 남학생인 경우의 처리와 여학생인 경우의 처리로 나누어서 구현하면 되며, 각 학생에게 부여된 번호에 해당하는 위치는 무조건 상태가 변하므로, 해당 위치의 상태는 미리 바꾼 다음 나머지 값들에 대한 처리를 했다.
• 남학생은 해당 인덱스가 배수인지 아닌지만 확인하면 되므로 간단하지만, 여학생의 경우가 좀 복잡할 수 있다. 여학생의 경우는 입력받은 위치를 중심으로 양 옆의 위치들을 확인해야한다.
• 자세한 구현은 코드와 아래 과정 설명을 확인하길 바란다.

과정

• 스위치의 개수 N 을 입력 받고 스위치의 상태를 저장할 배열 status 에 스위치의 시작 상태를 입력받는다.
• 학생의 수 M 을 입력 받고 각 학생의 성별과 번호를 입력받는다.
• 어떤 경우에도 입력 받은 번호 num 위치의 스위치 상태는 변하므로, 해당 위치는 미리 변경을 해둔다. 학생의 성별에 따라 다음과 같이 처리를 한다.
  • 남학생의 경우
    1. status 배열을 순회하면서 해당 인덱스의 값이 num 과 일치하는지와 num 의 배수인지를 확인한다.
    2. 1 에 해당하면 해당 위치의 상태 값을 바꾼다.
  • 여학생의 경우
    1. 대칭 검사를 위해 left 와 right 라는 변수를 사용한다. 해당 값들은 num 에서 j 만큼을 더하고 뺀 값이며, j 는 1 부터 N/2 까지의 값이다. (num 위치를 중심으로 탐색해 나가기 위함)
    2. left 나 right 값이 배열의 범위를 벗어나거나 두 위치의 상태가 대칭을 이루지 않으면 반복을 종료한다.
    3. 2 의 조건을 모두 통과했다면 해당 위치는 대칭을 이루는 값들이므로 상태 값을 변경해준다.
• 위 과정을 모두 끝냈다면 현재 status 배열의 상태를 출력한다. 이때, 출력 조건을 따라 20번째 원소를 출력할 때마다 줄바꿈을 해준다. 출력을 한번만 수행하기 위해 StringBuilder 를 사용한다.

💬 입출력 예시

📌 풀이(소스코드)

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

public class Main {

    static int N;
    static boolean isBoom = false;
    static final int[] dr = {-1, -1, -1, 0, 0, 1, 1, 1};
    static final int[] dc = {-1, 0, 1, -1, 1, -1, 0, 1};
    static char[][] mineBoard, playBoard, resultBoard;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        N = Integer.parseInt(br.readLine());
        mineBoard = new char[N][N];
        playBoard = new char[N][N];
        resultBoard = new char[N][N];

        inputBoard(br, mineBoard);
        inputBoard(br, playBoard);
        initResultBoard();

        process();
        boom();

        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < N; i++) {
            sb.append(resultBoard[i]).append("\n");
        }
        System.out.println(sb);
    }

    private static void inputBoard(BufferedReader br, char[][] playBoard) throws IOException {
        for (int i = 0; i < N; i++) {
            String input = br.readLine();
            for (int j = 0; j < N; j++) {
                playBoard[i][j] = input.charAt(j);
            }
        }
    }

    private static void initResultBoard() {
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                resultBoard[i][j] = '0';
            }
        }
    }

    private static void process() {
        for (int r = 0; r < N; r++) {
            for (int c = 0; c < N; c++) {
                if (playBoard[r][c] == 'x') {
                    if (mineBoard[r][c] == '*') {
                        isBoom = true;
                        continue;
                    }
                    countMines(r, c);
                }

                if (playBoard[r][c] == '.') {
                    resultBoard[r][c] = playBoard[r][c];
                }
            }
        }
    }

    private static void countMines(int r, int c) {
        for (int d = 0; d < 8; d++) {
            int nr = r + dr[d];
            int nc = c + dc[d];

            if (nr < 0 || nc < 0 || nr >= N || nc >= N) {
                continue;
            }

            if (mineBoard[nr][nc] == '*') {
                resultBoard[r][c]++;
            }
        }
    }

    private static void boom() {
        if (isBoom) {
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) {
                    if (mineBoard[i][j] == '*') {
                        resultBoard[i][j] = '*';
                    }
                }
            }
        }
    }
}

📄 해설

접근

• 출력문을 만드는 조건이 출력문 설명 부분에 있어서.. 문제를 읽자마자 이해하기 좀 난해했다 😑
• 그래도 설명 부분을 찾았다면, 접근 자체는 쉽게 가능하다. 주어진 조건에 따라 구현하면 되는 간단한 문제이다.
• 한가지 주의할 점은 작성자의 실수이긴한데, 지뢰를 밟으면 모든 지뢰를 표시해야한다. 라는 부분이다. 지뢰찾기 하다가 지뢰를 클릭했을 때의 상태를 만들라는 것. 이를 위해 isBoom 이라는 플래그 변수를 사용하였다.
  • 혹시라도 15% 부근에서 실패하는 사람이 있다면, 이 과정을 거쳤는지 확인해보길 바란다. 😅

과정

• 총 세 개의 2차원 char 배열을 사용했고, 각각 지뢰의 위치 정보, 플레이 결과 정보, 결과 정보 를 담는 배열들이다.
• 플레이 결과 정보를 담는 배열인 playBoard 를 순회하면서 해당 위치가 열려있는 위치인지를 확인한다. if (playBoard[r][c] == 'x)
  • 열려있는 위치라면 지뢰인지를 확인하고, 지뢰라면 isBoom = true 로 바꾸고 반복문으로 복귀한다.
  • 지뢰가 아닌 경우, 8방 탐색을 통해 근처에 지뢰가 몇개인지를 세고, 결과를 resultBoard 에 반영한다.
• 열려있지 않은 경우, resultBoard 의 해당 위치에 . 을 저장한다.
• playBoard 에 대한 순회가 끝나면, isBoom 이 true 인지 false 인지 확인한다. 이때, isBoom 이 true 인 경우, 지뢰를 누른 것이므로 모든 지뢰의 위치를 resultBoard 에 반영한다.

💬 입출력 예시

📌 풀이(소스코드)

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

public class Main {

    static final int SIZE = 5;
    static int result = 0;
    static int lineCnt = 0;
    static int[][] board = new int[SIZE][SIZE];

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        for (int i = 0; i < SIZE; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int j = 0; j < SIZE; j++) {
                board[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        for (int i = 0; i < SIZE; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int j = 0; j < SIZE; j++) {
                result++;
                // 사회자가 부르는 숫자
                int num = Integer.parseInt(st.nextToken());

                // 숫자 사용처리
                for (int r = 0; r < SIZE; r++) {
                    for (int c = 0; c < SIZE; c++) {
                        if (board[r][c] == num) {
                            board[r][c] = -1;
                        }
                    }
                }
                // 빙고 확인
                checkRow();
                checkCol();
                checkLeftDiagonal();
                checkRightDiagonal();

                if (lineCnt >= 3) {
                    System.out.println(result);
                    return;
                }
                lineCnt = 0;    //  중복을 막기 위해 초기화
            }
        }
    }

    private static void checkRow() {
        for (int i = 0; i < SIZE; i++) {
            int count = 0;
            for (int j = 0; j < SIZE; j++) {
                if (board[i][j] == -1) {
                    count++;
                }
            }
            if (count == SIZE) {
                lineCnt++;
            }
        }
    }

    private static void checkCol() {
        for (int i = 0; i < SIZE; i++) {
            int count = 0;
            for (int j = 0; j < SIZE; j++) {
                if (board[j][i] == -1) {
                    count++;
                }
            }
            if (count == SIZE) {
                lineCnt++;
            }
        }
    }

    private static void checkLeftDiagonal() {
        int count = 0;
        for (int i = 0; i < SIZE; i++) {
            if (board[i][i] == -1) {
                count++;
            }
            if (count == SIZE) {
                lineCnt++;
            }
        }
    }

    private static void checkRightDiagonal() {
        int count = 0;
        for (int i = 0; i < SIZE; i++) {
            if (board[i][SIZE - i - 1] == -1) {
                count++;
            }
            if (count == SIZE) {
                lineCnt++;
            }
        }
    }
}

📄 해설

접근

• 문제에서 주어진 조건에 따라, 가로, 세로, 대각선 5 칸을 확인해서 3줄 빙고가 되는지를 확인하면 되는 문제
• 문제 접근이나 풀이 과정 자체는 어렵지 않으나, 구현하는 과정이 조금 까다로울 수 있다. 작성자 얘기 맞다 😅

과정

• 빙고판을 입력 받고, 저장한 뒤, 사회자가 불러주는 숫자들을 하나씩 지운다. 지워진 숫자는 -1 로 표시한다.
• 숫자 한개를 지울 때 마다 빙고가 완성 됐는지를 확인한다. 이때, 가로, 세로, 대각선 모두를 확인해준다.
• 확인하면서 총 빙고의 숫자인 lineCnt 변수의 값을 증가시키고, 이 값이 3을 넘으면 빙고를 외칠 타이밍이므로, 몇번째 숫자인지를 기억하고 있는 result 변수를 출력하고 프로그램을 종료한다.

💬 입출력 예시

📌 풀이(소스코드)

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

public class Main {

    static final int SIZE = 14;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int money = Integer.parseInt(br.readLine());
        int[] costs = new int[SIZE];

        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < SIZE; i++) {
            costs[i] = Integer.parseInt(st.nextToken());
        }

        // 두 방법의 최종 결과 값만 알면됨
        int bnpRet = bnp(costs, money);
        int timingRet = timing(costs, money);

        if (bnpRet > timingRet) {
            System.out.println("BNP");
        } else if (bnpRet < timingRet) {
            System.out.println("TIMING");
        } else {
            System.out.println("SAMESAME");
        }
    }

    private static int bnp(int[] costs, int money) {
        int stocks = 0;
        for (int cost : costs) {
            if (cost <= money) {
                stocks += money / cost;
                money -= cost * (money / cost);
            }
        }
        return costs[costs.length - 1] * stocks + money;
    }

    private static int timing(int[] costs, int money) {
        int stocks = 0;
        int upCnt = 0;
        int downCnt = 0;

        for (int i = 0; i < costs.length; i++) {
            // 하락
            if (i != 0 && costs[i] < costs[i - 1]) {
                downCnt++;
            } else {
                downCnt = 0;
            }
            if (i != 0 && costs[i] > costs[i - 1]) {
                upCnt++;
            } else {
                upCnt = 0;
            }

            if (upCnt >= 3) {
                money += costs[i] * stocks;
                stocks = 0;
            }

            if (costs[i] <= money && downCnt >= 3) {
                stocks += money / costs[i];
                money -= costs[i] * (money / costs[i]);
            }
        }
        return stocks * costs[costs.length - 1] + money;
    }
}

📄 해설

접근

• 구현 문제는 사실 크게 접근이랄게 없다. 최근 풀이한 문제들이 전부 실버 난이도 이하여서, 너무 오랫동안 글을 작성하지 않는 것에 불안감을 느끼고 작성한다.
• 두 경우를 메소드로 나눠서 구현을 했다.
• BNP 는 단순히 매수 가능할 때 전량 매수를 하고, 마지막 날의 값과 계산을 한다.
• TIMING 은 BNP 보다는 복잡하다. 하락이나 상승이 3일 연속 이루어지고 있는지를 계속해서 확인하고, 3일 째 하락이나 상승이 이루어졌을 때, 매수나 매도 로직을 수행하면 된다.

과정

• 시작 자금을 입력 받고, 14일 동안의 주식 가격을 입력 받아 costs 배열에 저장한다.
• BNP 의 결과값을 얻는 메소드와 TIMING 의 결과값을 얻는 메소드를 각각 실행하고, 둘의 결과 값을 비교하여 둘 중 큰 값을 가진 방법을 출력한다. 같으면 SAMESAME 을 출력한다.
• BNP 메소드의 흐름은 다음과 같다.
  • 현재 갖고 있는 현금이 주식의 가격과 크거나 같다면 바로 전량 매수를 한다.
• TIMING 메소드의 흐름은 다음과 같다.
  • 오늘 주식의 가격이 전날보다 상승했는지, 하락했는지를 확인하기 위해 upCnt 변수와 downCnt 변수를 유지한다.
  • upCnt 변수가 3 이상이 될 경우, 전량 매도를 수행한다.
  • downCnt 변수가 3 이상이고 매수할 수 있다면 전량 매수를 수행한다.
• 두 메소드 모두 결과 값을 얻는 방법은 다음과 같이 동일하다.
  • 반복 종료 후, 현재 주식의 개수 * 마지막날 주식의 가격 + 보유 현금 을 반환한다.
• 출력부에 대한 설명은 생략하겠다.

💬 입출력 예시

📌 풀이(소스코드)

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.time.Duration;
import java.time.LocalDateTime;
import java.time.format.DateTimeFormatter;
import java.util.HashMap;
import java.util.TreeMap;

public class Main {

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        String[] input = br.readLine().split(" ");
        int N = Integer.parseInt(input[0]);
        int F = Integer.parseInt(input[2]);

        // 시간 파싱
        String[] date = input[1].split("/");
        String[] time = date[1].split(":");
        int limitDay = Integer.parseInt(date[0]);
        int limitHour = Integer.parseInt(time[0]);
        int limitMinute = Integer.parseInt(time[1]);
        long limitTime = limitDay * 24L * 60L + limitHour * 60L + limitMinute;  // 분으로 환산된 대여기간

        // Key 가 회원, 부품이고 value 가 일자 및 시간인 HashMap
        // Key 가 회원이고 value 가 벌금인 TreeMap
        HashMap<String, String> rentalMap = new HashMap<>();
        TreeMap<String, Long> fineMap = new TreeMap<>();
        for (int i = 0; i < N; i++) {
            input = br.readLine().split(" ");

            String value = input[0] + " " + input[1];
            String key = input[2] + input[3];

            if (rentalMap.containsKey(key)) {
                // 이미 있는 경우의 처리
                DateTimeFormatter formatter = DateTimeFormatter.ofPattern("yyyy-MM-dd HH:mm");
                LocalDateTime startTime = LocalDateTime.parse(rentalMap.get(key), formatter);
                LocalDateTime endTime = LocalDateTime.parse(value, formatter);

                Duration duration = Duration.between(startTime, endTime);

                long delayTime = duration.getSeconds() / 60 - limitTime;
                if (delayTime > 0) {
                    long totalFine = delayTime * F;
                    if (totalFine > 0) {
                        fineMap.put(input[3], fineMap.getOrDefault(input[3], 0L) + totalFine);
                    }
                }

                rentalMap.remove(key);    // 같은 물건은 중복해서 대여할 수 없으므로 맵에서 제거
            } else {
                rentalMap.put(key, value);  // 중복이 없으므로 맵에 바로 등록
            }
        }

        // 벌금 낼 사람이 없으므로 -1 출력
        if (fineMap.isEmpty()) {
            System.out.println(-1);
            return;
        }

        // 벌금을 내야하는 사람과 요금 출력
        StringBuilder sb = new StringBuilder();
        for (String key : fineMap.keySet()) {
            sb.append(key).append(" ").append(fineMap.get(key)).append("\n");
        }
        System.out.println(sb);
    }

}

📄 해설

접근

• 시간 관련 라이브러리를 잘 활용해야하는 문제. 작성자는 해당 라이브러리를 많이 사용해보질 않아, 다른 풀이를 확인하고 풀었다. 나중에 다시 풀어봐야할 문제다.
• 대여장을 표현하기 위해 Key 가 회원, 부품이고 Value 가 일자 및 시간인 HashMap 을 사용하고, 이름순으로 정렬된 벌금 장부를 표현하기 위해 Key 가 회원이고 Value 가 벌금인 TreeMap 을 사용한다.
• 대여장에 이미 대여 내역이 있는 경우 벌금을 계산하고 대여장에서 해당 내역을 제거하고, 없는 경우 그냥 대여장에 추가한다.

과정

• 입력 받은 문자열을 파싱해서 대여 기간을 구한다.
• 이후 N개의 입력을 받으면서, 입력 받은 문자열을 파싱해서 대여장을 표현하는 rentalMap 에 파싱해서 만든 Key 가 이미 존재하는 경우와 그렇지 않은 경우로 처리가 나뉜다.
• 이미 대여장에 현재 입력받은 회원과 부품이 Key로 존재하는 경우, rentalMap 에 저장된 일자 및 시간과 현재 입력 받은 일자 및 시간과의 차이를 계산하고, 연체한 경우 벌금을 계산해서 fineMap 에 벌금을 추가한다. 그 다음 같은 물건은 중복 대여가 불가능 하므로, rentalMap 에서 해당 회원과 부품을 제거한다.
• 대여장에 현재 입력 받은 회원과 부품이 존재하지 않는 경우, 단순히 rentalMap 에 추가한다.
• 벌금을 저장하고 있는 fineMap 이 비어있지 않은 경우 -1을 출력하고, 그렇지 않으면 fineMap 에 존재하는 모든 회원의 벌금을 함께 출력한다. 이때, TreeMap 이므로 이미 이름 순으로 정렬이 되어있다.

💬 입출력 예시

📌 풀이(소스코드)

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Collections;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

/**
 * 1시간
 * 다시 풀어야함. 기존 풀이는 두개의 리스트를 사용했는데, 두 개의 우선순위 큐를 사용하는 것이 훨씬 더 효율적임
 * 최대힙, 최소힙 두개를 사용해야함
 */
public class Main {

    public static void main(String[] args) throws Exception {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        int T = Integer.parseInt(br.readLine());
        while (T-- > 0) {
            // 최대힙과 최소힙 두개 사용. 최대힙은 내림차순 정렬, 최소힙은 오름차순 정렬 => 중앙값 접근
            PriorityQueue<Integer> minHeap = new PriorityQueue<>();
            PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());

            // 출력하는 중앙값의 개수 == (수열의 크기 / 2) + 1
            int M = Integer.parseInt(br.readLine());
            sb.append((M + 1) / 2).append("\n");

            int cnt = 0;
            StringTokenizer st = null;
            for (int i = 0; i < M; i++) {
                // 입력을 위한 조건문
                if (i % 10 == 0) {
                    st = new StringTokenizer(br.readLine());
                }

                // 두 힙의 크기가 같으면 홀수번째 숫자 -> 최대힙에 저장
                // 두 힙의 크기가 다르면 짝수번째 숫자 -> 최소힙에 저장
                int num = Integer.parseInt(st.nextToken());
                if (maxHeap.size() == minHeap.size()) {
                    maxHeap.offer(num);
                } else {
                    minHeap.offer(num);
                }

                // 입력마다 최소 힙의 최솟값과 최대 힙의 최댓값을 비교
                // 최대 힙은 중앙 값 이하의 숫자만 가져야 한다. 즉, 최대 힙의 모든 값은 최소 힙의 모든 값보다 작아야 함
                // 그러므로 최대 힙의 최댓값과 최소 힙의 최솟값을 스왑해준다.
                if (!minHeap.isEmpty() && !maxHeap.isEmpty()) {
                    if (maxHeap.peek() > minHeap.peek()) {
                        int temp = minHeap.poll();
                        minHeap.offer(maxHeap.poll());
                        maxHeap.offer(temp);
                    }
                }

                // 홀수번째 수를 읽을 때마다 중앙값 출력
                // 위에서 최대 힙을 기준으로 하여 값을 추가했으므로 최대 힙의 최솟값이 중앙값
                if (i % 2 == 0) {
                    sb.append(maxHeap.peek()).append(" ");

                    // 한 줄에 10개씩 출력하기 위한 조건문
                    cnt++;
                    if (cnt % 10 == 0) {
                        sb.append("\n");
                    }
                }
            }
        }

        System.out.println(sb);
    }
}

📄 해설

접근

• 이전에 풀었던 풀이는 두 개의 ArrayList를 사용해서 중앙값을 저장하는 리스트와 수열을 저장하는 리스트 두개로 나누어서 풀었던 풀이이다.
• 그러나 이번에는 두 개의 우선순위 큐를 사용하는 풀이를 찾아 해당 풀이로 정리를 해보고자 한다.
• 최대 힙과 최소 힙 두개를 사용하는 것으로 접근을 해야하고, 어떤 것을 기준으로 하여 값을 추가할 것인지에 따라 출력부의 처리가 달라진다.

과정

• 이번 풀이 과정은 주석을 확인하는 것이 더 효율적일 것이라고 생각된다. 하지만 작성해보도록 하겠다. 입력과 출력을 위한 코드에 대한 과정은 알고리즘적인 부분은 아니므로 제외하겠다.
• 최소 힙과 최대 힙의 크기가 동일한지에 대해 확인한다. 이때 같으면 홀수번째 숫자가 들어온 것이므로 최대 힙에 넣고, 같지 않으면 짝수번째 숫자가 들어온 것이므로 최소 힙에 넣는다.
• 둘 중 하나의 힙에 값을 넣었다면, 두 힙 모두 비어있지 않을 경우 최소 힙의 최솟값인 minHeap.peek() 과 최대 힙의 최댓값인 maxHeap.peek() 을 비교한다. 최소 힙의 최솟값이 최대 힙의 최댓값보다 작은 경우, 최소 힙의 최댓값과 최대 힙의 최솟값을 스왑한다.
  • 이렇게 하는 이유는, 최소 힙의 모든 원소는 최대 힙의 모든 원소보다 커야하기 때문이고, 이를 유지하기 위함이다.
• 위 규칙을 그대로 따르고, 홀수번째 숫자의 입력 시 마다 출력문을 양식에 맞춰서 조정해주면 된다. 중앙값은 최대 힙을 기준으로 값을 입력했기 때문에, 최대 힙의 맨 처음 원소. 즉, 최대 힙의 최댓값이 된다.

💬 입출력 예시

📌 풀이(소스코드)

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.HashSet;
import java.util.StringTokenizer;

public class Main {

    public static void main(String[] args) throws Exception {
        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());

        HashSet<String> set = new HashSet<>();

        for (int i = 0; i < N; i++) {
            set.add(br.readLine());
        }

        int cnt = 0;

        for (int i = 0; i < M; i++) {
            String s = br.readLine();

            if (set.contains(s)) {
                cnt++;
            }
        }

        System.out.println(cnt);
    }
}

📄 해설

접근

• HashSet 을 이용하여 단순 구현을 하는 문제
• 단순히 HashSet 에 문자열을 넣고 입력으로 주어지는 M 개의 문자열이 몇개나 포함되는지 개수를 세면 된다.

과정

• HashSet 을 생성하고, N개의 입력받은 문자열을 추가한다.
• M 개의 문자열을 입력받고, 해당 문자열이 HashSet 에 있으면 cnt 값을 증가시킨다.
• 반복 종료 후 cnt 값을 출력하면 끝

💬 입출력 예시

📌 풀이(소스코드)

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.StringTokenizer;

public class Main {

    public static void main(String[] args) throws Exception {
        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());

        HashMap<Integer, String> numberMap = new HashMap<>();
        HashMap<String, Integer> nameMap = new HashMap<>();

        for (int i = 1; i <= N; i++) {
            String s = br.readLine();
            numberMap.put(i, s);
            nameMap.put(s, i);
        }

        StringBuilder sb = new StringBuilder();

        for (int i = 0; i < M; i++) {
            String key = br.readLine();

            if (Character.isDigit(key.charAt(0))) {
                sb.append(numberMap.get(Integer.parseInt(key))).append("\n");
            } else {
                sb.append(nameMap.get(key)).append("\n");
            }
        }

        System.out.println(sb);
    }
}

📄 해설

접근

• 우선 문제가 너무 길고 불필요해서 가장 필요한 부분만 캡쳐해서 가져왔다..
• 번호가 들어오면 해당 포켓몬의 이름을 출력하고, 이름이 들어오면 해당 포켓몬의 번호를 출력해야하기 때문에 두 개의 HashMap 을 사용하는 것으로 접근했다.

과정

• 로직은 간단하다. 단순 구현 문제이므로, 입력을 받은 후, 출력을 요구하는 M개의 입력에 대하여 해당 입력이 숫자인 경우와 문자열인 경우의 처리를 분기한다.
• 두 개의 HashMap 을 사용한다. 포켓몬의 번호와 이름을 입력 받으면서 각각 <번호, 이름> 쌍과 <이름, 번호> 쌍으로 저장한다.
• 문자열인 경우 <번호, 이름> 쌍을 저장한 맵에 접근하고, 숫자인 경우 <이름, 번호> 쌍을 저장한 맵에 접근한다.

💬 입출력 예시

📌 풀이(소스코드)

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

public class Main {

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        String s = br.readLine();
        Stack<Character> stack = new Stack<>();

        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);

            if (c == '(') {
                stack.push(c);
            } else if (c == ')') {
                while (!stack.isEmpty()) {
                    if (stack.peek() == '(') {
                        stack.pop();
                        break;
                    }
                    sb.append(stack.pop());
                }
            } else if (c == '*' || c == '/' || c == '+' || c == '-') {
                while (!stack.isEmpty()) {
                    if (getPriority(stack.peek()) > getPriority(c)) {
                        break;
                    }
                    sb.append(stack.pop());
                }
                stack.push(c);
            } else {
                sb.append(c);
            }
        }

        while (!stack.isEmpty()) {
            sb.append(stack.pop());
        }

        System.out.println(sb);
    }

    private static int getPriority(char op) {
        if (op == '(' || op == ')') {
            return 3;
        } else if (op == '*' || op == '/') {
            return 1;
        } else if (op == '+' || op == '-') {
            return 2;
        }
        return -1;
    }
}

📄 해설

접근

• Character 타입의 스택을 사용하여 해결하는 문제이다.
• 피연산자는 바로 출력하고, 여는 괄호는 스택에 넣고 닫는 괄호를 만나면 여는 괄호를 찾을 때까지 모든 원소를 출력한다.
• 연산자의 경우도 스택에 추가한다. 이때, 스택의 탑이 현재 연산자보다 높은 우선순위를 가진다면 스택이 빌때까지 전부 다 출력한다.
• 문자열 순회 끝나고 난 다음에 마지막에 추가된 연산자가 있을 수 있으니 한번 더 스택이 빌때까지 전부 다 출력한다.

과정

• Character 타입의 스택을 하나 선언하고, 입력 받은 문자열을 순회한다.
• 여는 괄호를 만난 경우, 스택에 추가한다.
• 닫는 괄호를 만난 경우, 스택이 빌때까지 스택의 모든 원소를 출력한다. 이때, 여는 괄호를 만나면 반복을 종료한다ㅏ.
• 연산자의 경우, 스택의 탑이 현재 연산자보다 높은 우선순위를 가진다면 스택이 빌 때까지 출력한다. 낮은 우선순위라면 반복을 종료한다. 현재 연산자를 스택에 넣는다.
• 피연산자의 경우는 그냥 바로 출력한다.
• 문자열 순회가 끝난 후에 남아있는 연산자가 존재할 수 있다. 그러므로 스택이 빌 때까지 스택 내의 원소들을 다 출력한다.

💬 입출력 예시

📌 풀이(소스코드)

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

public class Main {

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());
        List<Point> points = new ArrayList<>();
        Stack<Point> stack = new Stack<>();

        while (N-- > 0) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int x = Integer.parseInt(st.nextToken());
            int r = Integer.parseInt(st.nextToken());

            // 왼쪽 끝점, 오른쪽 끝점을 구분한다.
            // x 좌표, 중심 좌표, 왼쪽 여부에 대한 정보를 담는 객체 리스트를 생성한다.
            points.add(new Point(x - r, x, true));
            points.add(new Point(x + r, x, false));
        }

        // 점의 x 좌표를 기준으로 정렬한다.
        points.sort(Comparator.comparingInt(o -> o.x));

        for (Point point : points) {
            // 원의 왼쪽 점이면 스택에 넣는다.
            if (point.isLeft) {
                stack.push(point);
                continue;
            }

            // 오른쪽 점인 경우 스택의 탑과 중심이 같다면 같은 원에 대한 좌표이므로 스택에서 뺀다.
            if (stack.peek().c == point.c) {
                stack.pop();
            } else {
                // 그렇지 않으면 둘이 다른원이다 => 겹치는 원이 존재한다.
                System.out.println("NO");
                return;
            }
        }

        // 리스트 순회가 끝났다면 겹치는 부분은 없었던 것이다.
        System.out.println("YES");
    }

    static class Point {

        int x;
        int c;
        boolean isLeft;

        public Point(int x, int c, boolean isLeft) {
            this.x = x;
            this.c = c;
            this.isLeft = isLeft;
        }
    }
}

📄 해설

접근

• 접근을 제대로 하지 못했다. 문제에서 힌트로 제공된 수식을 사용하는 풀이를 적용했을 때, 98% 에서 틀렸는데, 다른 사람의 풀이를 찾아봤더니 전혀 다른 풀이여서 아직 그 이유를 밝히지 못했다..
• 우선 위 풀이에서의 접근은, 각 원마다 왼쪽 끝점과 오른쪽 끝점을 구분해서 x 좌표, 중심 좌표, 왼쪽 여부에 대한 정보를 담는 Point 클래스 객체를 새로 생성하고, 리스트를 만든다.
• 해당 리스트를 x 좌표를 기준으로 정렬하고, 리스트를 순회하면서 왼쪽 끝점인지 오른쪽 끝점인지에 따라 처리를 하고, 겹치는 원이 있는지 없는지를 확인한다.

과정

• Point 객체를 담을 리스트와 스택을 선언하고, N 개의 원의 정보를 입력 받는다.
• 입력 받은 정보에 따라 왼쪽 끝점과 오른쪽 끝점에 대한 객체들을 새롭게 생성하여 리스트에 추가한다.
• 입력이 끝나면 점의 x 좌표를 기준으로 해당 리스트를 정렬하고, 리스트를 순회화면서 아래 동작을 반복한다.
  • 왼쪽 끝점일 경우, 스택에 추가한다.
  • 오른쪽 끝점일 경우 스택의 탑과 중심 좌표가 같다면, 각 점은 같은 원을 구성하므로, 스택에서 뺀다.
  • 스택의 탑과 중심 좌표가 같지 않다면, 둘은 다른 원이므로, 겹치는 원이 존재한다는 뜻이므로 NO 를 출력한다.
• 리스트 순회가 정상적으로 종료되었다면, 겹치는 원은 없었던 것이므로 YES 를 출력한다.

💬 입출력 예시

📌 풀이(소스코드)

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

public class Main {

    static BufferedReader br;
    static StringTokenizer st;
    static StringBuilder sb;
    static Stack<Tower> stack = new Stack<>();
    static int N;

    public static void main(String[] args) throws Exception {
        br = new BufferedReader(new InputStreamReader(System.in));
        sb = new StringBuilder();

        N = Integer.parseInt(br.readLine());
        st = new StringTokenizer(br.readLine());

        for (int i = 0; i < N; i++) {
            Tower now = new Tower(i + 1, Integer.parseInt(st.nextToken()));

            while (!stack.isEmpty()) {
                Tower top = stack.peek();
                if (top.height >= now.height) {
                    sb.append(top.idx).append(" ");
                    break;
                }
                stack.pop();
            }

            if (stack.isEmpty()) {
                sb.append(0).append(" ");
            }

            stack.push(now);
        }
        System.out.println(sb);
    }

    static class Tower {
        int idx;
        int height;

        public Tower(int idx, int height) {
            this.idx = idx;
            this.height = height;
        }
    }
}

📄 해설

접근

• 스택을 사용하고, 탑의 높이와 번호 정보를 저장할 Tower 클래스를 사용하는 문제
• 한 개의 탑이 한 개의 신호를 수신할 수 있다는 부분에서 스택으로 접근했다.

과정

• Tower 타입의 스택을 선언하고, 입력 받은 숫자들에 대해 아래 과정을 반복한다.
• 입력 받은 높이와 인덱스 번호를 담는 Tower 객체 하나를 만든다.
• 스택이 빌때까지 반복문을 실행하고, 아래 과정을 수행한다.
  • 스택의 탑(Top)의 높이가 현재 새로운 탑(Tower)의 높이보다 크거나 같은 경우, 스택 탑의 번호를 출력한다.
  • 스택에 Pop 연산을 수행한다.
• 스택이 빈 경우, 0 을 출력한다.
• 위 과정이 끝나면 현재 탑(Tower) 를 스택에 넣는다.

💬 입출력 예시

📌 풀이(소스코드)

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Stack;
import java.util.TreeSet;

public class Main {

    static ArrayList<Pos> posList = new ArrayList<>();
    static TreeSet<String> set = new TreeSet<>();

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        String input = br.readLine();
        Stack<Integer> stack = new Stack<>();


        for (int i = 0; i < input.length(); i++) {
            char c = input.charAt(i);

            if (c == '(') {
                stack.push(i);
            } else if (c == ')') {
                posList.add(new Pos(stack.pop(), i));
            }
        }


        dfs(0, posList.size(), input);
        set.remove(input);

        StringBuilder sb =  new StringBuilder();
        for (String s : set) {
            sb.append(s).append("\n");
        }

        System.out.println(sb);
    }

    private static void dfs(int depth, int n, String s) {
        // 공백 제거 후 Set 에 추가
        if (depth == n) {
            set.add(s.replaceAll(" ", ""));
            return;
        }

        Pos pos = posList.get(depth);
        StringBuilder sb = new StringBuilder(s);
        sb.setCharAt(pos.start, ' ');
        sb.setCharAt(pos.end, ' ');

        // 제거하는 경우
        dfs(depth + 1, n, sb.toString());
        // 제거하지 않는 경우
        dfs(depth + 1, n, s);
    }

    static class Pos {
        int start;
        int end;

        public Pos(int start, int end) {
            this.start = start;
            this.end = end;
        }
    }
}

📄 해설

접근

• 스택, DFS, TreeSet 을 사용해야 해결할 수 있는 문제이다.
• 이 문제 또한 접근이 상당히 어려웠고, TreeSet 을 사용한 적이 없어서 결국 다른 사람의 풀이를 보고 풀었다.
• 또한 괄호의 시작과 끝의 위치를 나타낼 클래스 Pos 를 구현해야한다.
• 해당 괄호를 제거하는 경우와 그렇지 않은 경우를 위해 DFS 알고리즘을 사용해야한다.
• 사전 순으로 출력해야한다는 조건을 맞추기 위해 자동으로 정렬되는 TreeSet 을 사용한다.

과정

• 정수형 스택 하나와 TreeSet 객체 하나, Pos 리스트를 사용한다.
• 입력 문자열에서 여는 괄호를 만난 경우는 스택에 현재 인덱스의 번호를 넣고, 닫는 괄호를 만난 경우 스택에서 괄호의 시작 위치를 꺼내어 Pos 객체를 새로 생성하고, 리스트에 추가한다.
• DFS 알고리즘을 수행해서 결과 문자열들을 담을 TreeSet 을 만든다.
• depth 가 괄호의 개수인 n 과 같은 경우, 공백을 제거하고 TreeSet 에 추가한다.
• 그렇지 않은 경우는 depth 인덱스에 위치한 괄호의 위치 정보를 꺼내서 해당 괄호를 제거한 문자열을 하나 만들고, 괄호를 제거하는 경우와 그렇지 않은 경우로 재귀 호출을 진행한다.
• DFS 알고리즘 수행이 끝난 후, TreeSet에서 입력 받았던 문자열을 제거한 다음, TreeSet 에 존재하는 모든 문자열을 출력한다.

💬 입출력 예시

📌 풀이(소스코드)

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

public class Main {

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        String s = br.readLine();
        Stack<Character> stack = new Stack<>();

        int total = 0;
        int val = 1;
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);

            if (c == '(') {
                stack.push(c);
                val *= 2;
            } else if (c == '[') {
                stack.push(c);
                val *= 3;
            } else if (c == ')') {
                if (stack.isEmpty() || stack.peek() != '(') {
                    total = 0;
                    break;
                }

                if (s.charAt(i - 1) == '(') {
                    total += val;
                }
                stack.pop();
                val /= 2;
            } else if (c == ']') {
                if (stack.isEmpty() || stack.peek() != '[') {
                    total = 0;
                    break;
                }

                if (s.charAt(i - 1) == '[') {
                    total += val;
                }
                stack.pop();
                val /= 3;
            }

        }

        if (!stack.isEmpty()) {
            System.out.println(0);
            return;
        }

        System.out.println(total);
    }
}

📄 해설

접근

• 스택을 사용하여 푸는 문제로, 소괄호와 대괄호 두 가지에 대한 케이스를 생각해야해서 까다로웠던 문제
• 여는 괄호를 계속 스택에 넣는 것은 동일하지만, 이 때 추가적인 처리가 필요했었다.
• 값들을 계산하는 기법을 생각해내지 못해서 해결하지 못하고 다른 사람의 풀이를 봤다.

과정

• Character 타입의 스택을 하나 선언하고, 결과 값을 담을 변수 ret 와 임시 계산 값을 담고 있을 변수 val 을 각각 0 과 1로 초기화한다. (val 을 1로 초기화한 이유는 이후 설명)
• 여는 괄호인 경우, 각 괄호에 따라 2 또는 3을 val 에 곱하고, 스택에 여는 괄호를 넣는다. 값을 더하는 것이 아니라 곱셈으로 계산하기 때문에 val 을 1로 초기화한 것
• 닫는 괄호의 경우 두 가지로 나뉜다.
  1. 스택이 비어있거나 스택의 탑이 같은 종류의 괄호가 아닌 경우는 올바른 괄호열이 아니므로 ret 을 0으로 초기화하고 출력한다.
  2. 직전 문자가 같은 종류의 괄호인 경우, ret 에 임시 값인 val 값을 더하고, 스택에서 여는 괄호를 꺼낸다. 그리고 val 값을 괄호에 따라 2 또는 3으로 나눈다.
• 문자열을 전부 순회했음에도 스택이 비어 있지 않은 경우도 올바른 괄호열이 아니므로 ret 을 0으로 초기화한다.
• ret 을 출력한다.

💬 입출력 예시

📌 풀이(소스코드)

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

public class Main {

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        String s = br.readLine();
        Stack<Character> stack = new Stack<>();
        int sum = 0;

        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);

            // 여는 괄호인 경우 스택에 넣고 다음 문자 확인
            if (c == '(') {
                stack.push(c);
                continue;
            }

            // 여는 괄호가 아닌 경우는 닫는 괄호 밖에 없음 -> 스택에서 꺼냄
            stack.pop();
            // 바로 직전문자가 여는 괄호 -> 레이저 -> 스택 크기 만큼 증가
            // 바로 직전 문자가 여는 괄호가 아니면 막대의 끝 -> 1 증가
            if (s.charAt(i - 1) == '(') {
                sum += stack.size();
            } else {
                sum++;
            }
        }

        System.out.println(sum);
    }
}

📄 해설

접근

• 스택을 사용하는 문제. 괄호 짝 맞추기 문제의 응용, 심화 버전이라고 보면 된다.
• 문자열을 탐색하면서 현재 문자가 여는 괄호인 경우, 스택에 넣고 닫는 괄호인 경우 필요한 처리를 해주면 된다.
• 이 문제에서는 닫는 괄호의 경우 해당 괄호가 레이저를 나타내는 괄호냐 쇠 막대기의 끝이냐를 구별해야하는데, 이는 바로 직전 문자가 여는 괄호인지 아닌지를 판별하면 된다.
• 쇠 막대기인 경우와 레이저인 경우의 처리를 다르게 해주어서 최종적으로 잘려지는 쇠 막대기 조각들의 총합을 구하면 된다.

과정

• 문자열을 입력 받고, 입력 받은 문자열의 문자를 하나씩 확인하면서 아래 과정을 수행한다.
  • 현재 문자가 여는 괄호인 경우 스택에 넣고 다음 문자를 확인한다. 이 문제의 경우 여는 괄호가 아닌 경우는 무조건 닫는 괄호이므로, continue 를 통해 다음 문자로 이동한다.
  • 현재 문자가 여는 괄호가 아닌 경우 무조건 닫는 괄호이므로, 스택에서 문자를 꺼낸다.
  • 현재 문자가 닫는 괄호이고, 바로 직전 문자가 여는 괄호라면 레이저이므로, 스택의 크기 만큼 sum 에 더해준다.
  • 직전 문자가 여는 괄호가 아니라면, 쇠 막대기의 끝이므로, sum 을 1만큼 증가시켜준다.
• sum 을 출력한다.

💬 입출력 예시

📌 풀이(소스코드)

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

public class Main {

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        int N = Integer.parseInt(br.readLine());
        Stack<Integer> stack = new Stack<>();

        int[] target = new int[N];
        for (int i = 0; i < N; i++) {
            target[i] = Integer.parseInt(br.readLine());
        }

        int idx = 0;
        for (int i = 1; i <= N; i++) {
            stack.push(i);
            sb.append("+\n");

            while (!stack.isEmpty() && stack.peek() == target[idx]) {
                stack.pop();
                idx++;
                sb.append("-\n");
            }
        }

        if (!stack.isEmpty()) {
            System.out.println("NO");
            return;
        }
        System.out.println(sb);
    }
}

📄 해설

접근

• 문제에 나와있듯, 스택을 사용하여 해결하는 문제이다.
• 스택에 넣는 순서는 오름차순이라고 했으므로, 1부터 N까지 스택에 넣고 빼면서 해당 수열을 만들 수 있는지 확인하면 된다.
• 만들려고하는 수열을 배열에 저장하고, 이를 스택의 탑과 비교한다.
• 1 부터 N 까지 처리를 마쳤음에도 스택이 비어있지 않다면 해당 수열을 만들 수 없다.

과정

• 길이가 N인 수열을 길이가 N인 배열 target 에 저장한다.

• 1부터 N까지 숫자를 증가시키면서 아래 과정을 반복한다.

  1. 현재 숫자를 스택에 넣고 + 를 출력한다.
  2. 스택의 탑에 있는 숫자가 target[idx] 의 원소와 같은지 확인한다. (이때 idx 는 만들려고 하는 수열에서 몇번째 숫자인지를 나타내는 변수이다.)
  3. 같다면 idx 를 증가시키고 스택에서 꺼내고 - 를 출력한다.

• 위 반복이 종료된 후에도 스택에 숫자가 남아있다면, 입력 받은 수열은 만들 수 없는 수열이므로, NO 를 출력한다. 그렇지 않으면 + 와 - 를 출력한다.

• + 와 - 를 출력하는 경우, 출력하지 않을수도 있으므로 StringBuilder 를 사용한다.

💬 입출력 예시

📌 풀이(소스코드)

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Deque;
import java.util.StringTokenizer;

public class Main {

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        int N = Integer.parseInt(br.readLine());
        Deque<Balloon> dq = new ArrayDeque<>();

        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            dq.add(new Balloon(i + 1, Integer.parseInt(st.nextToken())));
        }

        // 첫 풍선 터트리고 시작
        Balloon first = dq.pollFirst();
        int num = first.num;
        sb.append(first.idx).append(" ");

        while (!dq.isEmpty()) {
            Balloon now = null;

            if (num < 0) {
                // 음수인 경우 왼쪽으로 이동하는 것을 구현 -> 덱의 뒤에서 빼서 앞으로 옮긴다.
                for (int i = 0; i < -num; i++) {
                    dq.offerFirst(dq.pollLast());
                }

                // 왼쪽으로 이동할 경우, 터져야 할 풍선은 현재 맨 뒤에 위치함
                now = dq.pollFirst();
                num = now.num;
            } else {
                // 양수인 경우 오른쪽으로 이동하는 것을 구현 -> 덱의 앞에서 빼서 뒤로 옮긴다.
                for (int i = 0; i < num; i++) {
                    dq.offerLast(dq.pollFirst());
                }

                // 오른쪽으로 이동할 경우, 터져야 할 풍선은 현재 맨 앞에 위치함
                now = dq.pollLast();
                num = now.num;
            }

            sb.append(now.idx).append(" ");
        }

        System.out.println(sb);
    }

    static class Balloon {
        int idx;
        int num;

        public Balloon(int idx, int num) {
            this.idx = idx;
            this.num = num;
        }
    }
}

📄 해설

접근

• 원형으로 풍선이 있고, 1번의 왼쪽에 N번이, N번의 오른쪽에 1번이 있다는 것, 터진 풍선을 빼고 이동하는 것, 오른쪽과 왼쪽 모두로 이동하는 것 => 덱을 사용해야하는 문제로 접근
• 덱을 사용한다는 접근을 했다면, 접근은 90% 끝났다고 생각한다. 나머지 10%는 다음과 같다.
  • 양수인 경우 오른쪽으로 이동한다. => dq.offerFirst(dq.pollLast())
  • 음수인 경우 왼쪽으로 이동한다. => dq.offerLast(dq.pollFirst())
• 접근을 다 했다면 큰 무리없이 해결이 가능했을 것이다.

과정

• N 을 입력받고, 덱을 생성한다. 이때, 풍선의 번호와 종이에 적힌 숫자를 표현하기 위해 Balloon 이라는 클래스를 만들어 사용했다. (길이가 2인 배열을 사용해도 된다.)
• 첫 번째 풍선은 먼저 터트리고 출력해준다.
• 덱이 빌 때까지, 종이에 적힌 숫자에 따라 풍선을 덱에서 꺼내고 출력하면 되는데, 이때 유의할 점은 총 3칸을 움직인 경우, 터트려야 할 풍선도 같이 이동해있는 상태이기 때문에, num이 음수일 경우 맨 앞의 풍선을 꺼내고, 양수일 경우 맨 뒤의 풍선을 꺼내준다.

💬 입출력 예시

📌 풀이(소스코드)

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

public class Main {

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st = null;

        int T = Integer.parseInt(br.readLine());

        while (T-- > 0) {
            st = new StringTokenizer(br.readLine());
            int N = Integer.parseInt(st.nextToken());
            int M = Integer.parseInt(st.nextToken());

            Queue<Document> q = new LinkedList<>();
            int cnt = 0;

            st = new StringTokenizer(br.readLine());
            for (int i = 0; i < N; i++) {
                q.offer(new Document(i, Integer.parseInt(st.nextToken())));
            }

            while (!q.isEmpty()) {
                Document now = q.poll();

                int size = q.size();
                boolean isFirst = true;
                for (int i = 0; i < size; i++) {
                    if (q.peek().priority > now.priority) {
                        isFirst = false;
                    }
                    q.offer(q.poll());
                }

                if (isFirst) {
                    cnt++;
                    if (now.idx == M) {
                        sb.append(cnt).append("\n");
                        break;
                    }
                } else {
                    q.offer(now);
                }
            }
        }
        System.out.println(sb);
    }

    static class Document {
        int idx;
        int priority;

        public Document(int idx, int priority) {
            this.idx = idx;
            this.priority = priority;
        }
    }
}

📄 해설

접근

• 문제에서 주어진 설명 대로 따라가면 되는 문제이다. 큐를 사용해야하고, 필자처럼 클래스를 만들어서 사용해도 되는데, 싫으면 그냥 길이가 2인 정수배열을 사용해도 무방하다. 아마 이 경우가 메모리나 속도 측면에서 더 빠를 것이다.
• 문제에서 주어진 설명은 다음과 같다.
  1. 현재 큐의 맨 앞의 문서의 중요도를 확인한다.
  2. 현재 문서보다 중요도가 높은 문서가 있다면, 이 문서를 뒤로 보내고, 그렇지 않다면 인쇄를 한다.
• 1 과 2 의 과정을 통해 M 번째에 해당하는 문서가 몇번째로 인쇄되는지를 구하는 문제이다.

과정

• 테스트 케이스 T 를 입력 받고, 아래의 과정들을 반복한다.
• N 과 M 을 입력 받는다. 각각 문서의 개수, 몇번째로 인쇄되는지 알고 싶은 문서의 번호이다.
• N 개의 문서의 중요도를 입력 받으면서 몇번째 문서인지와 중요도를 클래스에 담고 큐에 넣는다.
• 큐가 빌 때까지 다음 과정을 반복한다.
  • 큐에서 원소 하나를 빼서 now 에 담고, 남은 원소들을 반복문을 통해 확인한다.
  • 큐에서 꺼낸 문서보다 중요도가 높은 문서를 발견한다면, isFirst 변수를 false 로 바꾼다. 그렇지 않다면 현재 큐의 맨앞에 있는 문서를 뒤로 보낸다. (지금 확인 중인 문서의 다음 문서이다.)
• 탐색이 끝난 후, isFirst 변수가 true 인 경우, 현재 문서의 중요도가 가장 높은 것이므로, cnt 값을 증가시키고, 현재 문서의 번호가 M 과 같은 값인지 확인한다.
• 같은 값이면 반복을 종료하고 출력한다.
• isFirst 변수의 값이 false 로 유지되고 있다면, 현재 문서를 다시 큐에 넣고 반복한다.

💬 입출력 예시

📌 풀이(소스코드)

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

public class Main {

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());
        String s = br.readLine();
        int idx = 0;
        Stack<Double> stack = new Stack<>();

        double[] arr = new double[N];
        for (int i = 0; i < N; i++) {
            arr[i] = Double.parseDouble(br.readLine());
        }

        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);

            if ('A' <= c && c <= 'Z') {
                stack.push(arr[c - 'A']);
            } else {
                double b = stack.pop();
                double a = stack.pop();

                if (c == '*') {
                    stack.push(a * b);
                } else if (c == '/') {
                    stack.push(a / b);
                } else if (c == '+') {
                    stack.push(a + b);
                } else if (c == '-') {
                    stack.push(a - b);
                }
            }
        }

        System.out.printf("%.2f", stack.pop());
    }
}

📄 해설

접근

• 스택을 사용해서 후위 표기식을 계산하는 방법을 알고 있어야 하고, 알파벳별 지정된 숫자를 배열에 저장해두고 사용한다는 것에 접근해야한다.
• 먼저 스택을 사용해서 후위 표기식을 계산하는 방법은 다음과 같다.
  1. 피연산자를 만나면 스택에 넣는다.
  2. 연산자를 만나면 스택에서 숫자 두 개를 꺼내서 계산하고 그 결과를 다시 스택에 넣는다.
  3. 마지막에 스택에 남아있는 수가 최종 연산 결과이다.
• 그리고 알파벳별로 지정된 숫자를 배열에 저장해둔다는 것은 다음과 같다.
  • A ~ Z 를 각각 아스키 코드 연산을 통해 배열의 0번 인덱스부터 25번 인덱스까지 다음과 같이 할당한다고 생각하면 된다. arr[{알파벳} - 'A']
• 결과 값이 실수가 나올 수 있으므로, 모든 변수를 실수형 타입으로 사용해준다.

과정

• A 부터 Z 까지 순서대로 숫자가 입력되므로, 순서대로 배열에 넣어준다.
• 이후 입력된 문자열의 모든 문자를 확인할 때까지 다음과 같은 과정을 반복한다.
  1. 연산자가 아닌 경우는 아스키 코드 연산을 통해 인덱스를 얻고, 그 인덱스로 배열에 접근해서 해당 값을 스택에 넣는다.
  2. 연산자를 만나면 스택에서 숫자 두개를 꺼내서 계산하고 그 결과를 다시 스택에 넣어준다.
• 스택의 마지막 원소가 연산의 결과값이므로, 스택에서 꺼내서 소숫점 둘째자리까지 출력해준다.

💬 입출력 예시

📌 풀이(소스코드)

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

public class Main {
    static int[] dq = new int[20001];
    static int start = 10000, end = 10000, size = 0;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        int N = Integer.parseInt(br.readLine());

        for (int i = 0; i < N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            String cmd = st.nextToken();

            if (cmd.equals("push_back")) {
                pushBack(Integer.parseInt(st.nextToken()));
            } else if (cmd.equals("push_front")) {
                pushFront(Integer.parseInt(st.nextToken()));
            } else if (cmd.equals("pop_front")) {
                sb.append(popFront()).append("\n");
            } else if (cmd.equals("pop_back")) {
                sb.append(popBack()).append("\n");
            } else if (cmd.equals("size")) {
                sb.append(size).append("\n");
            } else if (cmd.equals("empty")) {
                sb.append(empty()).append("\n");
            } else if (cmd.equals("front")) {
                sb.append(front()).append("\n");
            } else if (cmd.equals("back")) {
                sb.append(back()).append("\n");
            }
        }
        System.out.println(sb);
    }

    private static void pushBack(int x) {
        dq[++end] = x;
        size++;
    }

    private static void pushFront(int x) {
        dq[start--] = x;
        size++;
    }

    private static int popFront() {
        if (size == 0) {
            return -1;
        }
        size--;
        return dq[++start];
    }

    private static int popBack() {
        if (size == 0) {
            return -1;
        }
        size--;
        return dq[end--];
    }

    private static int empty() {
        if (size == 0) {
            return 1;
        }
        return 0;
    }

    private static int front() {
        if (size == 0) {
            return -1;
        }
        return dq[start + 1];
    }

    private static int back() {
        if (size == 0) {
            return -1;
        }
        return dq[end];
    }
}

📄 해설

결론부터 말하자면...

솔직히 결론부터 말하자면, 이 문제도 그냥 라이브러리 쓰면 되는 문제이다. 그러나 정수배열로 구현을 해서 덱의 내부 동작을 완전히 이해하고 싶은 사람이라면, 라이브러리도 사용해보고 정수배열도 사용해보는 것을 권장한다. 이론적으로 아는 것과 구현해본 것은 확실히 다르니까.

본론

• ArrayDeque 를 사용해서도 풀어보았고, 그냥 정수 배열로도 풀어보았다.
• 정수 배열의 경우 필자는 원형 배열을 사용할 생각을 못했는데, 다른 풀이를 찾아보던 중 원형 배열을 사용한 풀이가 있어서 같이 첨부하고자 한다.
• ArrayDeque 를 사용한 코드와 원형 배열을 사용한 코드는 아래에 따로 첨부하겠다. ArrayDeque 는 단순히 연산에 맞게 메소드를 호출하면 되고, 원형 배열은 코드에 주석으로 설명을 대체하겠다.
• 이전에 풀었던 스택과 큐 문제와 동일하게, 명령에 맞는 연산들을 메소드로 구현해서 풀이했다. 각각의 메소드에 대한 설명은 겹치니까 생략하고, 중요한 부분인 배열을 어떻게 사용할지와 인덱스 계산은 어떻게 하는지에 대한 설명을 아래에 작성하겠다.

참고로 원래 인덱스 변수명을 `front` 와 `rear` 로 표현하지만,
메소드 이름과 겹치게 사용하기 싫어서 같은 의미인 `start` 와 `end` 로 사용했다.

• front 인덱스와 rear 인덱스를 배열의 중간부터 시작하게 한다. 이유는 배열의 인덱스가 0부터 시작하는데, 덱을 배열로 구현하다보면 자칫 음수 인덱스가 되어 예외를 발생시킬 수 있기 때문이다.
• 그리고 배열이 중간부터 시작하므로, 배열의 크기는 주어진 명령의 개수인 10000 의 2배로, 20001 로 선언해준다.
• 배열로 구현할 때 주의점은, 어떤 풀이를 사용하더라도 front 인덱스가 가리키는 인덱스는 비어있어야한다. 즉, 실제로 front 인덱스에 해당하는 원소는 front + 1 의 위치에 존재하는 것이다.
• 이렇게 하는 이유는 아래와 같은 예외를 방지하기 위함이다.
  • 배열이 비어있는 상태에서 push 연산을 한다고 가정하자. 이때 push_front 를 한다면, 덱의 front 는 9999가 되고, 덱의 rear 는 여전히 10000을 가리킬 것이다.
  • 덱에 원소가 하나만 들어있으면, 해당 원소가 front 이자 rear 가 되어야 하는데, 위 경우는 그렇지 않은 것을 알 수 있다. 그러므로 덱의 front 에 먼저 원소를 넣고, front-- 를 해줘야하는 것이다.
• 사실 대부분의 코드 자체가 큐 구현에서 크게 벗어난 것이 없다. 단지 앞과 뒤에서의 연산을 고려해줘야하기 때문에 처음 구현해본다면 까다로울 것이다.

다른 풀이 (소스코드)

ArrayDeque 풀이

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.StringTokenizer;

public class Main {

    static BufferedReader br;
    static StringTokenizer st;
    static StringBuilder sb;
    static int N;
    static ArrayDeque<Integer> dq = new ArrayDeque<>();

    public static void main(String[] args) throws Exception {
        br = new BufferedReader(new InputStreamReader(System.in));
        sb = new StringBuilder();

        N = Integer.parseInt(br.readLine());

        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            String cmd = st.nextToken();

            switch (cmd) {
                case "push_front":
                    dq.addFirst(Integer.parseInt(st.nextToken()));
                    break;
                case "push_back":
                    dq.addLast(Integer.parseInt(st.nextToken()));
                    break;
                case "pop_front":
                    if (dq.size() == 0) {
                        sb.append(-1).append("\n");
                    } else {
                        sb.append(dq.pollFirst()).append("\n");
                    }
                    break;
                case "pop_back":
                    if (dq.size() == 0) {
                        sb.append(-1).append("\n");
                    } else {
                        sb.append(dq.pollLast()).append("\n");
                    }
                    break;
                case "size":
                    sb.append(dq.size()).append("\n");
                    break;
                case "empty":
                    if (dq.isEmpty()) {
                        sb.append(1).append("\n");
                    } else {
                        sb.append(0).append("\n");
                    }
                    break;
                case "front":
                    if (dq.isEmpty()) {
                        sb.append(-1).append("\n");
                    } else {
                        sb.append(dq.peekFirst()).append("\n");
                    }
                    break;
                case "back":
                    if (dq.isEmpty()) {
                        sb.append(-1).append("\n");
                    } else {
                        sb.append(dq.peekLast()).append("\n");
                    }
                    break;
            }
        }
        System.out.println(sb);
    }
}

원형 배열 풀이

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

public class Main {

    static final int ARRAY_SIZE = 10000;
    static int[] dq = new int[ARRAY_SIZE];
    static int start = 0, end = 0, size = 0;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        int N = Integer.parseInt(br.readLine());

        for (int i = 0; i < N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            String cmd = st.nextToken();

            if (cmd.equals("push_back")) {
                pushBack(Integer.parseInt(st.nextToken()));
            } else if (cmd.equals("push_front")) {
                pushFront(Integer.parseInt(st.nextToken()));
            } else if (cmd.equals("pop_front")) {
                sb.append(popFront()).append("\n");
            } else if (cmd.equals("pop_back")) {
                sb.append(popBack()).append("\n");
            } else if (cmd.equals("size")) {
                sb.append(size).append("\n");
            } else if (cmd.equals("empty")) {
                sb.append(empty()).append("\n");
            } else if (cmd.equals("front")) {
                sb.append(front()).append("\n");
            } else if (cmd.equals("back")) {
                sb.append(back()).append("\n");
            }
        }
        System.out.println(sb);
    }

    private static void pushBack(int x) {
        end = (end + 1) % ARRAY_SIZE;
        dq[end] = x;
        size++;
    }

    private static void pushFront(int x) {
        dq[start] = x;
        start = (start - 1 + ARRAY_SIZE) % ARRAY_SIZE;
        size++;
    }

    private static int popFront() {
        if (size == 0) {
            return -1;
        }

        int ret = dq[(start + 1) % ARRAY_SIZE];
        start = (start + 1) % ARRAY_SIZE;
        size--;
        return ret;
    }

    private static int popBack() {
        if (size == 0) {
            return -1;
        }
        int ret = dq[end];
        end = (end - 1 + ARRAY_SIZE) % ARRAY_SIZE;
        size--;
        return ret;
    }

    private static int empty() {
        if (size == 0) {
            return 1;
        }
        return 0;
    }

    private static int front() {
        if (size == 0) {
            return -1;
        }
        return dq[(start + 1) % ARRAY_SIZE];
    }

    private static int back() {
        if (size == 0) {
            return -1;
        }
        return dq[end];
    }
}

[원형배열 풀이 링크는 여기로!] (https://st-lab.tistory.com/211)

💬 입출력 예시

📌 풀이(소스코드)

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

public class Main {

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());
        ArrayDeque<Integer> dq = new ArrayDeque<>();

        for (int i = 1; i <= N; i++) {
            dq.addLast(i);
        }

        while (dq.size() > 1) {
            dq.pollFirst();
            dq.addLast(dq.pollFirst());
        }

        System.out.println(dq.poll());
    }
}

📄 해설

접근

• 문제의 설명에 따라, 단순히 큐의 크기가 1이 될때까지 맨 앞의 원소를 빼서 버리고, 그 다음 맨 앞의 원소를 맨 뒤로 보내는 작업을 반복하면 되는 문제이다.

과정

• 문제 풀이는 간단하다. 1부터 N 까지의 정수를 큐에 넣고, 큐에 정수가 1개 남을때까지 dq.pollFirst() 를 통해 맨 앞의 원소를 빼준다.
• 그 다음 맨 앞의 원소가 된 것은 dq.addLast(dq.pollFirst()) 를 통해 맨 뒤로 옮겨준다.
• 마지막으로 남은 원소를 dq.poll() 를 통해 빼내어 출력한다.

ArrayDeque vs LinkedList ?

• ArrayDeque 가 아니라 LinkedList 를 사용해서 풀어도 된다. 어차피 덱의 기능까지는 사용할 필요가 없다.
• 그런데 ArrayDeque 로 풀이를 올린 이유는 ArrayDeque 와 LinkedList 를 사용했을 때의 메모리 차이에 있다.
• 이미지에서 위의 결과가 ArrayDeque, 아래의 결과가 LinkedList 이다.
• 위와 같이 시간에서는 차이가 발생하지 않았지만, 메모리에서 2배에 가까운 효율 차이를 보인다.
• 그 이유는 ArrayDeque 는 LinkedList 와 달리 다음 노드에 대한 참조를 유지할 필요가 없기 때문에 더 적은 메모리를 사용하기 때문이다.
• 그리고 본 문제에서는 특정 원소에 접근할 필요가 없었기 때문에 연산 속도에서의 차이를 보지는 못했는데, ArrayDeque 는 Random Access가 가능하기 때문에 조회에서도 LinkedList 에 비해 빠르다.

• 둘을 비교한 고마운 정리 글이 있어 가져와봤다.
• 그래서 필자는 앞으로 큐를 구현할 때는 ArrayDeque 를 사용하려한다.

위 정리글 이미지 출처 (누르면 이동 됩니당)