백준) 스택, 덱, 큐

백준 10828번 스택

---

내가 생각한 풀이

기본적인 스택을 알고있는지 확인하는 문제라고 생각한다. 제가 조금 해맷던 부분은 BufferedReader로 받는데 push 할때는 2개의 입력을 받아야된다. 이 부분에서 고민을 하다가 전체를 String으로 받고 push라는 단어가 포함된 String에서는 split를 사용하여 자른 문자를 배열로 따로 받았다. 

---

정확한 풀이

import java.io.*;
import java.util.*;
public class Baek10828 {

	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		Stack<Integer> stack = new Stack<>();
		
		int n = Integer.parseInt(br.readLine());
		int m = 0;
		String str = "";
		for(int i = 0; i < n; i++) {
			str = br.readLine();
		
			if(str.contains("push")) {
				String spt[] = str.split(" ");
				stack.push(Integer.parseInt(spt[1]));
			}
			else if(str.equals("top")) {
				if(stack.empty()) {
					System.out.println(-1);
				}
				else {
					System.out.println(stack.peek());
				}
			}
			else if(str.equals("size")) {
				System.out.println(stack.size());
			}
			else if(str.equals("empty")) {
				if(stack.empty()) {
					System.out.println(1);
				}
				else {
					System.out.println(0);
				}
			}
			else if(str.equals("pop")) {
				if(stack.empty()) {
					System.out.println(-1);
				}
				else {
					System.out.println(stack.pop());
				}	
			}
		}	
	}
}

---

백준 18258번 큐 2

---

내가 생각한 풀이

위에 문제와 비슷한 문제이다. Queue를 이용해서 풀려고 했는데 front와 back에 대한 처리를 고민하다가 Deque로 풀었습니다.

---

정확한 풀이

import java.io.*;
import java.util.*;
public class Baek18258 {
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		String str = "";
		Deque<Integer> que = new LinkedList<>();
		StringBuffer bf = new StringBuffer();
		for(int i = 0; i < n; i++) {
			str = br.readLine();
			if(str.contains("push")) {
				String spt[] = str.split(" ");
				int m = Integer.parseInt(spt[1]);
				que.offer(m);
			}
			else if(str.equals("front")) {
				if(que.isEmpty()) {
					bf.append("-1\\n");
				}
				else {
					bf.append(que.peek() + "\\n");
				}
			}
			else if(str.equals("pop")) {
				if(que.isEmpty()) {
					bf.append("-1\\n");
				}
				else {
					bf.append(que.poll() + "\\n");
				}
			}
			else if(str.equals("size")) {
				bf.append(que.size() + "\\n");
			}
			else if(str.equals("empty")) {
				if(que.isEmpty()) {
					bf.append("1\\n");
				}
				else {
					bf.append("0\\n");
				}
			}
			else if(str.equals("back")) {
				if(que.isEmpty()) {
					bf.append("-1\\n");
				}
				else {
					bf.append(que.getLast() + "\\n");
				}
			}
		}
		System.out.println(bf.toString());
	}
}

---

백준 10866번 덱

---

내가 생각한 풀이

위에 문제들과 같은 문제들로 Deque에 대한 기본 지식을 뭍는 문제이다.

---

정확한 풀이

import java.io.*;
import java.util.*;
public class Baek10866 {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuffer bf = new StringBuffer();
		int n = Integer.parseInt(br.readLine());
		Deque<Integer> que = new LinkedList<>();
		String str = "";
		
