10866번(덱), 9012번(스택), 1764번

10866번

 

덱의 기본 개념을 묻는 문제이다

 

여기서 주의해야할 점은 어제와 풀었던 문제와 마찬가지로 명령어를 push_back X와 push_front X인 문자열로 받았을 때 이를 공백을 기준으로 문자열과 숫자로 분리시켜야 한다는 것이다

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Deque;


public class Practice {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        StringBuilder sb = new StringBuilder();
        Deque<Integer> deque = new ArrayDeque<>();
        for (int i = 0; i < n; i++) {
            String str = br.readLine();
            if (str.startsWith("push_front")) {
                String[] part = str.split(" "); // 공백을 기준으로 문자열을 나눠 뒷부분을 문자열에서 정수로 변환
                int m = Integer.parseInt(part[part.length - 1]);
                deque.offerFirst(m);
            } else if (str.startsWith("push_back")) {
                String[] part = str.split(" "); // 공백을 기준으로 문자열을 나눠 뒷부분을 문자열에서 정수로 변환
                int m = Integer.parseInt(part[part.length - 1]);
                deque.offerLast(m);
            } else if (str.equals("front")) {
                if (deque.isEmpty()) {
                    sb.append(-1).append("\n");
                } else {
                    sb.append(deque.peekFirst()).append("\n");
                }
            } else if (str.equals("back")) {
                if (deque.isEmpty()) {
                    sb.append(-1).append("\n");
                } else {
                    sb.append(deque.peekLast()).append("\n");
                }
            } else if (str.equals("size")) {
                sb.append(deque.size()).append("\n");
            } else if (str.equals("empty")) {
                if (deque.isEmpty()) {
                    sb.append(1).append("\n");
                } else {
                    sb.append(0).append("\n");
                }
            } else if (str.startsWith("pop_front")) {
                if (deque.isEmpty()) {
                    sb.append(-1).append("\n");
                } else {
                    sb.append(deque.pollFirst()).append("\n");
                }
            } else if (str.startsWith("pop_back")) {
                if (deque.isEmpty()) {
                    sb.append(-1).append("\n");
                } else {
                    sb.append(deque.pollLast()).append("\n");
                }
            }
        }
        System.out.println(sb);
    }
}

 

 

해당 문제를 통해 알 수 있는 것은 덱의 경우 양방향으로 데이터를 추가하고 삭제할 수 있다는 것이다

 

9012번

 

스택의 기본 개념을 활용한 문제이다

 

 

괄호들을 한 줄의 문자열로 받은 뒤 이를 쪼개서 괄호 하나씩 들어가는 char 배열로 만들어준다

for문을 돌면서 배열 내 괄호들을 하나씩 확인하며 '('가 포함될 경우 해당 괄호를 스택에 넣어준다

만약 배열 내 괄호가 ')'일 경우 스택의 데이터를 하나씩 제거한다

 

여기서 가장 주의해야 할 점은 스택이 비었는데 괄호가 ')'인 경우 제거할 데이터가 없다는 것이다

이런 경우 괄호의 짝이 절대로 맞을 수 없기 때문에 괄호의 개수와 위치가 적절한지 판단하기 위한 boolean형 변수를 false로 초기화하고 for문을 종료한다

 

결과적으로 스택이 비어있을 경우 괄호의 짝이 맞아 올바른 괄호 문자열이 될 수 있어 yes를 출력하고 스택이 비어있지 않거나 boolean형 변수가 false인 경우 올바른 문자열이 될 수 없으므로 no를 출력한다

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Practice {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int num = Integer.parseInt(br.readLine());
        for (int i = 0; i < num; i++) {
            char [] ch = br.readLine().toCharArray();
            Stack<Character> stack = new Stack<>();
            boolean tf = true;
            for (int j = 0; j <ch.length; j++) {
                if (ch[j] == '(') {
                    stack.push('(');
                } else if (ch[j] ==')') {
                    if(!stack.empty()) {
                        stack.pop(); // stack에 여는 괄호가 존재한다면 stack의 값을 pop
                    } else {
                        tf = false; // 여는 괄호가 없는데 닫힌 괄호가 나왔으면 false, 반복문 종료
                        break;
                    }
                }
            }
            if(!stack.empty() || tf== false) {
                System.out.println("NO");
            } else {
                System.out.println("YES");
            }
        }
    }
}

 

boolean을 사용하지 않고 만약 괄호 ')'가 들어왔을 때 스택이 비어있다면 pop()을 할 수 없으므로 char 타입의 임의 문자를 스택에 넣어줘도 된다. 이러면 올바른 괄호 문자열이 아닐 경우 무조건 스택에 문자가 남아있게 된다

 

for (int j = 0; j <ch.length; j++) {
    if (ch[j] == '(') {
        stack.push('(');
    } else if (ch[j] ==')') {
        if(!stack.empty()) {
            stack.pop();
        } else {
            stack.push('X');
            break;
        }
    }
}

 

1764번

 

교집합과 정렬을 활용한 문제이다

 

 

Set을 사용하여 데이터를 입력 받았다

듣도 못한 사람의 명단을 set1으로 보도 못한 사람을 set2로 넣고 set2가 set1의 요소들을 포함하고 있는지 여부를 확인하여 듣보잡의 수를 구하고 양쪽에 포함되는 사람을 list에 넣어 오름차순으로 정렬하였다

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;


public class Practice {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine()," ");
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        Set<String> set1 = new HashSet<>();
        Set<String> set2 = new HashSet<>();
        StringBuilder sb = new StringBuilder();
        for(int i = 0; i<n; i++) {
            set1.add(br.readLine());
        }
        for(int i = 0; i<m; i++) {
            set2.add(br.readLine());
        }
        int count = 0;
        List <String> list = new ArrayList<>();
        for(String str : set1) {
            if(set2.contains(str)) {
                count++;
                list.add(str);
            }
        }
        sb.append(count+"\n");
        Collections.sort(list);
        for(String str : list) {
            sb.append(str+"\n");
        }
        System.out.println(sb);
    }
}

 

굳이 set을 2개씩 만들 필요가 있는지 생각이 들어 다른 풀이를 생각해보았다

set을 하나만 만들어 여기에 듣도 못한 사람을 넣고 입력 받은 보도 못한 사람이 그 set에 들어있는지를 확인하며 들어있다면 겹치는 개수 count를 세고 list에 담아줬다. 이후 과정은 위와 동일

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;


public class Practice {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine()," ");
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        Set<String> set = new HashSet<>();
        StringBuilder sb = new StringBuilder();
        List <String> list = new ArrayList<>();
        for(int i = 0; i<n; i++) {
            set.add(br.readLine());
        }
        int count = 0;
        for(int i = 0; i<m; i++) {
            String name = br.readLine();
            if(set.contains(name)) {
                count++;
                list.add(name);
            }
        }

        sb.append(count+"\n");
        Collections.sort(list);
        for(String str : list) {
            sb.append(str+"\n");
        }
        System.out.println(sb);
    }
}