blossun / algorithm Goto Github PK

View Code? Open in Web Editor NEW

0.0 1.0 0.0 955 KB

자료구조, 알고리즘 학습 저장소

Python 3.42% Java 96.58%

algorithm's Introduction

Programmers

Programmers.md

🌵문제풀이를 이슈로 관리합니다.

algorithm's People

Contributors

Watchers

algorithm's Issues

아이디어

알파벳 크기만큼 배열을 생성해서 각 문자가 등장할 때마다 해당하는 알파벳 인덱스의 값을 +1 씩 한다.
시간 복잡도 : O(n)

어려운점 & 실수

정답

import java.io.*;

public class N10808 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        char[] chars = br.readLine().toCharArray();
        int[] alpha = new int[26];
        for (char c : chars) {
            alpha[(int)c - 'a']++;
        }
        for (int i : alpha) {
            bw.write(i + " ");
        }
        bw.flush();
        bw.close();
        br.close();
    }
}

아이디어

10 size의 배열 : 한 셋트 0 ~ 9
숫자 배열 입력받아서 해당 번호의 인덱스 값 +1
6이면 6값을 +1 계속하기
9이면 9값을 +1 계속하기
최종적으로 6과 9의 갯수를 더해서 /2 한 값이 (6과 9의 )필요한 셋트 수 가 된다.
각 인덱스의 값이 가장 높은 값 = 필요한 셋트 수 (6과 9는 별도로 계산)

어려운점 & 실수

(잘못 생각한 아이디어)
이미 값이 1인 경우 새로운 셋트 추가 -> X
but, 6이거나 9인 경우 서로의 값도 확인 -> X

정답

import java.util.Arrays;
import java.util.Scanner;

public class N1475 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int[] numbers = Arrays.stream(sc.nextLine().split("")).mapToInt(Integer::parseInt).toArray();
        int total = 0;
        int[] cardSet = new int[10];
        for (int number : numbers) {
            cardSet[number]++;
        }
        // 6과 9 때문에 필요한 셋트 수를 먼저 계산해서 total에 저장
        total = (int) Math.round((double) (cardSet[6] + cardSet[9]) / 2); //5개변 3개가 필요
        // 6과 9는 계산했으니깐 초기
        cardSet[6] = 0;
        cardSet[9] = 0;
        // 더 많이 필요한 숫자가 있는 경우 해당 숫자의 갯수가 필요한 셋트 수가 된다.
        int temp = Arrays.stream(cardSet).max().getAsInt();
        if (temp > total) {
            total = temp;
        }
        System.out.println(total);
    }
}

아이디어

입력은 한번에 br로 받아서 처리해야할듯
~~입력문자가 영문 A~~Z,a~~z인 경우?? (특수키가 아닌경우) 저장하는 스택 1~~
~~특수키(지우기, 커서 위치 이동)를 저장하는 스택 2~~
커서를 기준으로
왼쪽 문자 스택 : left
오른쪽 문자 스택 : right
각 키입력마다에 따라 push, pop을 진행

어려운점 & 실수

정답

package dev.solar.baekjoon;

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

public class N5397 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int n = Integer.parseInt(br.readLine());

        for (int i = 0; i < n; i++) {
            char[] keyLoger = br.readLine().toCharArray();
            Stack<Character> left = new Stack<>();
            Stack<Character> right = new Stack<>();
            for (char c : keyLoger) {
                if (c == '<') {
                    if (!left.empty()) {
                        right.push(left.pop());
                    }
                } else if (c == '>') {
                    if (!right.empty()) {
                        left.push(right.pop());
                    }
                } else if (c == '-') {
                    if (!left.empty()) {
                        left.pop();
                    }
                } else { //문자인 경우
                    left.push(c);
                }
            }
            // 모든 문자를 right 스택으로 이동
            while (!left.empty()) {
                right.push(left.pop());
            }
            // 문자 출력
            while (!right.empty()) {
                bw.write(right.pop());
            }
            bw.write('\n');
        }
        bw.flush();
        bw.close();
        br.close();
    }


}

아이디어

int 배열로 만들어서 총합을 구함 → 합에 따라 도개걸윷모로 매핑해서 출력

어려운점 & 실수

정답

import java.io.*;
import java.util.Arrays;
import java.util.stream.IntStream;

public class N2490 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int[] numbs = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        bw.write(mapping(IntStream.of(numbs).sum()) + "\n");
        numbs = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        bw.write(mapping(IntStream.of(numbs).sum()) + "\n");
        numbs = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        bw.write(mapping(IntStream.of(numbs).sum()) + "\n");
        bw.flush();
        bw.close();
        br.close();
    }

    public static char mapping(int n) {
        if (n == 4) {
            return 'E';
        } else if (n == 3) {
            return 'A';
        } else if (n == 2) {
            return 'B';
        } else if (n == 1) {
            return 'C';
        }
        return 'D';
    }
}

아이디어

어려운점 & 실수

정답

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

public class N9012 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int testCase = Integer.parseInt(br.readLine());
        for (int i = 0; i < testCase; i++) {
            char[] cmd = br.readLine().toCharArray();
            Stack<Character> st = new Stack<>();
            boolean isVPS = true;
            for (int j = 0; j < cmd.length; j++) {
                if (cmd[j] == '(') {
                    st.push('(');
                    continue;
                } else { // ')' 인 경우
                    if (st.empty()) { // 스택이 비어있으면 false, 스택에 push되는 문자는 '(' 밖에 없으니깐 다른 비교 필요 없음
                        isVPS = false;
                        break;
                    }
                    st.pop();
                }
            }
            // 스택이 남아있으면 false
            if (!st.empty()) {
                isVPS = false;
            }
            bw.write(isVPS ? "YES\n" : "NO\n");
        }
        bw.flush();
        bw.close();
        br.close();
    }
}

아이디어

어려운점 & 실수

정답

import java.util.Scanner;

public class N10807 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int size = sc.nextInt();
        int[] nums = new int[size];
        for (int i = 0; i < size; i++) {
            nums[i] = sc.nextInt();
        }
        int findNum = sc.nextInt();
        int count = 0;
        for (int num : nums) {
            if (num == findNum) {
                count++;
            }
        }
        System.out.println(count);
    }
}

⇒ O(n) 인데, nums를 101사이즈 배열로 선언해서 값을 입력받을 때, 입력값에 대응되는 인덱스 위치의 값을 +1 시킨다. → 나중에 찾을 때 해당값의 인덱스 값에 접근하면 ( nums[findNumber] ) O(1) 로 찾을 수 있다.

아이디어

자바가 제공하는 Queue를 이용하면 쉽게 풀림

어려운점 & 실수

Java의 컬렉션 Queue 를 쓰지 않고 직접 배열로 원형큐를 구현해서 사용하려다보니 어디서 잘못된 건지 모르겠다....
배열 길이를 늘려서 통과했는데, 그러면 원형 큐로 구현한 의미가 있는 건가?
첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 2,000,000)이 주어진다.
즉, 배열의 길이는 push 명령이 2000000개 일 수 있으니 그만큼 크게 잡아줘야 하나? → 그렇다면 배열의 크기를 줄이고 원형큐로 구현하는 것은 의미가 없나?

정답

import java.io.*;

public class N18258 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        MyQueue queue = new MyQueue();
        int n = Integer.parseInt(br.readLine());
        String[] cmd;
        for (int i = 0; i < n; i++) {
            cmd = br.readLine().split(" ");
            switch (cmd[0]) {
                case "push" :
                    queue.push(Integer.parseInt(cmd[1]));
//                    bw.write(cmd[1]);
                    break;
                case "front" :
                    bw.write(queue.front() + "\n");
                    break;
                case "back" :
                    bw.write(queue.back() + "\n");
                    break;
                case "size" :
                    bw.write(queue.size() + "\n");
                    break;
                case "empty" :
                    bw.write(queue.empty() ? "1\n" : "0\n");
                    break;
                case "pop" :
                    bw.write(queue.pop() + "\n");
                    break;
            }
        }
        bw.flush();
        bw.close();
        br.close();
    }

    static class MyQueue {
        // 원형큐 구현
        // head, tail의 시작은 0으로
        int max = 2000000; //이걸 늘려주니깐 통과함....  이걸 쓸거면 원형 큐 쓰는 의미가 없는 거 아닌가?
        int[] queue = new int[max];
        int head, tail = 0;

        public void push(int x) {
            if (full()) {
                return ;
            }
            tail = (tail + 1) % max;
            queue[tail] = x;
        }

        public int pop() {
            if (empty()) {
                return -1;
            }
            head = (head + 1) % max;
            return queue[head];
        }

        public int size() {
            return tail - head;
        }

        // 큐가 비었는지 확인
        public boolean empty() {
            return head == tail;
        }

        // 큐가 꽉 찼는지 확인
        public boolean full() {
            return (tail + 1) % max == head;
        }

        public int front() {
            return empty() ? -1 : queue[(head + 1) % max];
        }

        public int back() {
            return empty() ? -1 : queue[tail];
        }
    }
}

