1. 선택정렬

1) 주어진 배열 중에서 최솟값을 찾는다.

2) 그 값을 맨 앞에 위치한 값과 교체한다(패스(pass)).

3) 맨 처음 위치를 뺀 나머지 리스트를 같은 방법으로 교체한다.

4) 하나의 원소만 남을 때까지 위의 1~3 과정을 반복한다

위의 알고리즘을 참고 하여 아래의 함수를 구현하시오.

• 1회전 후는 첫번째자리 한자리는 무조건 정렬이 된다.

public class SelectionSortTest {
    public static void selectionSort(int n, int[] arr) {
        int [] result = arr;

        for (int i = 0; i < n-1; i++) {
            int tmp = result[i];
            int index = i;
            for (int j = i+1; j < n; j++) {
                if (tmp > result[j]) {
                    tmp = result[j];
                    index = j;
                } else continue;
            }
            result[index] = result[i];
            result[i] = tmp;
        }
    }

    public static void main(String[] args) {

        int[] arr = {5,3,6,4,8,9,1,2,7};
        int num = arr.length;

        selectionSort(num, arr);
        System.out.println(Arrays.toString(arr));
    }
}

피드백

• 다른 사람들은 최소값과 배열의 값을 바꿀 때 swap()으로 함수를 빼내어서 구현을 하였다. 하지만 크게 메모리, 효율성에서 차이는 없을 것 같다.
• 원래는 int 배열로 반환했으나 그냥 void로 함수배열만 바꿔주었다.

2. stack 구현 (with 배열)

즉, 가장 최근에 스택에 추가한 항목이 가장 먼저 제거될 항목이다.

스택의 구현

• pop()가장 최 상위에 위치한 자료를 추출한 후에 스택에서 제거한다
• push(item)스택의 최 상위에 새로운 자료를 삽입한다
• isEmpty()스택이 empty 상태인지 확인한다. 비어 있으면 true를 반환한다
• clear()스택에 존재하는 모든 자료들을 삭제한다
• peek()가장 최 상위에 위치한 자료를 추출한다 pop 메소드와는 달리 스택에서 제거하지는 않는다

interface Stack{
    public boolean isEmpty();
    public boolean isFull();
    public void push(char item);
    public char pop();
    public char peek();
    public void clear();
}

public class StackTest {
	public static void main(String[] args) {
		
		Scanner sc = new Scanner(System.in);
		System.out.print("스택 사이즈를 입력하시오.");
		int stackSize = sc.nextInt() ;
		
		Stack stack = new Stack(stackSize);

		stack.push('A');
		stack.printStack();

		stack.push('B');
		stack.printStack();

		stack.push('C');
		stack.printStack();

		stack.pop();
		stack.printStack();

		stack.pop();
		stack.printStack();

		stack.peek();
		stack.printStack();

		stack.clear();
		stack.printStack();
	}
}

문제 해결

1. 처음에 풀이 방법을 몇가지 생각하였다.
   1) stack 값의 갯수에 맞게 배열 새로 생성 : 구현했을 때 생각보다 복잡하지는 않으나 메모리를 많이 잡아먹을 것 같다.
   2) 빈 공간을 다른 무언가로 채우기 : 특별히 채울만한게 없다.
   3) 안 보여주기 : 모범 답안과 비슷

2. 3)으로 풀이 시에도 남은 공간을 변수로 만드니 함수 안에서 변수를 계속 만들어야 해서 stack 안의 갯수를 변수로 선언하였다.

3. isEmpty(), isFull()안에 출력 (println) 을 넣었더니 push(), pop() 등의 if문의 조건문에 isEmpty(), isFull()를 썼을 때 출력이 계속 나왔다. 조건문에 함수를 넣을 때 주의하자.

package fifth.sep;

import java.util.Arrays;
import java.util.Scanner;

interface StackI{
    public boolean isEmpty();
    public boolean isFull();
    public void push(char item);
    public char pop();
    public char peek();
    public void clear();
}

class Stack implements StackI{
    private final int size;
    private char[] stack;
    private int num;

    public Stack(int size) {
        this.size = size;
        stack = new char[size];
        num = 0;
    }

    @Override
    public boolean isEmpty() {
        boolean empty = false;
        if (num == 0) {
            empty = true;
        }
        return empty;
    }

    @Override
    public boolean isFull() {
        boolean full = false;
        if (num == size) {
            full = true;
        }
        return full;
    }

    @Override
    public void push(char item) {
        if (this.isFull()) {
            System.out.println("Stack is Full!");
        } else {
            stack[num] = item;
            num += 1;
            System.out.println("입력된 문자  :  " + item);
        }

    }

    @Override
    public char pop() {
        char pop = 'X';

        if(this.isEmpty()) {
            System.out.println("Stack is Empty!");
        } else {
            pop = stack[num-1];
            num -= 1;
            System.out.println("삭제된 문자  :  " + pop);
        }
        return pop;
    }

    @Override
    public char peek() {
        char peak = 'X';

        if(this.isEmpty()) {
            System.out.println("Stack is Empty!");
        } else {
            peak = stack[num-1];
            System.out.println("마지막 문자  :  " + peak);
        }
        return peak;
    }

    @Override
    public void clear() {
        num = 0;
        System.out.println("Clear Stack");
    }

    public void printStack() {
        String stackToString = "";
        if (this.isEmpty()) {
            System.out.println("Stack is Empty!");
        } else {
            for (int i = 0; i < num; i++) {
                stackToString += stack[i];
            }
            System.out.println("Stack elements  :  " + stackToString);
        }
    }
}