[해커랭크(HackerRank) JAVA 풀이] - Java Dequeue

해커랭크 - https://www.hackerrank.com/
Prepare > Java > Data Structures > Java Dequeue

HackerRank

 

컴퓨터 과학에서 양방향 큐(dequeue, 종종 deque로 약칭됨, Deck로 발음됨)는 큐를 일반화하는 추상 데이터 유형으로, 이 큐에 대해 앞(머리) 또는 뒤(꼬리)에 요소를 추가하거나 제거할 수 있습니다. ).

Deque 인터페이스는 LinkedList 또는 ArrayDeque 클래스와 같은 다양한 유형의 컬렉션을 사용하여 구현할 수 있습니다. 예를 들어 deque는 다음과 같이 선언할 수 있습니다.

Deque deque = new LinkedList<>();
or
Deque deque = new ArrayDeque<>();

Deque에 대한 자세한 내용은 여기에서 확인할 수 있습니다.

이 문제에서는 N개의 정수가 제공됩니다. 크기가 M인 모든 가능한 연속 하위 배열 중에서 고유한 정수의 최대 수를 찾아야 합니다.

참고: 이 문제의 제한 시간은 3초입니다.

 

Input Format

입력의 첫 번째 줄에는 정수의 총 수와 하위 배열의 크기를 나타내는 두 개의 정수 N과 M이 있습니다. 다음 줄은 N개의 공백으로 구분된 정수를 포함합니다.

 

Constraints

• 1 ≤ N ≤ 100000
• 1 ≤ M ≤ 100000
• M ≤ N

배열의 숫자 범위는 [0, 10000000]입니다.

 

Output Format

크기가 M인 모든 가능한 연속 부분배열 중에서 고유한 정수의 최대 개수를 출력합니다.

 

 

Sample Input

6 3
5 3 5 2 3 2

 

Sample Output

3

 

Explanation

샘플 테스트 케이스에는 4개의 연속 숫자 하위 배열이 있습니다.

• S1 = (5, 3, 5) - 2개의 고유 번호가 있습니다.
• S2 = (3, 5, 2) - 3개의 고유 번호가 있습니다.
• S3 = (5, 2, 3) - 3개의 고유 번호가 있습니다.
• S4 = (2, 3, 2) - 2개의 고유 번호가 있습니다.

이 하위 배열에는 각각 2, 3, 3, 2개의 고유한 숫자가 있습니다. 가능한 모든 인접 하위 배열 중 고유 번호의 최대 양은 3입니다.

 

Code

import java.util.*;
public class test {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        Deque deque = new ArrayDeque<>();
        int n = in.nextInt();
        int m = in.nextInt();

        Set set = new HashSet<>();
        int max = 0;

        for (int i = 0; i < n; i++) {
            int num = in.nextInt();
            deque.add(num);
            set.add(num);
            if( i < m-1 ) continue;
            int size = set.size();
            if( size > max ) max = size;
            int removed = (Integer) deque.remove();
            if( !deque.contains(removed) ) {
                set.remove(removed);
            }  
        }
        System.out.println(max);
    }
}

 

 

Deque (Double Ended Queue)
양 끝에서 요소를 추가하거나 제거할 수 있는 큐 자료 구조.
큐와 스택의 모든 기능을 지원할 수 있음.

Deque 주요 메서드

• addFirst(E e) : 덱의 앞 쪽에 요소 추가
• addLast(E e) : 덱의 뒤쪽에 요소 추가
• offerFirst(E e) : 덱의 앞쪽에 요소 추가하고, 추가에 성공하면 true 반환.
• offerLast(E e) : 덱의 뒤쪽에 요소 추가하고, 추가에 성공하면 true 반환.
• removeFirst() : 덱의 앞쪽에서 요소를 제거하고, 제거한 요소 반환. 덱이 비어있으면 NoSuchElementException 발생.
• removeLast() : 덱의 뒤쪽에서 요소를 제거하고, 제거한 요소 반환. 덱이 비어있으면 NoSuchElementException 발생.
• pollFirst() : 덱의 앞쪽에서 요소를 제거하고, 제거한 요소 반환. 덱이 비어있으면 null 반환.
• pollLast() : 덱의 뒤쪽에서 요소를 제거하고, 제거한 요소 반환. 덱이 비어있으면 null 반환.
• getFirst() : 덱의 앞쪽 요소를 반환. 제거하지 않음. 덱이 비어있으면 NoSuchElementException 발생.
• getLast() : 덱의 뒤쪽 요소를 반환. 제거하지 않음. 덱이 비어있으면 NoSuchElementException 발생.
• peekFirst() : 덱의 앞쪽 요소를 반환. 제거하지 않음. 덱이 비어있으면 null 반환.
• peekLast() : 덱의 뒤쪽 요소를 반환. 제거하지 않음. 덱이 비어있으면 null 반환.

 

 

개인 공부를 위한 포스팅입니다.
모든 번역, 코드는 완벽하지 않을 수 있습니다.