200 - 자료구조1(연습)

---

단어뒤집기2 - 17413

나의 풀이

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

public class Main {

	static Stack<String> stack = new Stack<String>();
	static StringBuilder sb = new StringBuilder();
	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String[] str = br.readLine().split("");
		boolean check = false;
		for (int i = 0; i < str.length; i++) {
			if (str[i].equals("<")) {
				append();
				sb.append("<");
				check = true;
			} else if (str[i].equals(">")) {
				sb.append(">");
				check = false;
			} else if (check) {
				sb.append(str[i]);
			} else if (str[i].equals(" ")) {
				append();
				sb.append(" ");
			} else {
				stack.add(str[i]);
			}
		}
		append();
		System.out.println(sb.toString());
	}
	
	public static void append() {
		while (!stack.empty()) {
			sb.append(stack.pop());
		}
	}
}

이전 단어뒤집기에서는 스택으로 풀지 않았지만 이번에는 스택을 활용하여 해결

---

쇠막대기 - 10799

나의 풀이

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

public class 쇠막대기 {

	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		Stack<String> stack = new Stack<String>();
		String[] bar = br.readLine().split("");
		int answer = 0;
		for (int i = 0; i < bar.length; i++) {
			if (bar[i].equals("(")) {
				stack.add("(");
			}else if (bar[i].equals(")")) {
				stack.pop();
				if (bar[i-1].equals("(")) {
					answer += stack.size();
				}else {
					answer ++;
				}
			}
		}
		System.out.println(answer);
	}
}

"(" -> 스택에 삽입, ")" -> 스택에서 삭제
만약 ")" 전에 "("이면 레이저
만약 ")" 전에 ")"이면 막대

---

오큰수 - 17298

나의 풀이

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
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();
		Stack<Integer> stack1 = new Stack<Integer>();
		Stack<Integer> stack2 = new Stack<Integer>();
		int n = Integer.parseInt(br.readLine());
		List<Integer> list = new ArrayList<Integer>();
		String[] input = br.readLine().split(" ");
		for (int i = 0; i < n; i++) {
			stack1.add(Integer.parseInt(input[i]));
		}
		stack2.add(stack1.pop());
		list.add(-1);
		while(!stack1.empty()) {
			if (stack2.empty()) {
				stack2.add(stack1.pop());
				list.add(-1);
			}else if (stack1.peek() < stack2.peek()) {
				list.add(stack2.peek());
				stack2.add(stack1.pop());
			}else {
				stack2.pop();
			}
		}
		Collections.reverse(list);
		for (Integer val : list) {
			sb.append(val + " ");
		}
		System.out.println(sb.toString().trim());
	}
}

반복문으로 풀면 시간복잡도가 O(n2)이상 이므로 시간초과가 날 확률이 높다.
따라서 시간복잡도 O(n)인 스택으로 해결함

---

오등큰수 - 17299

나의 풀이

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
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());
		Stack<Integer> stack1 = new Stack<Integer>();
		Stack<Integer> stack2 = new Stack<Integer>();
		List<Integer> list = new ArrayList<Integer>();
		String[] str = br.readLine().split(" ");
		int[] arr = new int[1000001];
		for (int i = 0; i < str.length; i++) {
			arr[Integer.parseInt(str[i])]++;
		}
		for (int i = 0; i < n; i++) {
			stack1.add(Integer.parseInt(str[i]));
		}
		stack2.add(stack1.pop());
		list.add(-1);
		while (!stack1.empty()) {
			if (stack2.empty()) {
				stack2.add(stack1.pop());
				list.add(-1);
			}else if (arr[stack1.peek()] < arr[stack2.peek()]) {
				list.add(stack2.peek());
				stack2.add(stack1.pop());
			}else {
				stack2.pop();
			}
		}
		Collections.reverse(list);
		for (Integer val : list) {
			sb.append(val + " ");
		}
		System.out.println(sb.toString().trim());
	}
}

이전 문제와 동일하고 추가된 부분은 빈도수 배열을 만들어서 그 값으로 비교하여 해결, 최대로 나올 수 있는 값이 1,000,000이므로 배열 생성시 주의

---

개인적으로 스택이라는 카테고리를 몰랐다면, 많이 해맸을 문제들인것 같다.
문제 해결 방법을 생각하기 부터 시간초과 까지 스택을 사용하므로써 잘 해결 한 것 같다.