[STUDY HALLE] 4주차 과제: 제어문

/* 실제로는 2021-02-23에 작성된 게시물입니다. */

학습 목표

자바가 제공하는 제어문을 학습하세요.

• 선택문
• 반복문

Deadline: ~2020/11/28 15:00

선택문

선택문(switch)은 if문과 비슷하지만 조금 더 정형화된 제어문이라고 할 수 있다.

switch(입력변수) {
    case 입력값1: ...
         break;
    case 입력값2: ...
         break;
    ...
    default: ...
         break;
}

조건이 많이 달릴 경우 if문보다 성능이 좋았지만, 요즘에는 이것이 유의미한 차이를 만들어내지 않는다고 한다. 다만, 그럼에도 좋은 가독성을 가지고 있으므로 입력값이 정형화 되어있는 경우 사용하면 좋을 것 같다.

반복문

반복해서 코드/문장을 수행해야할 경우 사용한다.
while

while(조건식){
  // 코드
}

do while : 조건이 만족되지 않더라도 한번은 수행하도록 한다.

do{
  // 코드
}while(조건식)

for : 반복 횟수가 고정되어있는 것이 특징이다.

for(초기화; 조건; 증감){
   // Body of for loop
}

for each(enhanced for) : for문을 사용하는데, iterative한 객체를 순회하며 원소에 접근할 수 있도록 한다.

for (변수타입 변수명 : 객체) {
    // 코드
}

LinkedList 구현

• LinkedList에 대해 공부하세요.
• 정수를 저장하는 ListNode 클래스를 구현하세요.
• ListNode add(ListNode head, ListNode nodeToAdd, int position)를 구현하세요.
• ListNode remove(ListNode head, int positionToRemove)를 구현하세요.
• boolean contains(ListNode head, ListNode nodeTocheck)를 구현하세요.

Linked List는 구성 요소인 노드가 자기 자신의 값과 다음 노드의 위치를 기억하고있는 자료구조의 형태이다. Array List와 비교하자면, Array List는 논리적 저장 순서와 물리적 저장 순서가 일치하므로, 원하는 인덱스의 값에 접근하는 시간은 상수시간 내에 가능하지만 삽입/삭제가 이루어질 경우 해당 인덱스 이후의 모든 값들을 한칸씩 옮겨주어야 하므로 O(n)의 시간 복잡도를 가진다.
반면 Linked List는 삽입/삭제를 위해서 노드의 포인터만 조작해주면 되므로 상수시간 내에 동작 가능하지만, 원하는 값을 찾기 위해서는 가장 앞에서부터 순차적으로 접근해야하기 때문에 O(n)의 시간 복잡도를 가진다. 하지만 결국 삽입/삭제를 위해 접근할 때도 O(n)이 소요되는 셈이므로, 어찌됬든 효율성을 따지자면 Array List에 비해 좋지 못하지만, 다른 자료구조(대표적으로 Tree)를 구성할 때 활용되며 진가를 발휘한다.

class ListNode{
    int value;
    ListNode next;

    ListNode(int value){
        this.value = value;
        next = null;
    }
}

public class LinkedList {
    public ListNode head;
    public int size;

    LinkedList(){
        head = null;
        size = 0;
    }

    boolean isValidPosition(int position){
        if(position < 0 || position > this.size - 1) return false;
        return true;
    }

    ListNode add(ListNode nodeToAdd, int position){
        if(!isValidPosition(position))
            return nodeToAdd;

        ListNode temp = this.head;
        for(int i = 0; i < position; ++i){
            temp = temp.next;
        }
        nodeToAdd.next = temp.next;
        temp.next = nodeToAdd;

        this.size += 1;
        return temp;
    }

    ListNode remove(int positionToRemove){
        if(!isValidPosition(positionToRemove))
            return null;

        ListNode temp = this.head;
        for(int i = 0 ; i < positionToRemove - 1; ++i){
            temp = temp.next;
        }

        if(temp == head) head = temp.next;
        else temp.next = temp.next.next;

        this.size -= 1;
        return temp;
    }

    boolean contains(ListNode nodeTocheck){
        ListNode temp = this.head;
        while(temp != null){
            if(temp == nodeTocheck) return true;
            temp = temp.next;
        }
        return false;
    }

    boolean contains(int valueTocheck){
        ListNode temp = this.head;
        while(temp != null){
            if(temp.value == valueTocheck) return true;
            temp = temp.next;
        }
        return false;
    }
}

Stack 구현

• int 배열을 사용해서 정수를 저장하는 Stack을 구현하세요.
• void push(int data)를 구현하세요.

• int pop()을 구현하세요.

• ListNode head를 가지고 있는 ListNodeStack 클래스를 구현하세요.
• void push(int data)를 구현하세요.
• int pop()을 구현하세요.

public interface Stack<T> {
    int maxsize = 100;
    void push(T data);
    T pop();
}

public class ArrayStack implements Stack<Integer>{
    private int size;
    private int[] arr;

    ArrayStack(){
        size = 0;
        arr = new int[maxsize];
    }

    @Override
    public void push(Integer data){
        if(this.size == maxsize)
            throw new RuntimeException();
        arr[size++] = data;
    }

    @Override
    public Integer pop(){
        if(size == 0)
            throw new RuntimeException();
        size -= 1;
        return arr[size];
    }

    public boolean isEmpty(){
        return size == 0;
    }
}

public class LinkedListStack implements Stack<Integer> {
    private LinkedList linkedList;

    @Override
    public void push(Integer data) {
        if(linkedList.size == maxsize)
            throw new RuntimeException();
        ListNode temp = new ListNode(data);
        linkedList.add(temp, linkedList.size++);
    }

    @Override
    public Integer pop() {
        if(linkedList.size == 0)
            throw new RuntimeException();
        linkedList.remove(--linkedList.size);
        return null;
    }

      public boolean isEmpty(){
        return linkedList.size == 0;
    }
}

참고문헌

https://lob-dev.tistory.com/