백준 1021번 회전하는 큐

문제

나의 풀이

import java.util.*;

public class Q1021 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        LinkedList<Integer> dq = new LinkedList<>();
        for(int i = 1; i <= n; i++) {
            dq.offer(i);
        }

        int m  = sc.nextInt();
        int arr[] = new int[m];
        for(int i = 0; i < m; i++) {
            arr[i] = sc.nextInt();
        }

        int count = 0;
        for(int i = 0; i < m; i++) {
            int target = dq.indexOf(arr[i]);
            int size = dq.size();
            int half = size % 2 == 0 ? size / 2 - 1 : size / 2;

            if(target <= half) { // 원소의 위치가 중간 위치 보다 앞에 있는 경우
                for(int j = 0; j < target; j++) {
                    dq.offerLast(dq.pollFirst()); // 2번 연산
                    count++;
                }
            } else { // 원소의 위치가 중간 위치 보다 뒤에 있는 경우
                for(int j = 0; j < size - target; j++) {
                    dq.offerFirst(dq.pollLast()); // 3번 연산
                    count++;
                }
            }
            dq.pollFirst(); // 원소 뽑아내기
        }

        System.out.println(count);
    }
}

2번 연산, 3번 연산을 보면 덱을 이용해야 하는 문제라는 것을 알 수 있다.
LinkedList를 이용해서 덱을 생성해주고, 1부터 입력 받은 n까지 요소를 덱에 추가시켜준다.
그런 다음 뽑아내려하는 수들을 arr 배열에 저장시켜준다.
뽑아내려는 수의 개수만큼 for문을 돌리면서 indexOf 메소드의 매개변수로 찾으려는 수를 넣어주고 덱에서 인덱스 위치를 찾는다. 그 위치를 target 변수에 넣어주고, 덱의 사이즈가 짝수인 경우는 사이즈에서 2를 나눈 수에 1를 빼준 수를 중간 위치로 half에 저장하고 홀수인 경우는 사이즈에서 2를 나눈 수를 중간 위치로 half에 저장한다.
만약 뽑아내려는 수의 위치가 중간 위치 보다 앞에 있는 경우는 2번 연산 으로 하는 게 더 최소한으로 할 수 있기 때문에 target 까지 2번 연산을 행하고 count를 증가시켜준다.
뽑아내려는 수의 위치가 중간 위치 보다 뒤에 있는 경우는 3번 연산 으로 하는 게 더 최소한으로 할 수 있기 때문에 덱의 사이즈에서 target을 뺀 횟수까지만 3번 연산을 행하고 count를 증가시켜준다.
이렇게 각각의 연산을 하고 나면 뽑아내려는 수를 뽑을 수 있기 때문에 pollFirst 메소드로 삭제시켜주며 반복한다.
마지막에는 count 값을 출력시켜주면 된다.

결과

백준 5430번 AC

문제

나의 풀이

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();
        StringBuilder sb = new StringBuilder();

        while(t-- > 0) {
            String p = sc.next();
            int n = sc.nextInt();
            StringTokenizer st = new StringTokenizer(sc.next(), "[],");
            LinkedList<Integer> dq = new LinkedList<>();
            for(int i = 0; i < n; i++) {
                dq.offer(Integer.parseInt(st.nextToken()));
            }
            
            boolean isRight = true;
            boolean isError = false;
            for(char c : p.toCharArray()) {
                if(c == 'R') {
                    isRight = !isRight;
                    continue;
                }

                if(isRight) {
                    if(dq.pollFirst() == null) {
                        sb.append("error\n");
                        isError = true;
                        break;
                    }
                } else {
                    if(dq.pollLast() == null) {
                        sb.append("error\n");
                        isError = true;
                        break;
                    }
                }
            }

            if(!isError) {
                sb.append("[");
                if(dq.size() > 0) {
                
                    if(isRight) { // 정방향일 경우
                        sb.append(dq.pollFirst());
                        while (!dq.isEmpty()) {
                            sb.append(",").append(dq.pollFirst());
                        }
                    } else {
                        sb.append(dq.pollLast());
                        while (!dq.isEmpty()) {
                            sb.append(",").append(dq.pollLast());
                        }
                    }
                
                }
                sb.append("]").append("\n");
            }
        }
        System.out.println(sb);
    }
}

테스트 케이스 개수 만큼 명령을 진행하는데 배열을 입력받을 때 StringTokenizer를 이용해서 두번째 매개변수에 [, ], , 을 구분자로 넣어서 이들을 제외하고 숫자들만 저장할 수 있도록 한다. 그렇게 원소들을 덱에 저장시켜준다.
그런 다음 isRight라는 정방향인지 아닌지에 대해 구분할 boolean 타입의 변수를 일단 정방향인 true로 초기화해준다. 명령에 대해서 for문을 돌려서 명령어가 뒤집어야되는 'R'인 경우 isRight를 현재 상태의 반대로 저장해주고 continue해준다.
나머지 로직은 이제 'D'인 경우일 텐데 정방향인 경우에는 pollFirst로 처음에 있는 원소를 뽑은 뒤 그 원소가 null이 아니라면 그냥 넘어가고 null인 경우에는 StringBuilder인 sb에 error문구를 추가해준다. 역방향인 경우에는 pollLast로 마지막원소를 봅은 뒤 그 원소가 null이 아니라면 그냥 넘어가고 null인 경우에는 마찬가지로 error 문구를 추가해준다.
그런 다음 이제 함수를 수행한 결과를 출력해주어야 한다. 이 경우에는 error문구가 출력되지 않았던 경우만 출력해주면 되기 때문에 if문에 isError가 아닌 경우의 조건을 달아준다. 그런 다음 덱의 사이즈가 0보다 큰 경우에만 원소의 내용을 정방향이면 pollFirst, 역방향이면 pollLast로 출력시킬 수 있도록 하고 0인 경우에는 []만 출력될 수 있도록 sb에 추가시켜준다.

결과

백준 3986번 좋은 단어

문제

나의 풀이

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        
        int count = 0;
        while(n-- > 0) {
            String s = sc.next();
            if(s.length() % 2 == 1) { // 문자열 길이가 홀수이면 짝이 맞지 않음
                continue;
            }
            Stack<Character> stack = new Stack<>();
            stack.push(s.charAt(0));
            for(int i = 1; i < s.length(); i++) {
                if(!stack.isEmpty() && stack.peek() == s.charAt(i)) {
                    stack.pop(); // 짝 제거하기
                } else {
                    stack.push(s.charAt(i));
                }
            }
            if(stack.isEmpty()) {
                count++;
            }
        }
        
        System.out.println(count);
    }
}

테스트 케이스만큼 수행하는데 입력 받은 문자열의 길이가 홀수이면 짝이 맞지 않으므로 continue해준다. 문자를 넣어가며 좋은 단어인지 확인해볼 스택을 생성해준다. 일단 문자열의 0번째 문자를 제일 먼저 스택에 push 해주고 1번째 문자부터 끝까지 for문을 돌려준다. 스택이 비어있지않으면서 스택의 최상단의 문자와 현재 i번째 문자가 일치하는 경우 짝이므로 stack에 있는 문자를 pop해준다. 그렇지 않은 경우는 짝이 아니므로 일단은 i번째 문자를 push해주어 짝을 기다린다.
문자열을 모두 검사하고 난 뒤 스택이 비어있다면 짝이 모두 알맞게 찾아진 좋은 단어라는 뜻이므로 count를 증가시킨다. 테스트케이스를 모두 수행하고 나서 count를 출력시켜주면된다.

결과