Hackerrank Day 18 Queues and Stacks

알고리즘 연습 사이트

www.hackerrank.com

Day 18:Queues and Stacks

 자료구조의 가장 기본이 되는 Queue와 Stack이다. 

*참고
Stack: https://docs.oracle.com/javase/7/docs/api/java/util/Stack.html
Queue: https://docs.oracle.com/javase/7/docs/api/java/util/Queue.html

* Stack 
Last In First Out (LIFO).
가장 나중에 넣은 것이 처음에 나오는 형태. 
밑이 막혀 있는 그릇에 데이터를 차곡차곡 쌓고 꺼낼때는 가장 위부터 꺼낸다.

Stack 클래스에는 주요 메소드 3가지가 있다
-Push : Stack의 가장 맨위에 데이터를 추가한다.
-Peek : 가장 맨위의 데이터를 리턴하지만 데이터를 지우지 않는다.
-Pop : 가장 맨위의 데이터를 리턴하고 그 데이터를 지운다.

* Queue
First In First Out (FIFO)
처음에 넣은 것이 처음에 나오는 형태.
- Enqueue : 큐의 가장 마지막의 그 다음에 데이터를 넣는다.
- Dequeue : 큐의 가장 앞부분(head)의 데이터를 리턴하고 그 값을 큐에서 삭제한다. 그러고 나면 두 번째에 있던 데이터가 head가 된다. 




오늘 문제는 앞으로 읽으나 거꾸로 읽으나 동일한 단어나 문장이 되는 문자열을 찾아내는 것이다. 그러한 문장 혹은 구를 palindrome이라고 한다.

문자열을 char형으로 쪼개어 Stack과 Queue에 각각 넣고 Stack에서는 pop을 하여 리턴되는 문자와, Queue의 remove메소드를 호출하여 리턴되는 결과를 서로 비교하여 문자열의 절반까지 비교를 하여 값이 완벽히 동일하다면 palindrome, 다르다면 palindrome이 아닌 것이다.

여기서 중요한 것은 스택과 큐의 성질을 이해하고 클래스의 메소드의 사용법을 이해하면 된다.

위에 링크해 둔 API 문서에 상세히 나와 있다.

public class Solution {
    // Write your code here.
    Stack stack = new Stack();
    Queue queue = new LinkedList();

    void pushCharacter(char ch){
        stack.push(ch);
    }
    void enqueueCharacter(char ch){
        queue.add(ch);
    }
    char popCharacter(){
        return stack.pop();
    }
    char dequeueCharacter(){
        return queue.remove();
    }
 
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        String input = scan.nextLine();
        scan.close();

        // Convert input String to an array of characters:
        char[] s = input.toCharArray();

        // Create a Solution object:
        Solution p = new Solution();

        // Enqueue/Push all chars to their respective data structures:
        for (char c : s) {
            p.pushCharacter(c);
            p.enqueueCharacter(c);
        }

        // Pop/Dequeue the chars at the head of both data structures and compare them:
        boolean isPalindrome = true;
        for (int i = 0; i < s.length/2; i++) {
            if (p.popCharacter() != p.dequeueCharacter()) {
                isPalindrome = false;                
                break;
            }
        }

        //Finally, print whether string s is palindrome or not.
        System.out.println( "The word, " + input + ", is " 
                           + ( (!isPalindrome) ? "not a palindrome." : "a palindrome." ) );
    }
}