20.10.15 [프로그래머스] SQL 1단계

문제 : SQL 최댓값 구하기
https://programmers.co.kr/learn/courses/30/lessons/59415

SELECT DATETIME from animal_ins order by datetime desc limit 1;

아이디어

100보다 작은 자연수만 입력된다고 했으므로 min 초기값을 100으로 잡음

어려운점 & 실수

정답

import java.util.Scanner;

public class N2576 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int min = 100;
        int num;
        int sum = 0;
        for (int i = 0; i < 7; i++) {
            num = sc.nextInt();
            if (num % 2 != 0) {
                sum += num;
                if (num < min) {
                    min = num;
                }
            }
        }
        if (sum == 0) {
            System.out.println(-1);
            return ;
        }
        System.out.println(sum + "\n" + min);
    }
}

아이디어

어려운점 & 실수

정답

import java.io.*;
import java.util.ArrayDeque;
import java.util.Deque;

public class N10866 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int n = Integer.parseInt(br.readLine());
        Deque<Integer> deque = new ArrayDeque<>();
        String[] command;
        for (int i = 0; i < n; i++) {
            command = br.readLine().split(" ");
            switch (command[0]) {
                case "push_front" :
                    deque.addLast(Integer.parseInt(command[1]));
                    break;
                case "push_back" :
                    deque.addFirst(Integer.parseInt(command[1]));
                    break;
                case "pop_front" :
                    bw.write(deque.isEmpty() ? "-1\n" : deque.removeLast() + "\n");
                    break;
                case "pop_back" :
                    bw.write(deque.isEmpty() ? "-1\n" : deque.removeFirst() + "\n");
                    break;
                case "size" :
                    bw.write(deque.size() + "\n");
                    break;
                case "empty" :
                    bw.write(deque.isEmpty() ? "1\n" : "0\n");
                    break;
                case "front" :
                    bw.write(deque.isEmpty() ? "-1\n" : deque.getLast() + "\n");
                    break;
                case "back" :
                    bw.write(deque.isEmpty() ? "-1\n" : deque.getFirst() + "\n");
                    break;

            }
        }
        bw.flush();
        bw.close();
        br.close();
    }
}

아이디어

어려운점 & 실수

String → String[]
String을 split하면 Char[]로는 만들 수 없고 String[]로 나오기때문에 하나의 문자열로 합치기 위해서 Stirng[]을 String으로 만드는 join을 활용함
String → char[]

정답

class Solution {
    public String solution(String phone_number) {
        String[] answers = phone_number.split("");
        int size = answers.length;
        for (int i = 0; i < size - 4; i++) {
            answers[i] = "*";
        }
        return String.join("", answers);
    }
}

class Solution {
    public String solution(String phone_number) {
        //String[] answers = phone_number.split("");
        char[] answers = phone_number.toCharArray();
        int size = answers.length;
        for (int i = 0; i < size - 4; i++) {
            answers[i] = '*';
        }
        return String.valueOf(answers);
    }
}

아이디어

어려운점 & 실수

정답

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

public class N10773 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        Stack<Integer> stock = new Stack<>();
        for (int i = 0; i < n; i++) {
            int number = Integer.parseInt(br.readLine());
            if (number == 0) {
                if (!stock.empty()) stock.pop();
            } else {
                stock.push(number);
            }
        }

        int result = 0;
        while (!stock.empty()) {
            result += stock.pop();
        }
        System.out.println(result);
        br.close();
    }
}

아이디어

어려운점 & 실수

x, y 좌표 인덱스로 넣어야 하는데 n, m으로 잘못넣음 ㅠㅠㅠ
수정 전

if (board[x][y] == 0 || visit[n][m]) continue; //배추가 없거나 이전에 방문한 곳이면 skip

수정 후

if (board[x][y] == 0 || visit[x][y]) continue; //배추가 없거나 이전에 방문한 곳이면 skip

정답

package dev.solar.baekjoon;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class N1012 {
    static int[][] board;
    static boolean[][] visit;
    static int[] dx = {0, 0, 1, -1};
    static int[] dy = {1, -1, 0, 0};
    static int N; //행
    static int M; //열

    static class Point {
        int x;
        int y;

        public Point(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int testCase = Integer.parseInt(br.readLine());
        for (int i = 0; i < testCase; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine().trim(), " ");
            N = Integer.parseInt(st.nextToken());
            M = Integer.parseInt(st.nextToken());
            board = new int[N][M];
            visit = new boolean[N][M];
            int count = 0; //필요한 지렁이 수

            int K = Integer.parseInt(st.nextToken()); //배추 위치 갯수
            for (int k = 0; k < K; k++) {
                st = new StringTokenizer(br.readLine().trim(), " ");
                board[Integer.parseInt(st.nextToken())][Integer.parseInt(st.nextToken())] = 1;
            }

            Queue<Point> q = new LinkedList<>();

            for (int n = 0; n < N; n++) {
                for (int m = 0; m < M; m++) {
                    if (board[n][m] != 1 || visit[n][m]) continue; //배추가 심어져있지 않거나 이전에 방문한 곳이면 skip
                    count++; //시작위치면 지렁이 수 +1
                    visit[n][m] = true; //시작위치 방문 표시
                    q.add(new Point(n, m)); //시작 위치 큐에 담기

                    while (!q.isEmpty()) {
                        Point cur = q.poll();
                        for (int dir = 0; dir < 4; dir++) { // 네 방향 확인
                            int x = cur.x + dx[dir];
                            int y = cur.y + dy[dir];
                            if (x < 0 || x >= N || y < 0 || y >= M) continue; //범위 박이면 skip
                            if (board[x][y] == 0 || visit[x][y]) continue; //배추가 없거나 이전에 방문한 곳이면 skip
                            visit[x][y] = true;
                            q.add(new Point(x, y));
                        }
                    }
                }
            }

            System.out.println(count);
        }
    }
}

아이디어

연결리스트를 이용해서 스택 구현
BufferedWriter로 출력했을 때 확연한 속도 차이

어려운점 & 실수

정답

import java.io.*;
import java.util.ArrayList;
import java.util.List;

public class N10828 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        MyStack myStack = new MyStack();
        int n = Integer.parseInt(br.readLine());
        for (int i = 0; i < n; i++) {
            String[] cmdLine = br.readLine().split(" ");
            String cmd = cmdLine[0];
            if (cmd.equals("push")) {
                myStack.push(Integer.parseInt(cmdLine[1]));
            } else if (cmd.equals("top")) {
                if (!myStack.empty()) {
                    bw.write(myStack.top() + "\n");
                } else {
                    bw.write("-1" + "\n");
                }
            } else if (cmd.equals("size")) {
                bw.write(myStack.size() + "\n");
            } else if (cmd.equals("pop")) {
                if (!myStack.empty()) {
                    bw.write(myStack.pop() + "\n");
                } else {
                    bw.write("-1" + "\n");
                }
            } else if (cmd.equals("empty")) {
                bw.write(myStack.empty() ? "1" : "0" + "\n");
            }
        }
        bw.flush();
        bw.close();
        br.close();
    }

    static class MyStack {
        // 연결리스트로 스택 구현
        private List<Integer> stock = new ArrayList<>();
        private int top;

        public MyStack() {
            this.top = -1;
        }

        public void push(int value) {
            stock.add(value);
            top++;
        }

        public int pop() {
            int result = stock.get(top);
            stock.remove(top);
            top--;
            return result;
        }

        public int size() {
            return stock.size();
        }

        public boolean empty() {
            return stock.isEmpty();
        }

        public int top() {
            return stock.get(top);
        }

        public List<Integer> getStock() {
            return stock;
        }
    }
}

아이디어

소수인지 판별하기 위한 반복 범위를 줄여야함

어려운점 & 실수

정답

import java.lang.Math;

