자바(JAVA) 알고리즘 손코딩 테스트 문제

1. 큐

import java.util.NoSuchElementException;

public class Queue {

	private static int MAX_QUE_SIZE = 10;
	private int last;
	private int first;
	private int size;
	private int[] data = new int[MAX_QUE_SIZE];
	
	public Queue() {
		
		first = last = size = 0;
	}
	
	public int size() {
		
		return size;
	}
	
	public boolean isEmpty() {
		return size==0;
	}
	
	public void add(int item) {
		last = (last+1) & data.length;
		data[last] = item;
		size++;
	}
	
	public int pop() {
		if (isEmpty()) {
			throw new NoSuchElementException();
		}
		
		first = (first+1) % data.length;
		int item = data[first];
		data[first] = 0;
		size --;
		
		return item;
	}
	
	public int peek() {
		
		if(isEmpty()) throw new NoSuchElementException();
		
		return data[first];
	}
}

 

2. 스택

public class Stack {

	private static int MAX_STACK_SIZE = 10;
	private int top;
	private int[] data = new int[MAX_STACK_SIZE];
	
	public Stack() {
		top = -1;
	}
	
	public void push(int data_) throws Exception {
		
		if(isFull()) {
			throw new Exception("스택이 가득 찼습니다.");
		}
		data[++top] = data_;
	}
	
	public int pop() throws Exception {
		if(isEmpty()) {
			throw new Exception("스택이 비었습니다.");
		}
		return data[top--];
	}
	
	public int peek() throws Exception {
		if(isEmpty()) {
			throw new Exception("스택이 비었습니다.");
		}
		return data[top];
	}
	
	public boolean isEmpty() {
		return top ==-1;
	}
	
	public boolean isFull() {
		return top == MAX_STACK_SIZE-1;
	}
	
	public int size() {
		return top + 1;
	}
}

 

3. 스택 2개로 큐 만들기

import java.util.Stack;

public class QueStack {

	Stack<Integer> oldStack;
	Stack<Integer> newStack;
	
	public QueStack() {
		oldStack = new Stack<>();
		newStack = new Stack<>();
	}
	
	public void enqueue(int a) {
		oldStack.push(a);
	}
	
	public int dequeue() {
		int result = -1;
		
		if(newStack.isEmpty()) {
			while(!oldStack.isEmpty()) {
				newStack.push(oldStack.pop());
			}
			
			result = newStack.pop();
		}
		
		//oldStack에 남아있는 값이 있으면 다시 #1로 옮겨준다.
		if(!newStack.isEmpty()) {
			while(!newStack.isEmpty()) {
				oldStack.push(newStack.pop());
			}
		}
		
		return result;
	}
}

 

4. 연결 리스트

public class LinkedList<N> {
    // 첫번째 노드를 가리키는 필드
    private Node head;
    private Node tail;
    private int size = 0;

    private class Node{
        // 데이터가 저장될 필드
        private Object data;
        // 다음 노드를 가리키는 필드
        private Node next;
        public Node(Object input) {
            this.data = input;
            this.next = null;
        }
        // 노드의 내용을 쉽게 출력해서 확인해볼 수 있는 기능
        public String toString(){
            return String.valueOf(this.data);
        }
    }

    public void addFirst(Object input){
        // 노드를 생성합니다.
        Node newNode = new Node(input);
        // 새로운 노드의 다음 노드로 해드를 지정합니다.
        newNode.next = head;
        // 헤드로 새로운 노드를 지정합니다.
        head = newNode;
        size++;
        if(head.next == null){
            tail = head;
        }
    }

    public void addLast(Object input){
        // 노드를 생성합니다.
        Node newNode = new Node(input);
        // 리스트의 노드가 없다면 첫번째 노드를 추가하는 메소드를 사용합니다.
        if(size == 0){
            addFirst(input);
        } else {
            // 마지막 노드의 다음 노드로 생성한 노드를 지정합니다.
            tail.next = newNode;
            // 마지막 노드를 갱신합니다.
            tail = newNode;
            // 엘리먼트의 개수를 1 증가 시킵니다.
            size++;
        }
    }

    Node node(int index) {
        Node x = head;
        for (int i = 0; i < index; i++)
            x = x.next;
        return x;
    }

    public void add(int k, Object input){
        // 만약 k가 0이라면 첫번째 노드에 추가하는 것이기 때문에 addFirst를 사용합니다.
        if(k == 0){
            addFirst(input);
        } else {
            Node temp1 = node(k-1);
            // k 번째 노드를 temp2로 지정합니다.
            Node temp2 = temp1.next;
            // 새로운 노드를 생성합니다.
            Node newNode = new Node(input);
            // temp1의 다음 노드로 새로운 노드를 지정합니다.
            temp1.next = newNode;
            // 새로운 노드의 다음 노드로 temp2를 지정합니다.
            newNode.next = temp2;
            size++;
            // 새로운 노드의 다음 노드가 없다면 새로운 노드가 마지막 노드이기 때문에 tail로 지정합니다.
            if(newNode.next == null){
                tail = newNode;
            }
        }
    }

