백준 10866번: 덱

코드: https://github.com/kgh128/Problem-Solving/blob/main/src/Baekjoon/p10866.java

1. Deque 클래스 구현

멤버 변수는 실제 정수를 저장할 int 배열 deque와 큐의 가장 앞에 있는 정수의 인덱스를 가리키는 frontIndex, 큐의 가장 뒤에 있는 정수의 인덱스를 가리키는 backIndex이다. 멤버 함수는 생성자 Deque(), 주어진 명령을 처리할 pushFront(), pushBack() popFront(), popBack() size(), empty(), front(), back()이다.

명령의 수는 최대 10,000개이므로 큐에 저장되는 정수의 개수도 최대 10,000개이다. 단, push_front 명령이 10,000번 나오는 경우는 배열의 왼쪽으로 10,000개의 공간이 필요하고, push_back 명령이 10,000번 나오는 경우는 배열의 오른쪽으로 10,000개의 공간이 필요하다. 따라서 Deque()에서 deque의 크기가 20,000개가 되도록 초기화한다.

또한 frontIndex는 10,000으로, backIndex는 9,999로 초기화한다. backIndex < frontIndex이므로 배열이 처음에는 비어있음을 표현할 수 있다. 그리고 이렇게 초기화하면 push_front 명령이 10,000번 나왔을 때 frontIndex의 값이 0이 되고, push_back 명령이 10,000번 나왔을 때 backIndex의 값이 19,999이 된다.

frontIndex와 backIndex의 값은 다음과 같이 바뀐다.

• pushFront(): --frontIndex (앞으로 한 칸 이동)
• popFront(): frontIndex++ (뒤로 한 칸 이동)
• pushBack(): ++backIndex (뒤로 한 칸 이동)
• popBack(): backIndex-- (앞으로 한 칸 이동)

deque안에 정수가 1개 있으면 frontIndex와 backIndex는 같아진다. 이 상태에서 popFront()이 호출되면 deque가 비워지고, frontIndex는 +1이 되어 backIndex < frontIndex이 된다. 또는 popBack()이 호출되어도 deque가 비워지고, backIndex가 -1이 되어 backIndex < frontIndex이 된다. 이것이 empty()에서 쓰이는 deque가 빈 상태인지 확인하는 조건이다.

size()에서 deque에 저장된 정수의 개수를 계산하는 수식은 backIndex - frontIndex + 1이다. deque가 비어있을 때의 frontIndex와 backIndex의 관계를 정확히 표현하면 frontIndex = backIndex + 1이다. 위의 수식에 이 관계식을 집어넣으면 0이 나오므로 deque가 비어있을 때도 해당 수식을 적용할 수 있다.

2. 명령 처리

String[] command = br.readLine().split(" ");

위의 코드로 명령을 입력받는다. command[0]이 명령의 키워드(push_front, push_back, pop_front, pop_back, size, empty, front, back)이므로 command[0]과 일치하는 명령의 키워드를 찾는다. (if (command[0].equals("push_front")) 형식)

• push_front, push_back 명령은 덱에 넣을 정수가 command[1]로 존재한다. String인 command[1]을 정수로 바꾸고 deque.pushFront(x) 또는 deque.pushBack(x)을 호출하여 처리한다.

• 나머지 명령은 command[1]이 존재하지 않으므로 Deque 클래스의 객체인 deque를 통해 명령에 맞는 메소드를 호출하여 처리한다.