Java/Algorithms

문제 주어진 쇠막대기들에 레이저를 발사했을 때 쇠막대기가 총 몇 개로 나뉘는지 계산하는 문제 접근 방식 풀고 나니 엄청 간단했지만 풀이법을 알기까지 많은 시간이 걸린 문제로 코드를 보면 알겠지만 엄청 간단한 문제다. ()(((()())(())()))(()) 위와 같은 문자열이 주어졌을 때 괄호가 열리자마자 닫히면 레이저고 그렇지 않다면 쇠막대기라는 것을 알 수 있다. 쇠막대기의 양끝과 레이저는 겹치지 않기 때문에 쇠막대기 위에 레이저가 발사되면 무조건 쇠막대기가 잘라진다. 즉 레이저를 쐈을 때 현재 스택에 있는 쇠막대기의 수만큼 쇠막대기가 늘어나기 때문에 열리자마자 닫히는 괄호를 발견했을 때마다 스택의 사이즈만큼 더해주면 된다. 주의해야 할 점은 쇠막대기가 끝날 때도 1씩 더해줘야 하는데 길이가 3인 쇠..

문제 A와 B로만 이루어진 문자열이 주어졌을 때 같은 글자끼리 선을 그어 교차하지 않고 모두 맞아떨어지는 경우 주어진 문자열을 좋은 단어라고 판단하고 좋은 단어가 몇개인지 출력하는 문제 접근 방식 좋은 단어에 대한 설명이 헷갈릴 수 있는데 아래와 같다. AABB (O) ABBA (O) ABAB (X) 알 수 있는 사실은 연속해서 존재하거나 중간에 다른 단어의 선과 겹치면 안 된다는 건데 같은 경우 빼주고 같지 않은 경우는 넣어주면 되므로 스택을 사용하면 쉽게 풀 수 있다. ABBA 같은 경우만 신경 써서 풀면 되는 문제로 아래와 같은 순서로 실행되는 코드를 짜면 된다. Stack stack = new Stack(); // ABBA stack.push('A');// stack(A) peek() == 'B'..

문제 알파벳과 소괄호, 대괄호로만 이루어진 문자열이 주어졌을 때 괄호가 알맞게 짝을 이루는지 여부를 출력하라 접근 방식 스택을 사용해서 풀 수 있는 대표적인 문제로 여는 괄호만 항상 스택에 넣어주고 닫는 괄호를 만났을 때 스택의 최상위와 비교하여 짝이 맞는지 확인하면 된다. 중간에 하나라도 짝이 맞지 않는 경우에는 반복문을 종료하고 "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 ..