200 - 자료구조 1
스택 - 10828
나의 풀이
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();
int n = Integer.parseInt(br.readLine());// br.read() - 48
Stack<Integer> stack = new Stack<Integer>();
for (int i = 0; i < n; i++) {
String[] command = br.readLine().split(" ");
if (command[0].equals("push")) {
stack.push(Integer.parseInt(command[1]));
} else if (command[0].equals("pop")) {
sb = stack.empty() ? sb.append("-1\n") : sb.append(stack.pop() + "\n");
} else if (command[0].equals("size")) {
sb.append(stack.size() + "\n");
} else if (command[0].equals("empty")) {
sb = stack.empty() ? sb.append("1\n") : sb.append("0\n");
} else if (command[0].equals("top")) {
sb = stack.empty() ? sb.append("-1\n") : sb.append(stack.peek() + "\n");
}
}
System.out.println(sb.toString());
}
}자료구조 스택에 명령에 따른 if{}else{}로 처리를 해줌
단어 뒤집기 - 9093
나의 풀이
import java.io.BufferedReader;
import java.io.InputStreamReader;
public class Main {
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
StringBuilder temp = new StringBuilder();
int n = Integer.parseInt(br.readLine());
for (int i = 0; i < n; i++) {
String[] sentence = br.readLine().split(" ");
for (int j = 0; j < sentence.length; j++) {
temp.append(sentence[j]);
String convert = temp.reverse().toString();
sb.append(convert + " ");
temp.setLength(0);
}
sb.append("\n");
}
System.out.println(sb.toString());
}
}reverse() 메서드를 사용해서 풀었지만
카테고리와 같이 스택 자료구조로 푸는게 더 좋을 듯
괄호 - 9012
나의 풀이
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());
Stack<String> stack = new Stack<String> ();
StringBuilder sb = new StringBuilder();
for (int i = 0; i < n; i++) {
String[] pl = br.readLine().split("");
for (int j = 0; j < pl.length; j++) {
if (pl[j].equals("(")) {
stack.push("(");
}else if (pl[j].equals(")")) {
if (stack.empty()) {
stack.push("(");
break;
}
stack.pop();
}
}
sb = stack.empty() ? sb.append("YES\n") : sb.append("NO\n");
stack.clear();
}
System.out.println(sb.toString());
}
}스택을 이용해서 "(" -> push, ")" -> pop 해서 YES or NO 판별
스택 수열 - 1874
나의 풀이
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());
Stack<Integer> stack = new Stack<Integer>();
StringBuilder sb = new StringBuilder();
int[] arr = new int[n];
int m = 0;
for (int i = 0; i < arr.length; i++) {
arr[i] = Integer.parseInt(br.readLine());
}
for (int i = 1; i <= n; i++) {
stack.push(i);
sb.append("+\n");
while (!stack.empty() && stack.peek() == arr[m]) {
stack.pop();
sb.append("-\n");
m++;
}
}
if (stack.empty()) {
System.out.println(sb.toString());
}else {
System.out.println("NO");
}
}
}오름차순인 숫자를 담을 스택과 입력 받은 배열을 만들어서 판별
에디터 - 1406
나의 풀이
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[] str = br.readLine().split("");
int n = Integer.parseInt(br.readLine());
Stack<String> stack1 = new Stack<String>();
Stack<String> stack2 = new Stack<String>();
for (int i = 0; i < str.length; i++) {
stack1.push(str[i]);
}
for (int i = 0; i < n; i++) {
String[] command = br.readLine().split(" ");
if (command[0].equals("P")) {
stack1.push(command[1]);
} else if (command[0].equals("B") && !stack1.empty()) {
stack1.pop();
} else if (command[0].equals("L") && !stack1.empty()) {
stack2.push(stack1.pop());
} else if (command[0].equals("D") && !stack2.empty()) {
stack1.push(stack2.pop());
}
}
while (!stack1.empty()) {
stack2.push(stack1.pop());
}
while (!stack2.empty()) {
sb.append(stack2.pop());
}
System.out.println(sb.toString());
}
}
삽입 삭제가 빈번히 발생하는데 시간제한이 엄격하여 list로는 힘들고 시간복잡도 O(1)을 가지는 스택으로 구현해야 했다.(삽입, 삭제가 peek에서만 일어나므로)
큐 - 10845
나의 풀이
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
public class Main {
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
Queue<Integer> queue = new LinkedList<Integer>();
int n = Integer.parseInt(br.readLine());
int back = -1;
for (int i = 0; i < n; i++) {
String[] command = br.readLine().split(" ");
if (command[0].equals("push")) {
int input = Integer.parseInt(command[1]);
queue.add(input);
back = input;
}else if (command[0].equals("pop")) {
sb.append(queue.isEmpty() ? -1 : queue.poll()).append("\n");
}else if (command[0].equals("size")) {
sb.append(queue.size() + "\n");
}else if (command[0].equals("empty")) {
sb.append(queue.isEmpty()? 1: 0).append("\n");
}else if (command[0].equals("front")) {
sb.append(queue.isEmpty() ? -1 : queue.peek()).append("\n");
}else if (command[0].equals("back")) {
sb.append(queue.isEmpty() ? -1 : back).append("\n");
}
}
System.out.println(sb.toString());
}
}자료구조 큐에 명령에 따른 if{} else{}로 처리를 해줌
요세푸스 - 1158
나의 풀이
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
public class Main {
public static void main(String[] args) throws Exception{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder("<");
String[] str = br.readLine().split(" ");
int n = Integer.parseInt(str[0]);
int m = Integer.parseInt(str[1]);
Queue<Integer> queue = new LinkedList<Integer>();
for (int i = 0; i < n; i++) {
queue.add(i+1);
}
int cnt = 1;
while (queue.size() != 1) {
if (cnt == m) {
sb.append(queue.poll() + ", ");
cnt = 1;
}else {
queue.add(queue.poll());
cnt++;
}
}
sb.append(queue.poll() + ">");
System.out.println(sb.toString());
}
}
덱 - 10866
나의 풀이
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Deque;
import java.util.LinkedList;
public class Main {
public static void main(String[] args) throws Exception{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
Deque<Integer> deque = new LinkedList<Integer>();
int n = Integer.parseInt(br.readLine());
for (int i = 0; i < n; i++) {
String[] command = br.readLine().split(" ");
if (command[0].equals("push_back")) {
deque.addLast(Integer.parseInt(command[1]));
}else if (command[0].equals("push_front")) {
deque.addFirst(Integer.parseInt(command[1]));
}else if (command[0].equals("back")) {
sb.append(deque.isEmpty() ? -1 : deque.getLast()).append("\n");
}else if (command[0].equals("front")) {
sb.append(deque.isEmpty() ? -1 : deque.getFirst()).append("\n");
}else if (command[0].equals("pop_back")) {
sb.append(deque.isEmpty() ? -1 : deque.pollLast()).append("\n");
}else if (command[0].equals("pop_front")) {
sb.append(deque.isEmpty() ? -1 : deque.pollFirst()).append("\n");
}else if (command[0].equals("size")) {
sb.append(deque.size() + "\n");
}else if (command[0].equals("empty")) {
sb.append(deque.isEmpty() ? 1 : 0).append("\n");
}
}
System.out.println(sb.toString());
}
}
자료구조 덱에 명령에 따른 if{} else{}로 처리를 해줌
기본적인 자료구조 스택, 큐, 덱에 관련해서 문제를 풀어봤다.
아직은 알고리즘 기초라서 할만 한 것 같다.
hello world:)