코딩마스터스 (중급) 밑장빼기

 

- 문제설명
준하는 영화 타짜를 감명깊게 봤습니다. 영화에 나오는 손기술을 연습하던 준하는 카드더미에서 맨 윗장 뿐만이 아니라, 맨 아래에 있는 카드를 대신 내려놓는 기술을 쓸 수 있게 되었습니다!

1부터 N까지 수가 쓰여져 있는 N장의 카드 더미가 주어집니다. 이 카드 더미에서 맨 위 또는 맨 아래에 있는 카드를 내려놓는 것을 반복해서, 1부터 N까지 차례대로 내려놓을 수 있는지 알려주는 프로그램을 작성해 주세요.

 

- 입력 예
입력 #1
5
1 4 5 3 2

입력 #2
5
1 4 3 5 2

- 입력값 설명

• 첫째 줄에 N이 주어집니다. (1 ≤ N ≤ 1,000)
• 둘째 줄에, 카드 더미에 있는 카드에 쓰인 수가 순서대로 주어집니다. (1 ≤ 카드에 쓰인 수 ≤ N)

- 출력 예

출력 #1
YES

출력 #2
NO

- 출력값 설명
카드 더미에서 맨 위 또는 맨 아래에 있는 카드를 내려놓는 것을 반복해서, 1이 쓰여있는 카드부터 N이 쓰여 있는 카드까지 차례대로 내려놓을 수 있으면 YES, 그렇지 않으면 NO를 출력합니다.

 

 

- 풀이 과정

문제를 읽다보니 맨 앞, 맨 뒤를 자유롭게 빼낼 수 있는 데큐(자료구조)를 사용하면 되겠다고 생각했다.

 

데큐 

Double-Ended Queue의 줄임말로 입출력 방식에 따라 큐(Queue), 스텍(Stack)으로도 사용이 가능하다.

참고로,

Queue는 선입 선출 개념으로 순서대로 한쪽으로 들어오면 다른한쪽으로 나가는 구조이며

Stack은  후입 선출 개념으로 가장 나중에 들어온 데이터가 가장 먼저 나오는 구조로

Stack이란 뜻 그대로 박스가 위아래로 쌓여있다고 생각하면 된다.

import java.io.*;
import java.util.*; 

public class Main {
    public static void main(String[] args) throws IOException { 
        Scanner scanner = new Scanner(System.in); 
        Deque<Integer> deque = new LinkedList<>();
        int n = scanner.nextInt(); 
        
        for(int i = 0; i < n; i++){
            deque.add(scanner.nextInt());
        }
        
        int count = 1;
        while(!deque.isEmpty()){
            if (deque.peekFirst() == count){ #맨 앞
                deque.pollFirst();
                count++;
            } else if (deque.peekLast() == count){ #맨 뒤
                deque.pollLast();
                count++;
            } else {
                System.out.print("NO");
                return;
            }
        }
        System.out.print("YES");
        scanner.close();
    }
}

 

여기서 중요한 3가지 메소드이다.

1. addFirst, add(= addLast) : 데큐에 요소를 앞, 뒤로 입력할 수 있는 메소드
2. peekFirst, Last : 데큐에 들어와 있는 요소를 앞, 뒤로 확인만 하는 메소드
3. pollFirst, Last : 데큐에 있는 요소를 앞, 뒤로 빼내는 메소드

count로 1씩 세어나가면서 모두 완료되면 YES를, 아니면 NO를 출력했다.

 

Java를 사용하신 다른 스터디원분은 입력을 받아오시는 부분이 달랐다.

 Scanner scanner = new Scanner(System.in);
        
        int a = Integer.parseInt(scanner.nextLine());
        String b = scanner.nextLine();
        
        int[] cards = Arrays.stream(b.split(" ")).mapToInt(Integer::parseInt).toArray();

 

python은 리스트에 넣어 맨뒤와 맨앞을 확인하시고 맞는 부분을 지우는 방식을 사용하셨다.

while s[0] ==i or s[-1]==i:
		s.remove(i)