class Solution {
    public int solution(int n) {
        int answer = 0;
        
        for (int i = 1; i <= n; i++) {
            if (isPrime(i)) {
              answer++;  
            }
        }
        
        return answer;
    }
    
    public boolean isPrime(int n) {
        if (n == 1) {
            return false;
        }
        for (int i = 2; i <= Math.sqrt(n); i++) {
            if (n % i == 0) {
                return false;
            }
        }
        return true;
    }
}

20.10.15 [프로그래머스] SQL 2단계

문제 : 최솟값 구하기
https://programmers.co.kr/learn/courses/30/lessons/59038

SELECT DATETIME from animal_ins order by datetime limit 1;

아이디어

첫째 줄에 도화지의 세로 크기 n(1 ≤ n ≤ 500)과 가로 크기 m(1 ≤ m ≤ 500)이 차례로 주어진다.
=> board 크기를 이보다 크게 잡아줌
Pair 자료구조를 직접 구현

어려운점 & 실수

정답

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class N1926 {
    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[][] board = new int[n][m]; // 칸
        int[][] visit = new int[n][m]; // 방문 여부 표시 : 1 - 방문함, 0 - 방문 안 함
        int[] dx = {1, 0, -1, 0}; //상하좌우 네 방향
        int[] dy = {0, 1, 0, -1};
        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine()); //한 줄씩 받아줘야 함
            for (int j = 0; j < m; j++) {
                board[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        int max = 0; //그림 최댓값
        int num = 0; //그림의 수
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) { //(i, j)를 시작지점으로
                //해당 좌표가 그림부분이 아니거나(0) 이미 방문한 곳(visit[i][j]이면 넘어감
                if (board[i][j] == 0 || visit[i][j] != 0) continue;
                // (i, j)는 새로운 그림에 속해있는 시작점
                num++; // 그림의 수 1 증가
                Queue<Pair<Integer, Integer>> q = new LinkedList<>(); //큐에 (x,y)좌표 pair 타입 데이터 저장
                // (i, j)를 BFS의 시작점으로 출발하기 위한 준비
                // 방문 표시를 큐에 넣을 때 해줌!!!!
                // (뺄 때 표시 no -> 같은 칸이 큐에 여러 번 들어가서 시간 초과나 메모리 초과 발생할 수 있음)
                visit[i][j] = 1; // 시작점을 방문했다고 표시
                q.add(new Pair<>(i, j));
                int area = 0; //현재 그림의 넒이
                while(!q.isEmpty()) {
                    area++; //큐에 들어있는 원소를 하나 뺄 때 마다 넓이를 1 증가시킴
                    Pair cur = q.poll();
                    for (int dir = 0; dir < 4; dir++) { //현재 좌표의 상하좌우 칸을 살펴봄
                        int nx = (int) cur.getLeft() + dx[dir];
                        int ny = (int) cur.getRight() + dy[dir];
                        if (nx < 0 || nx >= n || ny < 0 || ny >= m ) continue; // 범위 밖일 경우 넘어감
                        if(visit[nx][ny] != 0 || board[nx][ny] != 1) continue; // 이미 방문한 칸이거나 파란 칸이 아닐 경우
                        visit[nx][ny] = 1; //(nx, ny)를 방문했다고 명시
                        q.add(new Pair<>(nx, ny));
                    }
                }
                max = Math.max(max, area); // area가 mx보다 클 경우 mx에 area를 대입.
            }
        }
        System.out.println(num + "\n" + max);
    }

    public static class Pair<L,R> {

        private final L left;
        private final R right;

        public Pair(L left, R right) {
            this.left = left;
            this.right = right;
        }

        public L getLeft() { return left; }
        public R getRight() { return right; }

        @Override
        public int hashCode() { return left.hashCode() ^ right.hashCode(); }

        @Override
        public boolean equals(Object o) {
            if (!(o instanceof Pair)) return false;
            Pair pairo = (Pair) o;
            return this.left.equals(pairo.getLeft()) &&
                    this.right.equals(pairo.getRight());
        }

    }
}

아이디어

LinkedList로 풀면 답은 나오지만 효율성 테스트 통과 못함 → 해시로 풀어서 속도개선
(다른 풀이)
완주 못한 선수는 항상 1명이다. 즉, 두 배열 길이의 차가 항상 1이다. 따라서 각 배열을 순서대로 정렬한 뒤 하나씩 비교하면서 일치하지 않는 인덱스의 선수를 return 하면 된다.

어려운점 & 실수

정답

import java.util.*;

class Solution {
    public String solution(String[] participants, String[] completion) {
        String answer = "";

        Map<String, Integer> result = new HashMap<>();

        for (String participant : participants) {
            if (result.get(participant) == null) {
                result.put(participant, 1);
                continue;
            }
            int val = result.get(participant);
            result.put(participant, val + 1);
        }
        
        for (String comp : completion) {
            int val = result.get(comp);
            result.put(comp, val - 1);
        }
        
        for (String key : result.keySet()) {
            if (result.get(key) == 1) {
                answer = key;
            }
        }

        return answer;
    }
}

아이디어

지금 시작점이 여러 개인 BFS를 돌 수 있어야 한다.
⇒ 모든 시작점을 큐에 넣고 앞에서 한 것과 똑같이 BFS를 돌면 끝

어려운점 & 실수

토마토가 안들어있거나 이미 익은 경우에 대한 체크
if (board[x][y] == -1 || days[x][y] >= 0) continue;
→ (실수) 0보다 크거나 같은 경우로 체크해야함!!
앞서 안익은 토마토는 -1로 초기화했으므로, 기본적으로 익은 토마토는 0임

정답

package dev.solar.baekjoon;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class N7576 {
    static int[][] board;
    static int[][] days;
    static int[] dx = {0, 0, 1, -1};
    static int[] dy = {1, -1, 0, 0};
    static int N;
    static int M;

    static class Point {
        int x;
        int y;

        public Point(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine().trim(), " ");
        M = Integer.parseInt(st.nextToken()); //행,열 구분 잘해줄 것
        N = Integer.parseInt(st.nextToken());

        board = new int[N][M];
        days = new int[N][M];

        Queue<Point> q = new LinkedList<>();
        int maxDays = 0;

        for (int n = 0; n < N; n++) {
            String[] strings = br.readLine().trim().split(" ");
            for (int m = 0; m < M; m++) {
                board[n][m] = Integer.parseInt(strings[m]);
//                board[n][m] = strings[m].charAt(0) - '0'; //오류 - '-1' 값이 들어올 수 있어서
                if (board[n][m] == 1) //모든 시작위치(익은 토마토)를 큐에 저장
                    q.add(new Point(n, m));
                if (board[n][m] == 0) //안 익은 토마토는 dist를 -1로 초기화, 익은토마토는 default 값인 0으로 초기화될 것임
                    days[n][m] = -1;
            }
        }

        while (!q.isEmpty()) {
            Point cur = q.poll();
            for (int i = 0; i < 4; i++) {
                int x = cur.x + dx[i];
                int y = cur.y + dy[i];
                if (x < 0 || x >= N || y < 0 || y >= M) continue; //범위 밖인 경우
                if (board[x][y] == -1 || days[x][y] >= 0) continue; //토마토가 안들어있거나 이미 익은 경우 //0보다 크거나 같은 경우로 체크해야함!! 0은 맨처음부터 익어있던 토마토임
                days[x][y] = days[cur.x][cur.y] + 1; //익을 날짜 +1
                maxDays = Math.max(maxDays, days[x][y]); //모두 익을 최소 날짜
                q.add(new Point(x, y));
            }
        }

        // 모두익지 않은 상황이면 -1 출력
        for (int n = 0; n < N; n++) {
            for (int m = 0; m < M; m++) {
                if (board[n][m] == 0 && days[n][m] == -1) {
                    System.out.println("-1");
                    return ;
                }
            }
        }
        System.out.println(maxDays);
    }
}

아이디어

다른 사람 풀이를 보고, 배열을 스택처럼, List를 스택처럼 활용해서 한번에 비교해 나가는 풀이가 인상깊었다.

어려운점 & 실수

출력결과가 맞는데 출력 초과로 실패
→ BufferedWriter로 출력할 내용을 저장하고 있었는데, 아무래도 NO를 출력하고 로컬에서는 return 되어서 더이상 출력 안되었지만, flush하면서 더 출력이 되지 않았을까 싶다.
→ StringBuilder로 출력할 내용을 저장해서 마지막에 출력해주도록 변경 후, 통과
반례를 보고 문제의 매커니즘을 다시 생각했음

