선형 자료 구조를 활용한 연습문제 - 1

문제1

ex) 1,3,7,5,9 -> 1,3,5,7,9

public class Practice1 {

    public static int[] solution(int[] arr){
        int[] arrNew = new int[arr.length];
        int index = 0;
        for(int i = 0; i < arr.length; i++){
            for (int j = 0; j < arr.length; j++){
                if(arrNew[index] == 0){
                    break;
                }
                index = (index + 1) % arr.length;
            }
            arrNew[index] = arr[i];
            index = (index + arr[i]) % arr.length;
        }
        return arrNew;
    }

    public static int[] modification(int[] arr) {
        int[] arrNew = new int[arr.length];

        int idx = 0;
        int cnt = 0;
        int val = arr[idx];

        while (cnt < arr.length) {
            while (val == 0) {
                idx = (idx + 1) % arr.length;
                val = arr[idx];
            }
            arrNew[cnt++] = val;
            arr[idx] = 0;
            idx = (val + idx) % arr.length;
            val = arr[idx];
        }
        return arrNew;
    }


    public static void main(String[] args) {
        // Test code
        // Modification test
        int[] arr = {1, 3, 7, 9, 5};
        int[] arrNew = modification(arr);
        System.out.println(Arrays.toString(arrNew));

        // Revert data
        arr = new int[]{1, 3, 5, 7, 9};
        int[] arrOrigin = solution(arr);
        System.out.println(Arrays.toString(arrOrigin));

        arr = new int[]{3, 2, 6, 8};
        arrOrigin = solution(arr);
        System.out.println(Arrays.toString(arrOrigin));
    }
}

문제2

public class Practice2 {

    public static void solution(int[][] matrix) {
        boolean frZero = false; // 첫째행
        boolean fcZero = false; // 첫째열

        for(int i = 0; i < matrix.length; i++){
            for(int j = 0; j < matrix[i].length; i++){
                if(matrix[i][j] == 0){
                    if(i == 0) frZero = true;
                    if(j == 0) fcZero = true;
                }
                matrix[i][0] = 0;
                matrix[0][i] = 0;
            }
        }

        for(int i = 0; i < matrix.length; i++){
            for(int j = 0; j < matrix[i].length; j++){
                if(matrix[i][0] == 0 || matrix[0][j] == 0){
                    matrix[i][j] = 0;
                }
            }
        }

        if(frZero){
            for(int i = 0; i < matrix[0].length; i++){
                matrix[0][i] = 0;
            }
        }

        if(fcZero){
            for(int i = 0; i < matrix[0].length; i++){
                matrix[i][0] = 0;
            }
        }

        for(int i = 0; i < matrix.length; i++){
            for(int j = 0; j < matrix[i].length; j++){
                System.out.print(matrix[i][j] + " ");
            }
            System.out.println();
        }
    }


    public static void main(String[] args) {
        // Test code
        int[][] matrix = {{1, 1, 1}, {1, 0, 1}, {1, 1, 1}};
        solution(matrix);

        System.out.println();
        matrix = new int[][]{{1, 1, 0}, {1, 1, 1}, {0, 1, 1}};
        solution(matrix);
    }
}

문제3

import java.util.LinkedList;

class Node{
    int data;
    int cmd;

    boolean visited;
    Node next;
    Node prev;

    public Node(int data, int cmd, boolean visited, Node next, Node prev) {
        this.data = data;
        this.cmd = cmd;
        this.visited = visited;
        this.next = next;
        this.prev = prev;
    }
}

class LinkedListC{
    Node head;

    public void add(int data, int cmd){
        if(this.head == null){
            this.head = new Node(data,cmd, false, null, null);
            this.head.next = this.head;
            this.head.prev = this.head;
        }else{
            Node cur = this.head;
            while(cur.next != this.head){
                cur = cur.next;
            }
            cur.next = new Node(data, cmd, false, cur.next, cur);
            this.head.prev = cur.next;
        }
    }
}


public class Practice3 {

    public static void solution(int[] data) {
        LinkedListC linkedList = new LinkedListC();
        for (int i = 0; i < data.length; i++) {
            linkedList.add(i+1, data[i]);
        }

        Node cur = linkedList.head;

        int visitCnt = 0;
        int cmd = 0;
        while(visitCnt != data.length){
            int cnt = 0;
            while(cnt != Math.abs(cmd)){
                if(cmd > 0){
                    cur = cur.next;
                }else{
                    cur = cur.prev;
                }

                if(cur.visited == false){
                    cnt++;
                }
            }
            System.out.print(cur.data + " ");
            cur.visited = true;
            visitCnt++;
            cmd = cur.cmd;
        }
    }

    public static void main(String[] args) {
        int[] balloon = {3, 2, 1, -3, -1};
        solution(balloon);
        System.out.println();

        balloon = new int[]{3, 2, -1, -2};
        solution(balloon);
    }
}

문제 4

