백준(10866, 9012, 1764)

문제 10866번(성공)

소스코드

import java.io.*;
import java.util.*;
public class boj10866 {
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        Deque deque = new ArrayDeque();
        int n = Integer.parseInt(br.readLine());
        int cnt = 0;
        while(cnt <n){
            String[] input = br.readLine().split(" ");
            String name =input[0];
            int num = 0;
            if(input.length >1){
                num = Integer.parseInt(input[1]);
            }
            if(name.equals("push_front")){
                deque.addFirst(num);
            }else if(name.equals("push_back")){
                deque.addLast(num);
            }else if(name.equals("pop_front")){
                if(deque.isEmpty()){
                    sb.append(-1 + "\n");
                }else{
                    sb.append(deque.pollFirst() +"\n");
                }
            }else if(name.equals("pop_back")){
                if(deque.isEmpty()){
                    sb.append(-1 + "\n");
                }else{
                    sb.append(deque.pollLast() +"\n");
                }
            }else if(name.equals("size")){
                sb.append(deque.size() + "\n");
            }else if(name.equals("empty")){
                if(deque.isEmpty()){
                    sb.append(1 +"\n");
                }else{
                    sb.append(0 + "\n");
                }
            }else if(name.equals("front")){
                if(deque.isEmpty()){
                    sb.append(-1 +"\n");
                }else{
                    sb.append(deque.peek() +"\n");
                }
            }else if(name.equals("back")){
                if(deque.isEmpty()){
                    sb.append(-1 +"\n");
                }else{
                    sb.append(deque.peekLast() + "\n");
                }
            }
            cnt++;
        }
        System.out.println(sb);
    }
}

풀이 접근

1. 양방향 입출 구조를 가지고 있는 Deque 선형 자료구조에 대해 이해한다.
2. int 인덱스까지 같이 입력 받는 경우를 예외처리한다.
3. 실행의 결과를 출력한다.

문제 핵심

• Deque 자료구조에 대한 이해

문제 9012번 (성공)

소스코드

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

풀이 접근

1. 해당 문제를 해결하기 위해 Stack 선형 자료구조를 떠올렸다.
2. 입력에서 '('와 ')'만 들어오기 때문에,Character형 stack을 만든다.
3. stack공간이 비어있을 때 ')'가 들어온 경우에는 No가 출력되어야 함으로, 해당 값을 push해 준 후 break시켜준다.
4. stack이 비어있지 않는 경우에는 Yes, 반대의 경우에는 NO 를 출력한다.

문제 핵심

• 해당 문제를 풀기 위해 자료구조를 사용할 수 있는가?
• 예외처리를 생각하고 문제를 풀었는가

문제 1764번 (실패, 시간초과)

소스코드

import java.io.*;
import java.util.*;
public class boj1764 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st = new StringTokenizer(br.readLine());
        HashSet<String> arr1 = new HashSet<>();
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        for (int i = 0; i < n; i++) {
            arr1.add(br.readLine());
        }
        ArrayList<String> arr2 = new ArrayList<>();
        for (int i = 0; i < m; i++) {
            String input = br.readLine();
            if(arr1.contains(input)){
                arr2.add(input);
            }
        }
        Collections.sort(arr2);
        System.out.println(arr2.size());
        for (int i = 0; i < arr2.size(); i++) {
            System.out.println(arr2.get(i));
        }
    }
}

실패한 경우의 풀이 접근

1. n명의 경우의 수를 ArrayList로 받는다
2. 문제의 조건에 따라 sort함수로 정렬해 준다.
3. m명의 이름을 받으면서 ArrayList에 해당 이름이 있는지 contains로 확인하여 출력한다.

수정한 경우의 풀이 접근

1. 시간 복잡도를 최대한 줄일 수 있는 HashSet을 사용한다.
2. ArrayList로 결과 값을 담을 리스트를 생성하여, m번의 입력을 받을 때 contains 메소드로 조건에 부합한 경우만 add한다.
3. 문제의 조건에 맞게 sort함수를 사용한다.
4. 출력한다.

문제 핵심

• 시간복잡도를 줄일 수 있는가?
• 문제를 해결할 수 있는 다양한 방법들을 떠올릴 수 있는가?