정답

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

public class N1874 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        int max = Integer.parseInt(br.readLine());
        int number = Integer.parseInt(br.readLine());
        Stack<Integer> left = new Stack<>();
        Stack<Integer> right = new Stack<>();
        int i = 1;
        
        while (i <= max) {
            if (i == number) {
                left.push(i);
                sb.append("+\n");
                right.push(left.pop());
                sb.append("-\n");
                if (i < max) {
                    number = Integer.parseInt(br.readLine());
                }
                i++;
            } else {
                // 입력값보다 i 가 작은/큰 경우
                if (i < number) { //작으면 오름차순으로 계속해서 next 입력값이 나올 때까지 left에 push
                    left.push(i);
                    sb.append("+\n");
                    i++;
                } else { //큰 경우 left에 push해 놓은 값들을 pop해서 같은지 확인
                    if (left.peek().equals(number)) { //같으면 pop해서 right로 이동
                        right.push(left.pop());
                        sb.append("-\n");
                        number = Integer.parseInt(br.readLine());
                    } else { //다르면 만들 수 없는 수열이므로 바로 "NO"를 출력하고 종료
                        System.out.print("NO");
                        return ;
                    }
                }
            }
        }

        // 최곳값 이후 left 스택과 남은 입력값을 비교
        // left 스택에 남은 값이 남은 입력값 보다 적게 남은 경우....?
        if (!left.empty()) {
            number = Integer.parseInt(br.readLine());
        }

        while (!left.empty()) {
            if (left.pop() == number) {
                sb.append("-\n");
                if (left.empty()) {
                    break;
                }
                number = Integer.parseInt(br.readLine());
            } else {
                System.out.print("NO");
                return ;
            }
        }

        System.out.println(sb);
        br.close();
    }
}

아이디어

불에 대한 BFS와 지훈이에 대한 BFS를 모두 돌림으로서 해결

먼저 지훈이는 신경쓰지 말고 불에 대한 BFS를 돌려서 미리 각 칸에 불이 전파되는 시간을 다 구해둬요.

그 다음에는 지훈이에 대한 BFS를 돌리며 지훈이를 이동시킵니다. 이 때 만약 지훈이가 특정 칸을 x시간에 최초로 방문할 수 있는데 그 칸에는 x시간이나 그 이전에 불이 붙는다면 그 칸을 못가게 됩니다.

어려운점 & 실수

사람이 갈 수 있는 진로 조건을 잘 살펴야 함
불이 먼저 붙은 곳은 가지 못함. 숫자가 낮다는 것은 (사람보다 빠른 시간으로) 먼저 도착했다는 의미

if (fire[x][y] != -1 && fire[x][y] <= visit[cur.x][cur.y] + 1) continue;

fire[x][y] != -1 : 불이 이미 도착했고를 and 연산으로 추가해줘야함. (도착하지 않았을 때가 -1)

정답

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;

public class N4179 {
    static char[][] board;
    static int[][] visit; //사람의 이동 시간
    static int[][] fire; //불의 전파 시간
    static int[] dx = {0, 0, 1, -1};
    static int[] dy = {1, -1, 0, 0};
    static int N;
    static int M;

    static class Point {
        int x;
        int y;

        public Point(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] nm = br.readLine().split(" ");
        N = Integer.parseInt(nm[0]);
        M = Integer.parseInt(nm[1]);
        board = new char[N][M];
        visit = new int[N][M];
        fire = new int[N][M];
        Queue<Point> fireQ = new LinkedList<>();
        Queue<Point> visitQ = new LinkedList<>();

        for (int n = 0; n < N; n++) {
            Arrays.fill(fire[n], -1); // fire -1로 초기화(방문하지 않은 위치)
            Arrays.fill(visit[n], -1); // visit -1로 초기화(방문하지 않은 위치)
        }

        // board 채우기
        // 입력받으면서 체크 - J면 visit 시작 위치로, F이면 fire 시작 위치로
        for (int n = 0; n < N; n++) {
            board[n] = br.readLine().toCharArray();
            for (int m = 0; m < M; m++) {
                char ch = board[n][m];
                if (ch == 'J') {
                    visit[n][m] = 0;
                    visitQ.add(new Point(n, m));
                }
                if (ch == 'F') {
                    fire[n][m] = 0;
                    fireQ.add(new Point(n, m));
                }
            }
        }

        // 먼저 불이 확산되는 경로 추적
        while (!fireQ.isEmpty()) {
            Point cur = fireQ.poll();
            for (int i = 0; i < 4; i++) {
                int x = cur.x + dx[i];
                int y = cur.y + dy[i];
                // 벽이면 확산 안 됨.
                if (x < 0 || x >= N || y < 0 || y >= M) continue; //범위를 벗어나면 skip
                if (board[x][y] == '#' || fire[x][y] >= 0) continue; //벽이거나 이미 퍼진곳은 skip
                fire[x][y] = fire[cur.x][cur.y] + 1;
                fireQ.add(new Point(x, y));
            }
        }

//        for (int[] ints : fire) {
//            for (int anInt : ints) {
//                System.out.print(anInt);
//            }
//            System.out.println();
//        }

        // 사람 경로
        while (!visitQ.isEmpty()) {
            Point cur = visitQ.poll();
            for (int i = 0; i < 4; i++) {
                int x = cur.x + dx[i];
                int y = cur.y + dy[i];
                // 벽이면 확산 안 됨.
                if (x < 0 || x >= N || y < 0 || y >= M) { //범위를 벗어났다는 것은 탈출했다는 의미
                    System.out.println(visit[cur.x][cur.y] + 1);
                    return;
                }
                if (board[x][y] == '#' || visit[x][y] >= 0) continue; //벽이거나 이미 방문한 곳은 skip
                if (fire[x][y] != -1 && fire[x][y] <= visit[cur.x][cur.y] + 1)
                    continue; //불이 안붙었으면 방문가능. 불이 먼저 붙은 곳은 가지 못함. 숫자가 낮다는 것은 먼저 도착했다는 의미
                visit[x][y] = visit[cur.x][cur.y] + 1;
                visitQ.add(new Point(x, y));
            }
        }

//        for (int[] ints : visit) {
//            for (int anInt : ints) {
//                System.out.print(anInt);
//            }
//            System.out.println();
//        }
        // 여기까지 왔다면 탈출하지 못한 것
        System.out.println("IMPOSSIBLE");

    }
}

아이디어

시간초과 해결

Scanner가 아닌 BufferedReader 사용
연결리스트는 시간초과!
아무래도 연결리스트가 add, remove 자체는 빠르지만, 커서로의 위치는 해당 인덱스의 위치로 이동(탐색)하는 시간이 O(n)만큼 걸리기 때문에 이 시간이 시간초과 원인인듯
스택을 이용
위치 이동이 필요 없이 pop, push가 O(1)이기 때문에 빠르게 처리 가능
두개의 스택을 이용
커서를 기준으로 왼쪽문자를 저장하는 스택, 오른쪽 문자를 저장하는 스택 2개를 만듦
커서의 위치는 왼쪽 스택의 마지막 위치
커서의 이동 : 왼쪽(오른쪽) 스택에서 오른쪽(왼쪽) 스택으로 pop해서 push로 이동시킴

어려운점 & 실수

연결리스트로 로직은 알겠는데 스택으로는 어떻게 처리하지?
해당 커서 위치를 기준으로 두 개의 스택을 가지고 구현해야하나?
커서를 기준으로
앞 text를 가진 스택 1 - left
뒤 text를 가진 스택 2 - right
두개의 스택을 가지고 빠르게 입력 출력을 진행해야 시간초과가 나지 않는다.

정답

import java.io.*;
import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

public class N1406 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        char[] charText = br.readLine().toCharArray();
        Stack<String> left = new Stack<>();
        Stack<String> right = new Stack<>();
        for (char c : charText) {
            left.push(String.valueOf(c));
        }
        int m = Integer.parseInt(br.readLine());
        String cmd;
        for (int i = 0; i < m; i++) {
            cmd = br.readLine();
            if (cmd.startsWith("P")) {
                left.push(cmd.substring(2));
            } else if (cmd.equals("L")) {
                if (!left.empty()) {
                    right.push(left.pop());
                }
            } else if (cmd.equals("D")) {
                if (!right.empty()) { // (커서가 문장의 맨 뒤이면 무시됨) //backText가 비어있으면 무시
                    left.push(right.pop());
                }
            } else if (cmd.equals("B")) {
                if (!left.empty()) {
                    left.pop();
                }
            }
        }
        StringBuilder sb = new StringBuilder();
        // left 스택의 모든 문자를 right 스택으로 모두 옮김
        while (!left.empty()) {
            right.push(left.pop());
        }
        // right 스택의 모든 문자를 꺼내서 문자열로 만듦
        while(!right.empty()) {
            bw.write(right.pop());
        }
        bw.flush();
        bw.close();
        br.close();
    }
}

