Java

문제 알파벳과 소괄호, 대괄호로만 이루어진 문자열이 주어졌을 때 괄호가 알맞게 짝을 이루는지 여부를 출력하라 접근 방식 스택을 사용해서 풀 수 있는 대표적인 문제로 여는 괄호만 항상 스택에 넣어주고 닫는 괄호를 만났을 때 스택의 최상위와 비교하여 짝이 맞는지 확인하면 된다. 중간에 하나라도 짝이 맞지 않는 경우에는 반복문을 종료하고 "no"를 출력해주면 된다. 풀이 public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringBuilder sb = new StringBuilder()..

문제 R(뒤집기)과 D(버리기) 함수가 있는 AC 언어를 이용하여 주어진 명령어대로 함수를 실행했을 때 결과를 반환해야 하며 배열에 있는 수가 없을 때는 D 함수를 실행하면 에러를 발생시켜야 한다. 접근 방식 여태까지 문제를 풀던 방식과는 다르게 입력이 배열로 들어와서 이걸 스캐너나 BufferedReader를 사용해서 어떻게 받아야 할지 몰라 시작부터 애를 먹었던 문제다... String input = "[1,2,3,4]"; // = br.readLine() String[] arr = input.substring(1, arrInput.length() - 1).split(","); 이런 식으로 서브스트링을 이용해 시작과 끝의 괄호를 없앤 후에 스플릿 함수를 이용하여 콤마 단위로 배열에 담아주었다. 이 문..

문제 n개의 원소를 가진 양방향 큐에서 아래와 같은 연산을 수행하여 주어진 순서대로 원소를 뽑을 때 2, 3번 연산의 최솟값을 구하라 첫 번째 원소를 뽑아낸다. 이 연산을 수행하면, 원래 큐의 원소가 a1,..., ak이었던 것이 a2, ..., ak와 같이 된다. 왼쪽으로 한 칸 이동시킨다. 이 연산을 수행하면, a1, ..., ak가 a2, ..., ak, a1이 된다. 오른쪽으로 한 칸 이동시킨다. 이 연산을 수행하면, a1, ..., ak가 ak, a1, ..., ak-1이 된다. 접근 방식 {1, 2, 3, 4, 5, 6, 7, 8, 9, 10} 위와 같은 값을 가진 큐가 주어졌을 때 {2, 9, 5} 순서대로 값을 뽑아내려면 2번과 3번 연산이 몇 번 필요한지 구해야 한다. 각각의 연산은 아래..

문제 스택, 큐 문제와 마찬가지로 덱을 구현하는 문제로 양 끝에서 모두 추가/삭제가 가능한 자료구조를 구현해야 한다. 접근 방식 이번에도 배열을 이용해서 구현할 것이기 때문에 배열의 크기를 지정해줘야 한다. 주어진 입력의 크기가 15라면 양쪽에서 최대 15개씩 총 30개의 값이 들어올 수가 있다. 그래서 배열의 크기는 주어진 입력의 크기 * 2 + 1을 해주면 충분하다. 기존 스택과 큐는 한쪽에서만 추가/삭제하는 메서드가 있었다면 메서드를 하나씩 추가해서 끝 부분에서도 추가/삭제가 가능하게 구현해 주면 된다. 풀이 public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new Buf..

문제 1부터 n까지의 숫자가 적힌 카드가 순서대로 가장 위에는 1로 시작해서 맨 밑에 n인 카드가 있을 때 아래와 같은 동작을 반복한다. 가장 위에 있는 카드를 뺀 후에 가장 위에 있는 카드를 카드의 가장 밑에 깔아 둔다. 이 과정을 반복하여 가장 마지막에 남는 카드를 구하라 접근 방식 가장 먼저 들어오는 1이 가장 먼저 나가는 구조니 큐를 사용하면 적당해 보인다. 가장 위에 카드를 빼고 하나를 더 빼야 하니 큐에서 두 개를 뺀 후 두 번째로 뺀 값을 다시 큐에 넣어준다. 이 과정을 큐의 크기가 1이 될 때까지 반복한다. 풀이 public class Main { public static void main(String[] args) throws IOException { BufferedReader br = ..

문제 Queue 자료구조를 직접 구현하는 문제로 push, pop, size, empty, front, back 메서드를 구현하면 된다. 참고로 18258번 큐2 문제와 같은 문제다. 접근 방식 스택처럼 push 할 때는 항상 맨 뒤에 넣는 것은 같지만 pop할 때는 가장 먼저 넣은 값을 꺼내줘야 한다. front와 back 메서드는 스택의 peek 메서드라고 볼 수 있다. 입력의 사이즈가 주어졌기 때문에 연결 리스트 보다는 배열을 이용해서 구현 하면 될거 같고 배열의 현재 front와 back 인덱스를 저장할 변수가 추가적으로 필요하다. front 인덱스는 pop을 할 때만 올라가야 하고 back 인덱스는 항상 배열의 끝에 값을 넣어줘야 하니 push 할 때마다 1씩 증가해야 한다. 풀이 public ..

문제 N개의 서로 높이가 다른 탑이 같은 수평선 상에 존재할 때 각 탑에서 발사한 레이저 신호를 어떤 탑에서 받는지를 알아내라 접근 방식 지문이 길어서 이해가 어려울 수도 있지만 발그림으로 그려보자면 아래 그림과 같다 높이가 낮은 탑은 자신보다 높은 가장 먼저 만나는 탑에 신호를 줄 수 있고 자신보다 높은 탑이 없다면 신호를 받는 탑이 존재하지 않는다. 높이가 4인 5번째 탑의 신호는 높이가 7인 4번째 탑이 받을 것이고 높이가 각각 5와 7인 3, 4번째 탑은 높이가 9인 2번째 탑이 받고 나머지 1, 2번째 탑의 신호는 받을 탑이 존재하지 않는다. 따라서 0 0 2 2 4가 정답이 된다. 첫 번째 탑부터 시작하면서 이전 탑들 중에 자신보다 높은 탑이 있는지 찾고 존재한다면 그 탑의 번호를 출력하면 되..

문제 1 ~ n까지의 수가 순서대로 들어올 때 정해진 수열을 스택을 사용해서 만들 수 있다면 연산 방법을 출력하고 불가능하다면 "NO"를 출력하라 접근 방식 입력을 담을 스택과 수열을 저장할 리스트 혹은 배열을 선언한다. 43687521 라는 수열이 주어진 경우 4가 먼저 나와야하니 4를 넣자마자 빼줘야한다. push(1); push(2); push(3); push(4); pop(); // 4 pop(); // 3 위와 같이 4까지 모두 넣어준 후에 4와 3을 빼주고 리스트에 넣어주면 43 수열이 완성된다. 다음으로 나와야 하는 수는 6이기 때문에 마저 스택에 수를 넣어주고 주어진 수열을 완성할 수 있는지 판단하면 된다. 즉, 스택에 값을 계속 넣어주면서 넣어준 값이 수열과 일치하는 경우 빼주면 된다. ..