24797번:알파벳 블록(Java)

 

 

 양방향 queue(Deque)와 Stack을 이용해 풀었다.

명령어에 따라 맨 앞, 맨뒤에 문자를 추가해야 했으므로, 문자열은 Deque로 만들었다.

가장 나중에 추가된 문자를 제거해야 했으므로, Stack을 사용해 First In Last Out 방식을 사용했다.

마지막으로 추가된 문자가 맨 앞에 추가되었는지 맨뒤에 추가되었는지 두 가지의 값만 필요했기 때문에 Stack에 넣을 수 있는 자료형으로 Boolean을 택했다.

 

 

Scanner scanner = new Scanner(System.in);
Deque<Character> list = new LinkedList<>();//문자열
Stack<Boolean> history = new Stack<>();//마지막으로 넣은 문자가 앞에 넣은 문자인지 뒤에 넣은 문자인지 판별
int n = scanner.nextInt();//반복 횟수
int order;//명령
char c;//입력받을 문자

 

 

 

 

이제 n번만큼 반복하면서 명령을 입력받은 후 해야 할 것은 다음과 같다.

1. n이 1이라면: 문자를 입력받은 뒤 addLast()로 Deque의 맨 뒤에 추가하고 Stack에 false를 push()한다.

2. n이 2라면:  문자를 입력받은 뒤 addFirst()로 Deque의 맨 앞에 추가하고 Stack에 true를 push()한다.

3. n이 3이라면: Stack이 비어있지 않다면 pop()을 하고, pop()으로 나온 값이 true라면 pollFirst(), false라면 pollLast()를 하면 된다. 

 

 

 이걸 코드로 구현하면 다음과 같다.

for(int i = 0; i<n; i++)
{
    order = scanner.nextInt();
    switch (order)
    {
        case 1://맨 뒤에 추가
        {
            c = scanner.next().charAt(0);
            list.addLast(c);
            history.push(false);
            break;
        }
        case 2://맨 앞에 추가
        {
            c = scanner.next().charAt(0);
            list.addFirst(c);
            history.push(true);
            break;
        }
        case 3://마지막으로 넣은 문자 제거
        {
            if(!history.isEmpty())//넣은 기록이 있다면
            {
                if(history.pop())//마지막으로 넣은 문자의 위치가 맨앞이라면
                {
                    list.pollFirst();
                }
                else//마지막으로 넣은 문자의 위치가 맨뒤라면
                {
                    list.pollLast();
                }
            }
            break;
        }
    }
}

 

 

이제 Deque에 있는 남은 문자들을 순서대로 StringBuilder에 append()하고 출력하면 된다. 

StringBuilder result = new StringBuilder();
for(char i : list) {
    result.append(i);
}

System.out.println(result.length() == 0 ? "0" : result);

 

 

 

 

 

 

 

결과 코드

import java.util.*;

public class Main
{
    public static void main(String[] args)
    {
        Scanner scanner = new Scanner(System.in);
        Deque<Character> list = new LinkedList<>();//문자열
        Stack<Boolean> history = new Stack<>();//마지막으로 넣은 문자가 앞에 넣은 문자인지 뒤에 넣은 문자인지 판별
        int n = scanner.nextInt();//반복 횟수
        int order;//명령
        char c;//입력받을 문자

        for(int i = 0; i<n; i++)
        {
            order = scanner.nextInt();
            switch (order)
            {
                case 1://맨 뒤에 추가
                {
                    c = scanner.next().charAt(0);
                    list.addLast(c);
                    history.push(false);
                    break;
                }
                case 2://맨 앞에 추가
                {
                    c = scanner.next().charAt(0);
                    list.addFirst(c);
                    history.push(true);
                    break;
                }
                case 3://마지막으로 넣은 문자 제거
                {
                    if(!history.isEmpty())//넣은 기록이 있다면
                    {
                        if(history.pop())//마지막으로 넣은 문자의 위치가 맨앞이라면
                        {
                            list.pollFirst();
                        }
                        else//마지막으로 넣은 문자의 위치가 맨뒤라면
                        {
                            list.pollLast();
                        }
                    }
                    break;
                }
            }
        }

        StringBuilder result = new StringBuilder();
        for(char i : list) {
            result.append(i);
        }

        System.out.println(result.length() == 0 ? "0" : result);
    }
}