아이디어

이터레이터(Iterator)의 개념을 알고있으면 쉽게 풀 수 있는 문제

중간값과 비교 -> X
위치랑 남은 size 비교 -> X
iterator로 위치값을 알아와서 덱의 size와 비교 -> O

어려운점 & 실수

else if (index > deque.size() / 2) { .. }
이 조건이 먼저나오느냐 후자에 나오느냐에 따라 달라짐 주의!! 반올림이 아니므로 계산하기

정답

import java.util.*;

public class N1021 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt(); // 1~N 까지 넣을 수 있는 덱
        int M = sc.nextInt(); //뽑으려는 숫자 갯수
        Deque<Integer> deque = new LinkedList<>();
        int count = 0;
        // 덱 초기화
        for (int i = 1; i <= N ; i++) {
            deque.add(i);
        }
        for (int i = 0; i < M; i++) {
            int num = sc.nextInt();
            while (true) {
//                if (deque.peekFirst() == num) {
//                    deque.pop();
//                    break;
//                }
                int index = 0; //몇번째 인덱스인지 찾기
                Iterator<Integer> it = deque.iterator(); //Iterator 타입으로 Integer로 지정해줘야 비교 가능
                while (it.hasNext()) {
                    if (it.next() == num)
                        break;
                    index++;
                }

                if (index == 0) {
                    deque.pop();
                    break;
                } else if (index > deque.size() / 2) { //이 조건이 먼저나오느냐 후자에 나오느냐에 따라 달라짐 주의!! 반올림이 아니므로 계산하기
                    deque.addFirst(deque.removeLast());
                    count++;
                } else {
                    deque.addLast(deque.removeFirst());
                    count++;
                }
            }
        }
        System.out.println(count);
    }
}

아이디어

결과를 ArrayList로 우선 저장.
앞의 숫자와 연속해서 나오면 continue하고, 다르면 add()
ArrayList를 배열로 변환해서 return

어려운점 & 실수

(ArrayList<>).toArray(new Integer[size]);
ArrayList를 배열로 바꿀 때, primitive 타입으로 변환할 수는 없음 (int X, Integer O)

정답

import java.util.*;

public class Solution {
    public Integer[] solution(int[] arr) {
        ArrayList<Integer> answer = new ArrayList<>();
        answer.add(arr[0]);
        int number = arr[0];
        
        for (int a : arr) {
            if (number == a) {
                continue;
            }
            answer.add(a);
            number = a;
        }

        return answer.toArray(new Integer[answer.size()]);

    }
}

아이디어

D(버리기) 를 커스텀해서 R(뒤집기) 상태 값을 함께 넘겨받아서
0(정상) 이면 front 값을 삭제
1(뒤집힌 상태) 이면 back 값을 삭제

어려운점 & 실수

출력 형태 자세히 볼 것!!! 공백없이 출력해야함
문제에서 요구하는 출력:
[1,2,3,5,8]
잘못된 출력:
[1, 2, 3, 5, 8] <= 공백이 들어가 있음
System.out.println(deque.toString().replace(" ", "")); 공백을 없애주도록 수정함
반례

입력 배열이 0인 경우에 대한 처리
→ 처리하지 않으면 [1,2,3] 를 파싱해서 덱에 넣을 때 에러남

정답

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Deque;
import java.util.LinkedList;

public class N5430 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        int testCase = Integer.parseInt(br.readLine());
        String[] command;
        for (int i = 0; i < testCase; i++) {
            command = br.readLine().split("");
            int size = Integer.parseInt(br.readLine());
            String array = br.readLine();
            // 배열이 0인경우에 대한 처리
            String[] numbers;
            if (size > 0) {
                array = array.substring(1, array.length() - 1);
                numbers = array.split(",");
            } else {
                numbers = new String[0];
            }
            // Deque에 저장해야함
            Deque<Integer> deque = new LinkedList<>();
            for (String number : numbers) {
                deque.add(Integer.parseInt(number));
            }
            excuteCommand(command, deque);
        }
    }

    private static void excuteCommand(String[] command, Deque<Integer> deque) {
        boolean isRocated = false;
        for (String cmd : command) {
//            System.out.println("isRocated : " + isRocated);
            if ("R".equals(cmd)) {
                isRocated = !isRocated; //반전
            } else if ("D".equals(cmd)) {
                if (!myD(deque, isRocated)) {
                    System.out.println("error");
                    return ;
                }
            }
        }
        // isRocated == true 라면 거꾸로 뒤집한 상태니깐 뒤에서부터 출력해야함
        if (!isRocated) {
            System.out.println(deque.toString().replace(" ", "")); //출력에 공백있으면 안됨 ㅠㅠ
            return ;
        } else {
            StringBuilder sb = new StringBuilder();
            String prefix = "";
            while (!deque.isEmpty()) {
                sb.append(prefix);
                prefix = ",";
                sb.append(deque.removeLast());
            }
            System.out.println("[" + sb + "]");
        }
    }

    private static boolean myD(Deque<Integer> deque, boolean isRocated) { //복사되는 deque이면,,,, 시간이 오래 걸릴듯
        // queue가 비어있으면 false 리턴
        if (deque.isEmpty()) return false;
        //isRocated == false 라면
        if (!isRocated) {
            deque.removeFirst();
        } else {
            deque.removeLast();
        }
        //isRocated == true 라면
        return true;
    }
}

아이디어

어려운점 & 실수

num % 2 == 0 이 아니면 당연히 1밖에 없지 않나?
else라고 하니깐 통과 못하는 테스트가 있어서 else if (num % 2 == 1) 로 바꿔주니깐 됐음

정답

class Solution {
    public int solution(int num) {
        int answer = 0;

        while (num != 1) {
            System.out.print(num + " ");
            if (num % 2 == 0) {
                num /= 2 ;
            } else if (num % 2 == 1) { //조건을 주지않고 else로만 하면 틀림
                num = (num * 3) + 1;
            }
            answer++;
            if (answer == 500) {
                return -1;
            }
        }
        return answer;
    }

}

20.10.15 [프로그래머스] 문자열 내 p와 y의 개수

문제

아이디어

어려운점 & 실수

String 비교

== : 주소값 비교
equals() : 값 비교

정답

class Solution {
    boolean solution(String s) {
        boolean answer = true;

        int numberOfP = 0;
        int numberOfY = 0;
        String[] array = s.split("");
        for (String ch : array) {
            System.out.println("ch : " + ch);
            if (ch.equals("p") || ch.equals("P")) {
                numberOfP++;
            }
            if (ch.equals("y") || ch.equals("Y")) {
                numberOfY++;
            }
        }
        System.out.println("P : " + numberOfP + ", Y : " + numberOfY);

        return numberOfP == numberOfY;
    }
}

아이디어

어려운점 & 실수

정답

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class N2164 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        Queue<Integer> queue = new LinkedList<>();
        for (int i = 1; i <= n; i++) {
            queue.offer(i);
        }
        while (queue.size() > 1) {
            queue.remove();
            queue.add(queue.poll());
        }
        System.out.println(queue.poll());
    }
}

아이디어

원형 연결 리스트를 사용하면 좋지 않을까 생각하는데, 그러면 직접 만들어야 하는지? → 그냥 연결리스트로 풀이 가능
index를 -1부터 시작해서 k만큼 인덱스위치를 더하고, 해당하는 위치의 값을 뽑아서 result(순열 결과 리스트)에 집어넣는다. 그리고 해당 인덱스의 값을 지우고, index값도 -1 해줌.
index가 리스트의 사이즈를 넘어가면 앞으로 돌아가서 거기서 부터 다시 계산.
리스트가 다 비워지면(size == 0) 탐색 종료

다른 풀이

next로 다음 사람 찾는 과정을 k번 해야함.
deque로 하면 좋을 것 같은데 연결리스트로도 가능할까? -> 연결리스트 가능. deque 가능

어려운점 & 실수