public class Practice4 {
    public static void solution(String str) {
        // stack 그냥 3개 잡고 했을때 오류가 나는 상황 다시 한번 생각해보자!(순서 보장 X)
        Stack<String> stack = new Stack<>();
        boolean checkFlag = true;

        HashMap<String, String> map = new HashMap<>();
        map.put("(", ")"); map.put("{","}"); map.put("[", "]");

        for(String s : str.split("")){
            if(map.containsKey(s)){
                stack.push(s);
            }else if(map.containsValue(s)){
                if(stack.isEmpty()){
                    checkFlag = false;
                    break;
                }else{
                    String cur = stack.pop();
                    if(!s.equals(map.get(cur))){
                        checkFlag = false;
                        break;
                    }
                }
            }
        }

        if(checkFlag && stack.isEmpty()){
            System.out.println("PASS");
        }else{
            System.out.println("FAIL");
        }
    }

    public static void main(String[] args) {
        // Test code
        solution("[yyyy]-[mm]-[dd]");               // Pass
        solution("System.out.println(arr[0][1))");  // FAIL
        solution("Support [Java or Python(3.x)]");  // PASS
        solution("([[{}])");                        // FAIL
    }
}

문제 5

public class Practice5 {
    public static Integer solution(int n, int k, int l, ArrayList<ArrayList> apples, Queue<ArrayList> moves) {
        int[][] board = new int[n+1][n+1]; // 뱀의 위치 (1,1) -> 인덱스 관리 편하게 하기위해 n+1 사용하였음
        for(ArrayList item: apples){
            board[(int)item.get(0)][(int)item.get(1)] = 1;
        }

        Queue<ArrayList> snake = new LinkedList<>();
        snake.add(new ArrayList(Arrays.asList(1,1)));

        ArrayList<ArrayList> direction = new ArrayList<>();
        direction.add(new ArrayList(Arrays.asList(0,1)));
        direction.add(new ArrayList(Arrays.asList(1,0)));
        direction.add(new ArrayList(Arrays.asList(0,-1)));
        direction.add(new ArrayList(Arrays.asList(-1,0)));

        int dIdx = 0; int score = 0; int x = 1; int y = 1;

        while(true){
            score += 1; // 시간
            x += (int)direction.get(dIdx).get(0);
            y += (int)direction.get(dIdx).get(1); // 오른쪽으로 한칸

            if(1 <= x && x <= n && 1 <= y && y <= n){
                // 이를 만족하지 않으면 게임 종료
                ArrayList cur = new ArrayList(Arrays.asList(x, y));
                if(snake.contains(cur)){
                    // 몸과 부딪힌 경우
                    return score;
                }
                snake.add(cur);

                if(board[x][y] == 0){
                    snake.poll();
                } else if(board[x][y] == 1){
                    // 사과가 있는 경우
                    board[x][y] = 0;
                }
            }else{
                // 벽과 부딪힌 경우
                return score;
            }

            if(moves.size() > 0 && score == (int)moves.peek().get(0)){
                if((char) moves.peek().get(1) == 'D'){
                    dIdx = (dIdx + 1) % 4; //우측 90도
                    moves.poll();
                } else if((char)moves.peek().get(1) == 'L'){
                    dIdx = (dIdx - 1) % 4;
                    moves.poll();
                }
            }
        }

    }

    public static void main(String[] args) {
        // Test code
        int n = 6;
        int k = 3;
        int l = 3;
        ArrayList<ArrayList> apples = new ArrayList();
        apples.add(new ArrayList<>(Arrays.asList(3, 4)));
        apples.add(new ArrayList<>(Arrays.asList(2, 5)));
        apples.add(new ArrayList<>(Arrays.asList(5, 3)));

        Queue<ArrayList> moves = new LinkedList();
        moves.add(new ArrayList(Arrays.asList(3, 'D')));
        moves.add(new ArrayList(Arrays.asList(15, 'L')));
        moves.add(new ArrayList(Arrays.asList(7, 'D')));
        System.out.println((solution(n, k, l, apples, moves)));

        n = 10;
        k = 4;
        l = 4;
        apples.clear();
        apples.add(new ArrayList<>(Arrays.asList(1, 2)));
        apples.add(new ArrayList<>(Arrays.asList(1, 3)));
        apples.add(new ArrayList<>(Arrays.asList(1, 4)));
        apples.add(new ArrayList<>(Arrays.asList(1, 5)));

        moves.clear();
        moves.add(new ArrayList(Arrays.asList(8, 'D')));
        moves.add(new ArrayList(Arrays.asList(10, 'D')));
        moves.add(new ArrayList(Arrays.asList(11, 'D')));
        moves.add(new ArrayList(Arrays.asList(13, 'L')));
        System.out.println((solution(n, k, l, apples, moves)));

        n = 10;
        k = 5;
        l = 4;
        apples.clear();
        apples.add(new ArrayList<>(Arrays.asList(1, 5)));
        apples.add(new ArrayList<>(Arrays.asList(1, 3)));
        apples.add(new ArrayList<>(Arrays.asList(1, 2)));
        apples.add(new ArrayList<>(Arrays.asList(1, 6)));
        apples.add(new ArrayList<>(Arrays.asList(1, 7)));

        moves.clear();
        moves.add(new ArrayList(Arrays.asList(8, 'D')));
        moves.add(new ArrayList(Arrays.asList(10, 'D')));
        moves.add(new ArrayList(Arrays.asList(11, 'D')));
        moves.add(new ArrayList(Arrays.asList(13, 'L')));
        System.out.println((solution(n, k, l, apples, moves)));
    }
}