Java/Algorithms

문제 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이기 때문에 마저 스택에 수를 넣어주고 주어진 수열을 완성할 수 있는지 판단하면 된다. 즉, 스택에 값을 계속 넣어주면서 넣어준 값이 수열과 일치하는 경우 빼주면 된다. ..

문제 숫자를 입력 받아 0이 입력으로 들어오면 이전 숫자를 지우고 최종적으로 남아 있는 값들의 합을 구하라 접근 방식 스택에 입력값을 계속 push하면서 입력값이 0인 경우에만 저장하지 않고 가장 최근에 저장된 값을 pop 해준다. 합은 스택을 forEach문을 돌리거나 pop으로 꺼내면서 더해준다. 풀이 public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out..

문제 스택을 직접 구현해서 주어진 명령어에 맞게 실행 결과를 출력하라. 접근 방식 스택의 크기는 가변적으로 늘어나야 하기 때문에 Vector 혹은 ArrayList를 사용해서 구현해주면 된다. 풀이 private static class Stack { Vector vector = new Vector(); private void push(Integer x) { vector.add(x); } private int pop() { try { return vector.remove(vector.size() - 1); } catch (Exception e) { return -1; } } private int size() { return vector.size(); } private int empty() { return ..

문제 n명의 사람이 원을 그리며 앉아 있을 때 k번째 사람을 한 명씩 빼주는 문제로 리스트를 계속 돌아야 한다. 접근 방식 7명의 사람이 원을 그리며 앉아 있을 때 진행 과정은 아래와 같다. 1, 2, 3, 4, 5, 6, 7 1, 2, 4, 5, 6, 7 1, 2, 4, 5, 7 1, 4, 5, 7 1, 4, 5 1, 4 4 결과는 라는 순열이 만들어 진다. 결국 1부터 n번째 사람이 모두 빠질 때까지 반복문을 돌면서 빠지는 순서대로 출력 버퍼에 추가해주면 된다. 문제가 하나 있는데 리스트의 끝까지 왔다면 다시 처음으로 돌아가야 한다. 이터레이터는 전후 한 칸 이동만 가능하기 때문에 처음으로 갈 수가 없다. iterator = list.listIterator(); iterator = list.listI..

문제 키보드를 누른 기록이 저장된 키로거 문자열에서 화살표와 백스페이스를 계산해서 실제 비밀번호를 알아내는 문제 접근 방식 에디터에서 사용했던 방식처럼 이번에도 연결 리스트와 이터레이터를 사용하면 될거 같다. 어떤 부분에 글자가 추가되고 어떤 부분이 빠지는지 수정해서 최종 결과를 구한다. 풀이 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.parseIn..

문제 주어진 명령어에 맞게 텍스트를 수정하는 에디터를 구현하는 문제 접근 방식 임의 위치의 요소를 수정해야 하니 배열보다는 연결 리스트를 사용하는 것이 좋을 것 같다. 커서의 위치를 기록하여 데이터의 추가/삭제 명령어가 입력 되었을 때 해당 커서의 인덱스를 수정하도록 하면 될거 같다. 사실 스택으로도 풀 수 있는 문제지만 연결 리스트에 대해 학습 중이기 때문에 지금은 연결 리스트로 풀고 나중에 다시 스택으로 풀어보겠다. 풀이 우선 처음 답안을 제출하고 시간 초과로 실패한 코드를 살펴보겠다. public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(..

문제 서로 다른 양의 정수로 이루어진 수열에서 둘을 합해 주어진 자연수 X가 될 수 있는 경우의 수를 구하라 접근 방식 이전까지 풀어왔던 방식과 동일하게 배열에 각 숫자들이 등장 여부를 기록한 후에 현재 숫자와 합해서 X가 될 수 있는 숫자가 등장 했는지를 확인하고 등장 했다면 카운트를 1씩 증가시켜 준다. 배열을 사용할 땐 인덱스의 범위를 신경서야 하기 때문에 각 숫자의 범위를 생각하면서 풀면 쉽게 풀 수 있다. (1 ≤ number ≤ 1000000, 1 ≤ x ≤ 2000000) 풀이 public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(ne..