제거된 사람 위치를 0으로 하면 안됨 -> 그사람을 빼고 원을 만들어야 하기 때문
제거된 사람 위치를 연결리스트 remove로 하면 index로 접근 헀을 떄 달라짐. -> 지운 뒤, index를 -1 해주면됨

정답

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class N1158 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int k = sc.nextInt();
        List<Integer> numbers = new ArrayList<>();
        List<Integer> result = new ArrayList<>();
        for (int i = 1; i < n + 1; i++) {
            numbers.add(i);
        }
        int index = -1;
        while (true) {
            for (int i = 0; i < k; i++) {
                if (index + 1 >= numbers.size()) {
                    index = -1;
                }
                index++;
            }
            if (numbers.size() == 0) { // 더 이상 없으면 종료
                break;
            }
            int num = numbers.get(index);
            result.add(num); //해당하는 사람을 뽑아놓고
            numbers.remove(index); //연결리스트에서 제거
            index--; //제거 했으므로 인덱스도 -1 줄여준다.
        }
        StringBuilder sb = new StringBuilder();
        sb.append("<");
        for (Integer num : result) {
            sb.append(num + ", ");
        }
        System.out.println(sb.toString().substring(0, sb.length() - 2) + ">");
    }
}

20.10.27 [백준] 2504 괄호의 값

문제

아이디어

더하는 건지, 괄호 안에 있는 건지 구분 방법?
닫는 괄호가 나왔을 때, stack의 peek값이 숫자냐 여는 괄호냐에 따라 구분

어려운점 & 실수

정답

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

public class N2504 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String[] cmd = sc.nextLine().split("");
        Stack<String> st = new Stack<>();
        boolean isValid = true;

        for (int i = 0; i < cmd.length; i++) {
            // 여는 괄호일 경우 본인의 닫는 괄호를 스택에 저장한다.
            if (cmd[i].equals("(") ) {
                st.push(")");
                continue;
            }

            if (cmd[i].equals("[") ) {
                st.push("]");
                continue;
            }

            // 닫는 괄호인 경우
            int num = 0;
            while (true) {
                if (st.isEmpty()) { // 아직본인 괄호가 나오지 않았는데 스택이 비었다는 뜻 유효하지 않은 괄호 문자열
                    isValid = false;
                    break;
                }
                if (isNumeric(st.peek())) { // 스택에 담겨있는 숫자들은 다 더함
                    num += Integer.parseInt(st.pop());
                } else {
                    if (isVPS(cmd[i], st.peek())) {// 자신과 괄호 짝이 맞는지 확인
                        st.pop();
                        int tmp = (")".equals(cmd[i])) ? 2 : 3;

                        if (num == 0) {
                            st.push(String.valueOf(tmp));
                        } else {
                            st.push(String.valueOf(tmp * num));
                        }
                        break;
                    } else { // 괄호 쌍이 안맞으면 false
                        isValid = false;
                        break;
                    }
                }
            }
            if (!isValid) break; // 유효하지 않음이 판명되었으면 더이상 확인 하지 않음
        }

        int result = 0;
        while (!st.empty()) {
            if (isNumeric(st.peek())) {
                result += Integer.parseInt(st.pop());
            } else { // ( 나 ) 가 남아있으면 유효하지 않음
                isValid = false;
                break;
            }
        }

        if (isValid) System.out.println(result);
        else System.out.println(0);
    }

    static boolean isVPS(String cmd, String target) {
        return cmd.equals(target);
    }

    static boolean isNumeric(String str) {
        if (str.equals(")") || str.equals("]"))
            return false;
        return true;
    }
}

20.10.08 [백준] 4948 소수 - 베르트랑 공준

문제

20.10.08 - [백준] 2798 브루트포스

문제

핵심 풀이

어려운 점 & 실수

풀이

20.10.26 [백준] 10845 큐

문제

아이디어

원형 큐로 구현하지 않고, 최대 입력 수 만큼 큰 배열을 사용해서 구현함. (알고리즘을 위한 큐... 실제로 X)
head, tail의 시작은 0으로
원형 큐, 연결리스트로 다시 구현 해보기

어려운점 & 실수

정답

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

public class N10845 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        MyQueue queue = new MyQueue();
        int n = Integer.parseInt(br.readLine());
        String[] cmd;
        for (int i = 0; i < n; i++) {
            cmd = br.readLine().split(" ");
            switch (cmd[0]) {
                case "push" :
                    queue.push(Integer.parseInt(cmd[1]));
//                    System.out.println(cmd[1]);
                    break;
                case "front" :
                    System.out.println(queue.front());
                    break;
                case "back" :
                    System.out.println(queue.back());
                    break;
                case "size" :
                    System.out.println(queue.size());
                    break;
                case "empty" :
                    System.out.println(queue.empty() ? "1" : "0");
                    break;
                case "pop" :
                    System.out.println(queue.pop());
                    break;
            }
        }

    }

    static class MyQueue {
        // 원형 큐로 구현하지 않고, 최대 입력 수 만큼 큰 배열을 사용해서 구현함. (알고리즘을 위한 큐... 실제로 X)
        // head, tail의 시작은 0으로
        int[] queue = new int[1000005];
        int head, tail = 0;

        public void push(int x) {
            queue[tail++] = x;
        }

        public int pop() {
            if (empty()) {
                return -1;
            }
            return queue[head++]; //head값을 출력하고 위치를 이동
        }

        public int size() {
            return tail - head;
        }

        public boolean empty() {
            return tail == head;
        }

        public int front() {
            return empty() ? -1 : queue[head];
        }

        public int back() {
            return empty() ? -1 : queue[tail - 1];
        }
    }
}

20.10.17 [프로그래머스] 직사각형 별찍기

문제

아이디어

출력해야할 내용이 많아지면 BufferedWriter를 쓰는 것이 좋음. (시간 속도가 훨씬 빠르다.)

어려운점 & 실수

정답

import java.util.Scanner;

public class Solution {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int a = sc.nextInt();
        int b = sc.nextInt();
        
        printStar(a, b);
    }
    
    public static void printStar(int x, int y) {
        for(int i=0; i<y; i++) {
            for (int j=0; j<x; j++) {
                System.out.print("*");
            }
            System.out.println("");
        }
    }
}

20.10.20 [백준] 2480 주사위 세계

문제

아이디어

3수를 입력 받아 정렬하고,

마지막 수가 첫 수랑 같다면 -> 세 수가 같음 : (1, 2, 3)
마지막 수가 두번째 수랑 같다면 -> 두 수가 같음 : 1, (2, 3)
두번째 수가 첫 수랑 같다면 -> 두 수가 같음 : (1, 2), 3
모두 다른 경우 이므로 -> 마지막 수가 제일 큰 수 : 1, 2, 3

어려운점 & 실수

정답

import java.util.Arrays;
import java.util.Scanner;

public class N2480 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int[] numbers = Arrays.stream(sc.nextLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        Arrays.sort(numbers);
        int max = numbers[2];
        if (max == numbers[0]) {
            System.out.println(10000 + max * 1000);
            return ;
        }
        if (max == numbers[1]) {
            System.out.println(1000 + max * 100);
            return ;
        }
        max = numbers[1];
        if (max == numbers[0]) {
            System.out.println(1000 + max * 100);
            return ;
        }
        System.out.println(numbers[2] * 100);
        return ;
    }
}

20.10.20 [백준] 13300 방배정

문제

아이디어

남학생 방 배열1
여학생 방 배열2
각 인덱스 : 학년
해당 방에 들어가 최대인원이 된다면 방 수를 +1 하고 해당 방을 0으로 초기화

어려운점 & 실수

정답

import java.util.Scanner;

public class N1330 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int total = sc.nextInt();
        int max = sc.nextInt();
        int[] female = new int[7];
        int[] male = new int[7];
        int gender;
        int grade;
        int totalRoom = 0;
        for (int i = 0; i < total; i++) {
            gender = sc.nextInt();
            grade = sc.nextInt();
            if (gender == 0) { //성별에 따라 방에 배정
                female[grade]++;
                if (female[grade] == max) { // 방이 다 찬 경우 초기화(새로운 방)
                    totalRoom++;
                    female[grade] = 0;
                }
            } else {
                male[grade]++;
                if (male[grade] == max) {
                    totalRoom++;
                    male[grade] = 0;
                }
            }
        }
        // 최종 방 갯수 확인 : 빈방(값이 0인 곳)제외하고 count
        for (int i : male) {
            if (i != 0) {
                totalRoom++;
            }
        }
        for (int i : female) {
            if (i != 0) {
                totalRoom++;
            }
        }
        System.out.println(totalRoom);
    }
}