    public String toString() {
        // 노드가 없다면 []를 리턴합니다.
        if(head == null){
            return "[]";
        }
        // 탐색을 시작합니다.
        Node temp = head;
        String str = "[";
        // 다음 노드가 없을 때까지 반복문을 실행합니다.
        // 마지막 노드는 다음 노드가 없기 때문에 아래의 구문은 마지막 노드는 제외됩니다.
        while(temp.next != null){
            str += temp.data + ",";
            temp = temp.next;
        }
        // 마지막 노드를 출력결과에 포함시킵니다.
        str += temp.data;
        return str+"]";
    }

    public Object removeFirst(){
        // 첫번째 노드를 temp로 지정하고 head의 값을 두번째 노드로 변경합니다.
        Node temp = head;
        head = temp.next;
        // 데이터를 삭제하기 전에 리턴할 값을 임시 변수에 담습니다.
        Object returnData = temp.data;
        temp = null;
        size--;
        return returnData;
    }

    public Object remove(int k){
        if(k == 0)
            return removeFirst();
        // k-1번째 노드를 temp의 값으로 지정합니다.
        Node temp = node(k-1);
        // 삭제 노드를 todoDeleted에 기록해 둡니다.
        // 삭제 노드를 지금 제거하면 삭제 앞 노드와 삭제 뒤 노드를 연결할 수 없습니다.
        Node todoDeleted = temp.next;
        // 삭제 앞 노드의 다음 노드로 삭제 뒤 노드를 지정합니다.
        temp.next = temp.next.next;
        // 삭제된 데이터를 리턴하기 위해서 returnData에 데이터를 저장합니다.
        Object returnData = todoDeleted.data;
        if(todoDeleted == tail){
            tail = temp;
        }
        // cur.next를 삭제 합니다.
        todoDeleted = null;
        size--;
        return returnData;
    }

    public Object removeLast(){
        return remove(size-1);
    }

    public int size(){
        return size;
    }

    public Object get(int k){
        Node temp = node(k);
        return temp.data;
    }

    public int indexOf(Object data){
        // 탐색 대상이 되는 노드를 temp로 지정합니다.
        Node temp = head;
        // 탐색 대상이 몇번째 엘리먼트에 있는지를 의미하는 변수로 index를 사용합니다.
        int index = 0;
        // 탐색 값과 탐색 대상의 값을 비교합니다.
        while(temp.data != data){
            temp = temp.next;
            index++;
            // temp의 값이 null이라는 것은 더 이상 탐색 대상이 없다는 것을 의미합니다.이 때 -1을 리턴합니다.
            if(temp == null)
                return -1;
        }
        // 탐색 대상을 찾았다면 대상의 인덱스 값을 리턴합니다.
        return index;
    }
}

 

5. 해시 테이블

public class HashTable {
    LinkedList<Node>[] data;

    public HashTable(int size) {
        this.data = new LinkedList[size];
    }

    int getHashCode(String key) {
        int hashCode = 0;
        for(char c : key.toCharArray()) {
            hashCode += c;
        }

        return hashCode;
    }

    int convertToIndex(int hashCode) {
        return hashCode % data.length;
    }

    Node searchKey(LinkedList<Node> list, String key) {
        if(list == null) return null;

        for(Node node : list) {
            if(node.key.equals(key)) {

                return node;
            }
        }

        return null;
    }

    void put(String key, String value) {
        int hashCode = getHashCode(key);
        int index = convertToIndex(hashCode);

        LinkedList<Node> list = data[index];

        if(list == null) {
            list = new LinkedList<Node>();
            data[index] = list;
        }

        Node node = searchKey(list, key);

        if(node == null) {
            list.addLast(new Node(key, value));
        } else {
            node.setValue(value);
        }
    }

    public String get(String key) {
        int hashCode = getHashCode(key);
        int index = convertToIndex(hashCode);
        LinkedList<Node> list = data[index];
        Node node = searchKey(list, key);

        return node == null ? "Not found" : node.getValue();
    }

    static class Node {
        String key;
        String value;

        public Node(String key, String value) {
            this.key = key;
            this.value = value;
        }

        public String getValue() {
            return this.value;
        }

        public void setValue(String value) {
            this.value = value;
        }
    }
}

 

6. 싱글턴 패턴

class Singleton {
    private Singleton() {}