		for(int i = 0; i < n; i++) {
			str = br.readLine();
			if(str.contains("push_back")) {
				String[] spt = str.split(" ");
				int m = Integer.parseInt(spt[1]);
				que.offerLast(m);
			} 
			else if(str.contains("push_front")) {
				String[] spt = str.split(" ");
				int m = Integer.parseInt(spt[1]);
				que.offerFirst(m);
			}
			else if(str.equals("front")) {
				if(que.isEmpty()) {
					bf.append(-1 + "\\n");
				}
				else {
					bf.append(que.getFirst() + "\\n");
				}
			}
			else if(str.equals("back")) {
				if(que.isEmpty()) {
					bf.append("-1\\n");
				}
				else {
					bf.append(que.getLast() + "\\n");
				}
			}
			else if(str.equals("pop_front")) {
				if(que.isEmpty()) {
					bf.append("-1\\n");
				}
				else {
					bf.append(que.pollFirst() + "\\n");
				}
			}
			else if(str.equals("pop_back")) {
				if(que.isEmpty()) {
					bf.append("-1\\n");
				}
				else {
					bf.append(que.pollLast() + "\\n");
				}
			}
			else if(str.equals("empty")) {
				if(que.isEmpty()) {
					bf.append("1\\n");
				}
				else {
					bf.append("0\\n");
				}
			}
			else if(str.equals("size")) {
				bf.append(que.size() + "\\n");
			}
		}
		System.out.println(bf.toString());
	}

}

---

문제점

위에 문제들을 푸는데 시간을 시간을 많이 소비했다. 기본적인 것을 뭍는 문제이지만 if else 문에서 split에서만 str.contains를 사용해야된다. str.equals자리에 str.contains를 사용하면 이상한 답이 나온다.이유는 개발문서 폴더에 작성하겠습니다.

---

백준 9012번 괄호

---

내가 생각한 풀이

스택을 사용해서 푸는 문제이다. String을 문자로 변환해서 하나씩 비교하는데 ( 문자를 만나면 스택에 push하고 ) 문자를 만났을 때는 스택이 비어있는지 확인하고 비어있으면 push하고 빠져나온다. 비어있지 않으면 ( 문자이므로 pop을 합니다. for문이 끝났을 떄 스택이 비어있는지 확인하고 비어있으면 YES 비어있지 않으면 NO를 출력한다.

---

정확한 풀이

import java.io.*;
import java.util.*;
public class Baek9012 {
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		Stack<Character> stack = new Stack<>();
		for(int i = 0; i < n; i++) {
			String str = br.readLine();
			int len = str.length();
			for(int j = 0; j < len; j++) {
				char chr = str.charAt(j);
				if(chr == '(') {
					stack.push(chr);               
				}		
				else {
					if(stack.isEmpty()) {
						stack.push(chr);
						break;
					}
					else {
						stack.pop();
					}
				}				
			}
			if(stack.isEmpty()) {
				System.out.println("YES");
			}
			else {
				System.out.println("NO");
			}
			stack.clear();
		}	
	}
}

 문제점

위에 문제를 풀때 알고리즘 논리에는 문제가 없는것 같다고 생각했지만 답이 이상한 출력이 나왔습니다. 알고리즘적 문제인 줄 알고 계속 알고리즘을 수정할려고 노력했습니다. 하지만 문제는 for문이 끝나고 stack을 초기화 시켜줘야되는데 초기화를 시켜주지 않아서 계속 잘못된 답이 나왔습니다.

 

오늘의 회고

오늘은 어제 배운 알고리즘의 좀 더 쉬운 기본문제를 풀었습니다. 하지만 기본 문제임에도 불구하고 오랜 시간이 걸려 4문제 밖에 풀지 못했습니다. 생각지 못한 equals와 contains 문제와 stack초기화 문제 알고리즘 문제를 풀때에 고려해야될 사항이 많다는 것을 느끼고 있습니다. 알고리즘 문제를 풀기 전에는 왜 기업들에서 알고리즘 코딩테스트를 보는지 이해를 하지 못했습니다. 너무 많은 지원자들이 있어 수준 이하 지원자들을 걸러내는 이유도 있겠지만 코드를 짜면서 고려해야될 문제와 효율적으로 작성을 할 수 있다는 점에서 코딩테스트를 보는 것 같습니다. 내일은 책에 있는 문제를 풀겠습니다.