20.10.20 [백준] 1919 애너그램 만들기

문제

아이디어

첫 문자열을 char 배열에 저장 (아스키코드 값으로 a -> 0, b -> 1)
두번째 문자열을 char 배열로 만들어서 하나하나 해당 문자를 -1 씩 지워나감
최종적으로
지워야할 문자 수 : 첫 문자 배열에 남아있는 문자 갯수 + 두 번째 문자배열에 남아있는 문자 갯수
즉, alpha 양수 갯수 + alpha 음수의 절댓값 갯수

어려운점 & 실수

정답

import java.util.Scanner;

public class N1919 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        char[] first = sc.nextLine().toCharArray();
        char[] second = sc.nextLine().toCharArray();
        int[] alpha = new int[26];
        int total = 0;
        for (char c : first) { //첫 문자열의 알파벳 갯수 파악
            alpha[(int) c - 'a']++;
        }
        for (char c : second) { //해당하는 문자 -1
            alpha[(int) c - 'a']--;
        }
        for (int i : alpha) {
            if (i >= 0) {
                total += i;
            } else {
                total += i * -1;
            }
        }
        System.out.println(total);
    }
}

20.10.27 [백준] 4949 균형잡힌 세상

문제

아이디어

문자가 '(' 또는 '[' 이면 stack에 push
문자가 ')' 또는 ']' 인 경우,

스택이 비어있다면 → false
스택의 최근 값 (peek()) 이 다르다면 → false
모든 문자열이 끝나고, stack이 비어있지 않다면 (여는 괄호가 남아있는 경우) → false
위 3가지 경우가 아니라면 true
true 라면 쌍이 맞는 경우라고 판단

주의
stack이 비어있는지 먼저 확인해야함. 비어있는데 pop하면 런타임에러!!

어려운점 & 실수

정답

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

public class N4949 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        while (true) {
            Stack<Character> st = new Stack<>(); //매번 스택 초기화되어야되는 위치
            boolean isYes = true;
            char[] str = br.readLine().toCharArray();
            if (str.length == 1 && str[0] == '.') {
                break;
            }
            for (int i = 0; i < str.length; i++) {
                char ch = str[i];
                if (ch == '[' || ch == '(') {
                    st.push(ch);
                } else if (ch == ']' || ch == ')') {
                    // 스택이 비어있다면 no
                    if (st.empty()) {
                        isYes = false;
                        break;
                    }
//                    System.out.println("st.peek : " + st.peek() + ", ch : " + ch);
                    if ((ch == ']' && st.peek() == '[') || (ch == ')' && st.peek() == '(')) { //쌍이 맞는경우
                        st.pop();
                    } else { //ch 와 최상위 스택 괄호와 짝이 안맞으면 no
                        isYes = false;
                        break;
                    }
                }
            }
//            System.out.println("stack : " + st);
            // 스택에 괄호가 남아있다면 no
            if (!st.empty()) {
                isYes = false;
            }
            if (isYes) {
                sb.append("yes\n");
            } else {
                sb.append("no\n");
            }
        }
        System.out.println(sb);
    }
}

20.10.15 [프로그래머스] 모의고사

문제

아이디어

각 학생마다 찍기리스트(int answers)를 가지도록 하고, 객체가 현재 찍어야할 번호를 알기 위해 index값을 가지고 있도록 함.
찍기리스트의 사이즈보다 index가 넘어갈 경우 다시 index를 0으로 셋팅해서 찍도록 구현

어려운점 & 실수

정답

import java.util.*;

class Solution {
    public Integer[] solution(int[] answers) {
        ArrayList<Integer> answer = new ArrayList<>();
        int[] answerOfOne = {1, 2, 3, 4, 5};
        int[] answerOfTwo = {2, 1, 2, 3, 2, 4, 2, 5};
        int[] answerOfThree = {3, 3, 1, 1, 2, 2, 4, 4, 5, 5};
        int countOfOne = 0;
        int countOfTwo = 0;
        int countOfThree = 0;
        AnswerList one = new AnswerList(answerOfOne);
        AnswerList two = new AnswerList(answerOfTwo);
        AnswerList three = new AnswerList(answerOfThree);
        for (int n : answers) {
            if (one.isAnswer(n))
                countOfOne++;
            if (two.isAnswer(n))
                countOfTwo++;
            if (three.isAnswer(n))
                countOfThree++;
        }
        
        int max = countOfOne;
        answer.add(1);
        if (max == countOfTwo)
            answer.add(2);
        else if (max < countOfTwo) {
            answer.clear();
            answer.add(2);
            max = countOfTwo;
        }

        if (max == countOfThree)
            answer.add(3);
        else if (max < countOfThree) {
            answer.clear();
            answer.add(3);
        }

        return answer.toArray(new Integer[answer.size()]);
    }
    
    class AnswerList {
        int[] answers;
        int size;
        int index;
        
        public AnswerList(int[] answers) {
            this.answers = answers;
            size = answers.length;
            index = -1;
        }
        
        public boolean isAnswer(int answer) {
            index++;
            if (index >= size) {
                index = 0;
            }
            return (answers[index] == answer) ? true : false;
        }
        
    }
}

20.10.08 [백준] 2581 소수

문제

20.10.20 [백준] 11328 Strfry

문제

아이디어

첫번째 문자열의 각 자리별로 알파벳 배열에 해당하는 각 인덱스값을 +1
두번째 문자열의 각 자리별로 알파벳 배열을 확인
알파벳 해당 자리의 값이 0이면 바로 Impossible
모든 알파벳이 존재한 경우, 알파벳 배열에 남아있는 알파벳이 있다면 Impossible
그리고 마지막으로 둘 다 아니고, 모든 알파벳이 일치하면 possible

어려운점 & 실수

정답

import java.util.Scanner;

public class N11328 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int testCase = sc.nextInt();
        for (int i = 0; i < testCase; i++) {
            char[] first = sc.next().toCharArray();
            char[] second = sc.next().toCharArray();
            if (isPossible(first, second)) {
                System.out.println("Possible");
            } else {
                System.out.println("Impossible");
            }
        }
    }

    public static boolean isPossible(char[] first, char[] second) {
        if (first.length != second.length) {
            return false;
        }
        int[] alpha = new int[26];
        for (char c : first) {
            alpha[(int)c - 'a']++;
        }
        for (char c : second) {
            if (alpha[(int)c - 'a'] == 0) { //만드려는 문자가 부족한 경우
                return false;
            }
            alpha[(int)c - 'a']--;
        }
        for (int i : alpha) { //알파벳이 남아있는 경우
            if (i != 0) {
                return false;
            }
        }
        return true;
    }
}

20.10.20 [백준] 2752 세수정렬

문제

아이디어

stream으로 입력,출력
Arrays.sort로 정렬

어려운점 & 실수

정답

import java.util.Arrays;
import java.util.Scanner;

public class N2752 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int[] numbers = Arrays.stream(sc.nextLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        Arrays.sort(numbers);
        Arrays.stream(numbers).forEach(n -> System.out.print(n + " "));
    }
}

20.10.31 [백준] 1697 숨바꼭질

문제

아이디어

핵심 아이디어
수빈이가 X에 있다고 할 때 X-1, X+1, 2X로 이동하는 것을 BFS로 처리할 수 있다.

한 가지 더 고민해야 할 문제 - BFS의 범위를 어디까지로 해야할까요?

답변
0부터 100,000으로 하면 되는거 아닌가하고 쉽게 생각을 하셨을수도 있는데, 문제를 보시면 수빈이와 동생의 위치가 0에서 100,000 사이라고 했지 수빈이가 이동 중에 반드시 0에서 100,000 사이에만 있어야한다는 조건은 없습니다.(중요!!) 예를 들어 100,000 밖으로 나갔다가 다시 안으로 올 수도 있습니다. 그래서 이 부분을 고려할 필요가 있습니다.

상식적으로 생각했을 때 음수로 갈 일은 없을 것입니다. 그건 진짜 절대 가장 빠른 경로가 될 수 없기 때문입니다. 그리고 100,000 바깥으로 나갈 수 있겠지만 일단 한 번 나갔다면 그 이후로는 -1만 계속 할거에요. 그렇기 때문에 동생을 가장 빠르게 찾아나가는 상황에서는 아무리 멀리가도 200,000을 넘어가지는 않습니다.