    public static Singleton getInstance() {
        return LazyHolder.INSTANCE;
    }

    private static class LazyHolder {
        private static final Singleton INSTANCE = new Singleton();
    }
}

 

7. 피보나치

public class Fibonacci {
    static int[] cache = new int[11];
    public static void main(String[] args) {
        System.out.println(loopFibonacci(8));
        System.out.println(recurFibonacci(8));
        System.out.println(dpFibonacci(8));
    }

    public static int loopFibonacci(int n) {
        int a = 0, b = 1, c = 0;
        if(n == 0) return 0;
        else if(n == 1) return 1;
        else {
            for (int i = 2; i <= n; i++) {
                c = a + b;
                a = b;
                b = c;
            }
        }
        return c;
    }


    public static int recurFibonacci(int n) {
        if(n == 0) return 0;
        if(n == 1) return 1;
        return recurFibonacci(n - 1) + recurFibonacci(n - 2);
    }


    public static int dpFibonacci(int n) {
        if(n == 0) return 0;
        if(n == 1) return 1;
        int ret = cache[n];
        if(ret != 0) return ret;
        return cache[n] = dpFibonacci(n - 1) + dpFibonacci(n - 2);
    }
}

 

8. N크기의 정수 배열에서 K번째로 큰 수

/*
*	Quick Selection 사용
*   보통 정렬을 사용하면 O(NlgN), 이 방법은 O(N)
*/

static int K = 4;
static int ret = -1;

public static void main(String[] args) {
    int[] arr = {3, 5, 2, 4, 1};

    QuickSelection(arr, 0, arr.length - 1);
    System.out.println(ret);
}


public static void QuickSelection(int[] arr, int left, int right) {
    int pivot = partition(arr, left, right);

    if(pivot == K - 1) {
       ret = arr[pivot];
    }
    else if(pivot > K - 1) {
        QuickSelection(arr, left, pivot - 1);
    } else {
        QuickSelection(arr, pivot + 1, right);
    }
}

public static int partition(int[] arr, int left, int right) {
    int mid = (left + right) / 2;
    swap(arr, left, mid);

    int i = left, j = right;
    int pivot = arr[left];

    while (i < j) {
        while(arr[j] >= pivot)
            j--;
        while(i < j && arr[i] <= pivot)
            i++;

        swap(arr, i, j);
    }

    arr[left] = arr[i];
    arr[i] = pivot;

    return i;
}

public static void swap(int[] arr, int a, int b) {
    int tmp = arr[a];
    arr[a] = arr[b];
    arr[b] = tmp;
}

 

9. 랜덤 한 자리 숫자 10개 출력

import java.util.Random;

public class RandomClass {
    public static void main(String[] args) {
        Random random = new Random();

        for(int i = 0; i < 10; i++) {
            System.out.println(random.nextInt(9) + 1);
        }
    }
}

 

10.  아나그램 판별

// 정렬해서 같은지 판별

import java.util.Arrays;

public class Anagram {
    public static void main(String[] args) {
        char[] a = "acdbe".toCharArray();
        char[] b = "ecabd".toCharArray();
        Arrays.sort(a);
        Arrays.sort(b);

        if(Arrays.equals(a, b))
            System.out.println(true);
        else
            System.out.println(false);
    }
}

 

11. 최소 공배수, 최대 공약수

// 유클리드 호제법
// 최소공배수 = (n1 * n2) / (n1과 n2의 최대공약수)

public class GCD_LCM {
    public static void main(String[] args) {
        System.out.println(gcd(8, 12));

        int LCM = (8 * 12) / gcd(8, 12);
        System.out.println(LCM);
    }


    public static int gcd(int a, int b) {
        if(b == 0) return a;
        return gcd(b, a % b);
    }
}

 

12. 이진 트리 순회

public class TreeTraversal {
    class Node {
        int data;
        Node left, right;

        public Node(int data) {
            this.data = data;
        }
    }

    class Tree {
        public Node root;

        public void setRoot(Node node) {
            root = node;
        }

        public Node getRoot() {
            return root;
        }

        public Node createNode(int data, Node left, Node right) {
            Node node = new Node(data);
            node.left = left;
            node.right = right;
            return node;
        }
                //중위 순회
        public void inOrder(Node node) {
            if(node == null) return;

            inOrder(node.left);
            System.out.println(node.data);
            inOrder(node.right);
        }
                //전위 순회
        public void preOrder(Node node) {
            if(node == null) return;

            System.out.println(node.data);
            preOrder(node.left);
            preOrder(node.right);
        }
                //후위 순회
        public void postOrder(Node node) {
            if(node == null) return;

            postOrder(node.left);
            postOrder(node.right);
            System.out.println(node.data);
        }
    }
}