이러한 생각을 거쳐서 0에서 200,000 사이에서만 BFS를 돌려도 답을 구하는데는 문제가 없음을 알 수 있게 되고, 여기서 더 깊게 생각을 해보면 사실 100,000을 나가는 것 자체가 손해라는 것을 알 수 있습니다. +1로 100,000을 탈출하는건 정말 바보짓이고, x2로 100,000을 탈출하는 상황이 있을 수 있겠다 싶지만, x2를 한 후 -1을 여러번 할 바에야 -1을 먼저 하고 x2를 하는게 더 낫기 때문입니다.

따라서 다음과 같이 큐에 들어갈 지점에 대한 조건을 추가함

if (next < 0 || next > 1000000) continue; //범위를 넘어가면 skip

어려운점 & 실수

1차 런타임에러 → 배열의 인덱스를 벗어나는 경우가 있는지 확인
처음 코드

static int[] disit = new int[1000002]; //이동거리

수정 코드

static int[] disit = new int[2000002]; //이동거리 - 2배 만큼 이동할 수 있는 거리를 잡아줌

정답

package dev.solar.baekjoon;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class N1697 {
    static int[] disit = new int[2000002]; //이동거리 - 2배 만큼 이동할 수 있는 거리를 잡아줌
    // 다음으로 이동할 위치는 -1, 1, 2x 이므로 로직 내에서 처리
    static int start;
    static int end;
    // 2차원 좌표가 아니므로 Point 클래스도 필요하지 않음

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        start = sc.nextInt();
        end = sc.nextInt();

        Queue<Integer> q = new LinkedList<>(); // 다음 이동할 지점 대기 큐
        Arrays.fill(disit, -1); // 이동거리 배열을 -1 로 초기화. 방문하지 않은 곳은 -1 임

        // 시작 지점 위치 지정
        disit[start] = 0;
        q.add(start);

        while (q.peek() != end) {
            int cur = q.poll(); //큐에서 다음 시작 위치를 가져옴
            for (int next : new int[]{cur - 1, cur + 1, cur * 2}) { // 이동할 수 있는 다음 위치를 bfs로 처리 - 다음 위치들 중에 bfs로 돌릴 대상들을 걸러야함
                if (next < 0 || next > 1000000) continue; //범위를 넘어가면 skip - 넘어가면 어짜피 가장 빠른 경로가 될 수 없다.
                if (disit[next] != -1) continue; // 이미 방문한 곳이면 skip
                disit[next] = disit[cur] + 1; //이동 거리 저장
                q.add(next); // 다음 시작 위치로 큐에 저장
            }
        }

        System.out.println(disit[end]);
    }
}

20.10.27 [백준] 4889 안정적인 문자열

문제

아이디어

'}' 인 경우
peek이 '{' 이면 -> pop 하고 넘어감
empty 이거나 '{'이 아니면 -> count + 1 하고, '{'로 바꿔서 push
'{' 인 경우
일단 다 push

cmd가 끝나고 스택에 '{' 가 남아있다면, size/2 만큰 count에 플러스한다. 스택에 남은 '{'의 반은 '}'로 바꿔주기 위해서)

어려운점 & 실수

정답

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

public class N4889 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        int n = 1;
        while (true) {
            String line = br.readLine();
            if (line.contains("-"))
                break;
            char[] cmd = line.toCharArray();
            Stack<Character> st = new Stack<>();
            int count = 0;
            for (int i = 0; i < cmd.length; i++) {
                if (cmd[i] == '}') {
                    if (st.empty() || st.peek() != '{') {
                        st.push('{');
                        count++;
                    } else {
                        st.pop();
                    }
                } else {
                    st.push('{');
                }
            }
            if (!st.empty()) {
                count += st.size() / 2;
            }
            sb.append(n + ". " + count + "\n");
            n++;
        }
        System.out.println(sb);
    }
}

20.10.08 [백준] 1929 소수 - 에라토스테네스의 체

문제

에라토스테네스의 체는

소수인지 판별하고자 하는 숫자들이 주어졌다면 일단 주어진 숫자들을 모두 나열하고 1을 제외한 모든 숫자를 소수라고 가정한다.
나열된 숫자들 중 소수이면서 가장 작은 숫자부터 시작해서 (자기 자신을 제외한) 그 숫자의 배수(소수가 아니므로)들을 지운다(소수가 아니라는 것을 저장한다고 봐도 된다).
1. 를 소수들만 남을 때까지 반복한다.

[백준] 참고

자주 틀리는 요인

20.10.19 [프로그래머스] SQL 3단계

문제 : 있었는데요 없었습니다
https://programmers.co.kr/learn/courses/30/lessons/59043

SELECT ins.ANIMAL_ID, ins.NAME from ANIMAL_INS ins join ANIMAL_OUTS outs on ins.animal_id = outs.animal_id where ins.datetime > outs.datetime order by ins.datetime;

20.10.27 [백준] 10799 쇠막대기

문제

아이디어

어려운점 & 실수

정답

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));
        char[] cmd = br.readLine().toCharArray();
        Stack<Character> st = new Stack<>();
        int count = 0;
        for (int i = 0; i < cmd.length; i++) {
            if (cmd[i] == '(') {
                // '(' 인경우와 '()'인 경우 구분
                if (cmd[i+1] == ')') { // 레이저인 경우
                    count += st.size();
                    i++;
                } else {
                    st.push('(');
                }
            } else if (cmd[i] == ')') {
                st.pop();
                count++;
            }

        }
        System.out.println(count);
        br.close();
    }
}

20.10.31 [백준] 2178 미로 탐색

문제

아이디어

dist 배열을 미리 -1로 초기화해두면 굳이 vis 배열을 따로 두지 않아도 방문 여부를 확인할 수 있게된다.
dist[0][0] = 0; ← 여기 거리를 0으로 측정하는 것 부터 시작하니깐 (0이 아니라) -1이 방문하지 않은 곳이 되는 것임
빨간색 칸 : 현재 보는 칸
검정색 : 추가되는 칸
현재 보고 있는 칸으로부터 추가되는 인접한 칸은 거리가 현재 보는 칸보다 1만큼 더 떨어져 있다.

어려운점 & 실수

내 코드 실행결과가 좀 오래 걸리는 것 같다. 다른 사람 풀이랑 비교해서 보완해야할 듯
최적화를 위해 배열 초기화를 Arrays.fill()을 이용함
2차원 배열 초기화는 행만큼 반복문을 돌아서 열을 채워줘야함

        for (int n = 0; n < N; n++) {
            Arrays.fill(disit[n], -1); //행은 지정해주고 열을 초기화해줘야함
        }

정답

package dev.solar.baekjoon;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class N2178 {
    static int[][] board;
    static int[][] disit; //거리계산
    static int[] dx = {1, 0, -1, 0};
    static int[] dy = {0, 1, 0, -1};
    static int N;
    static int M;

    static class Point {
        int x;
        int y;

        public Point(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine().trim(), " ");
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        board = new int[N][M];
        disit = new int[N][M];

        // board 입력 받기
        for (int n = 0; n < N; n++) {
            String arr[] = br.readLine().trim().split("");
            board[n] = Arrays.stream(arr).mapToInt(Integer::parseInt).toArray();
        }

        // visit 배열 방문 여부를 -1(방문안함)으로 초기화
        for (int n = 0; n < N; n++) {
            Arrays.fill(disit[n], -1);
        }

        // (0, 0) 좌표 부터 탐색 시작
        Queue<Point> q = new LinkedList<>();
        q.add(new Point(0, 0));
        disit[0][0] = 0; //시작 위치 거리를 0부터 시작

        while(!q.isEmpty()) {
            Point cur = q.poll();
            for (int dir = 0; dir < 4; dir++) {
                int x = cur.x + dx[dir];
                int y = cur.y + dy[dir];
                if (x < 0 || x >= N || y < 0 || y >= M) continue; //범위 밖이면 skip
                if (board[x][y] != 1 || disit[x][y] != -1) continue; //길이 아니거나 이미 방문한 경우 skip
                disit[x][y] = disit[cur.x][cur.y] + 1; //중심 좌표의 거리값에서 +1
                q.add(new Point(x, y));
            }
        }

        System.out.println(disit[N-1][M-1] + 1); //문제에서는 (0, 0)거리를 1부터 계산하기 때문에 마지막에 +1

    }
}