aaaicu

문제 : https://www.acmicpc.net/problem/10828

import java.util.LinkedList;
import java.util.List;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scan = new  Scanner(System.in);
        InnerStack s = new InnerStack();
        int input = Integer.parseInt(scan.next());
        
        for(int i = 0 ; i < input ; i++) {
            String str = scan.next();
            if("push".equals(str)) {
                int num = Integer.parseInt(scan.next());    
                s.push(num);
            }else if("pop".equals(str)) {
                System.out.println(s.pop());
            }else if("size".equals(str)) {
                System.out.println(s.size());
            }else if("empty".equals(str)) {
                System.out.println(s.isEmpty());
            }else if("top".equals(str)) {
                System.out.println(s.top());
            }    
            
        }
    }
    
    public static class InnerStack {
        InnerStack(){
        }
        List list = new LinkedList<>();
        private int cursor = 0 ;
    
        public void push(int i ) {
            list.add(i);
            cursor++;
        }
        
        public int pop() {
            int res;
            
            if(cursor > 0) {
                res=list.get(cursor-1);
                list.remove(cursor-1);
                cursor--;
            }else {
                res = -1;
            }
            
            return res;
        }
        
        public int top() {
            int res;
            if(cursor > 0) {
                res=list.get(cursor-1);
            }else {
                res = -1;
            }
            return res;
        }
        
        public int size() {
            return cursor;
        }
        
        public int isEmpty() {
            int res;
            if (cursor ==0) {
                res = 1;
            }else {
                res = 0;
            }
            return res;
        }
        
    }
}

문제 : https://www.acmicpc.net/problem/2750

import java.util.Scanner;

public class Main {
    static int[] bubleSort(int[] array) {
        int[] result = new int[array.length];
            for(int i = array.length ; i > 1 ; i -- ) {
                for(int j = 0 ; j < i-1 ; j++ ) {
                    if(array[j]>array[j+1]) {
                        int temp = array[j+1];
                        array[j+1] = array[j];
                        array[j] = temp;
                    }
                    
                }
            }
        result = array;
        return result;
    }
    
    public static void main(String[] args) {

        Scanner scan = new Scanner(System.in);
        int count = 0;
        int num = scan.nextInt();
        int[] arr = new int[num];
        for (int i = 0; i < num; i++) {
            arr[count] = scan.nextInt();
            count++;
        }
        // int[] arr = {5,3,4,7,6,2,1};
        for (int a : bubleSort(arr)) {
            System.out.println(a);
        }

        scan.close();
    }
}

문제 : https://www.acmicpc.net/problem/2750

import java.util.Scanner;
public class Main {
	public static void main(String[] args) {
		
		Scanner scan = new Scanner(System.in);
		int count = 0;
		int num = scan.nextInt();
		int[] arr = new int[num];
		for (int i = 0 ; i< num ; i++){
			arr[count] = scan.nextInt();
			// System.out.println(arr[count]);
			count++;
		}
		// int[] arr = {5,3,4,7,6,2,1};
		for (int i = 1; i < arr.length; i++) {
			int a = i - 1;
			int std = arr[i];
			while (a >= 0 && std < arr[a]) {
				arr[a + 1] = arr[a];
				a = a - 1;

			}
			arr[a + 1] = std;
		}

		for (int a : arr) {
			System.out.println(a);
		}
		scan.close();
	}
}

문제 : https://www.acmicpc.net/problem/1149

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        int[][] street = new int[n][3];
        int d[][] = new int[n][3];

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < 3; j++) {
                street[i][j] = scan.nextInt();
            }
        }
        // 입력부
        for (int j = 0; j < n; j++) {
            for (int i = 0; i < 3; i++) {
                if (j == 0) {
                    d[j][i] = street[j][i];
//                    System.out.print(d[j][i] + " ");
                } else {

                    d[j][i] = Math.min(d[j - 1][(i + 1) % 3], d[j - 1][(i + 2) % 3]) + street[j][i];
//                    System.out.print(d[j][i] + " ");
                }
            }
//            System.out.println();
        }

//        for (int a : d[n - 1]) {
//            System.out.println(a);
//        }
        System.out.println(Math.min(d[n-1][0],Math.min(d[n-1][1], d[n-1][2])));

        scan.close();
    }

}

문제 : https://www.acmicpc.net/problem/2748

간단하게 구현할 수 있는 피보나치 수열에 동적계획법을 적용해봤다.

배열을 만들어서 피보나치 메소드에 배열의 위치를 알려주어 한번 계산한 피보나치수는 다시 계산하지 않도록 만들었다.

import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		//피보나치
		
		Scanner scan = new Scanner(System.in);
		int n = scan.nextInt();
		long [] arr = new long [n+1];
		for( int i = 0 ; i < arr.length; i ++) {
			arr[i] = -1;
		}
		System.out.println(fi(n, arr));
//		for(int a : arr) {
//			System.out.print(a+" ");
//		}
		scan.close();
	}
	static long fi(int num,long [] arr) {
		if(arr[num] != -1) {
			return arr[num];
		}
		if (num == 0 || num == 1) {
			arr[num] = num;
			return num;
		} else {
			long result = fi(num-1,arr) + fi(num-2,arr);
			arr[num] = result;
			return result;
		}
	}

}

문제 : https://www.acmicpc.net/problem/2667

import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = Integer.parseInt(scan.next());

        Queue q = new LinkedList<>();
        int groupCount = 0;
        List res = new LinkedList<>();
        Node[][] arr = new Node[n][n];
        Node start = null;
        for (int i = 0; i < n; i++) {
            String temp = scan.next();
            for (int j = 0; j < n; j++) {
                int value = temp.charAt(j) - '0';
                arr[i][j] = new Node(i, j, value);
                if (arr[i][j].val == 1) {
                    start = arr[i][j];
                }
            }
        }
        while (start != null) {
            groupCount++;
            int count = 1;
            start.val = -1;
            q.offer(start);

            while (!q.isEmpty()) {
                Node[] aj = find(q.poll(), n, arr);
                for (int i = 0; i < 4; i++) {
                    if (aj[i] != null) {
                        aj[i].val = -groupCount;
                        count++;
                        q.offer(aj[i]);
                    }
                }

            }

//            for (int i = 0; i < n; i++) {
//                for (int j = 0; j < n; j++) {
//                    System.out.print(arr[i][j].val);
//                }
//                System.out.println();
//            }
            res.add(count);
            // start를 기준으로 탐색시작
            start = null;
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    if (arr[i][j].val == 1) {
                        start = arr[i][j];
                    }
                }
            }
        }

        System.out.println(groupCount);
        for(int i =0 ; i < groupCount ; i ++) {
            res.sort(null);
            System.out.println(res.get(i));
        }
    }

    static Node[] find(Node node, int n, Node[][] array) {
        Node[] result = new Node[4];
        int[] addCol = { 0, 0, -1, 1 };
        int[] addRow = { -1, 1, 0, 0 };

        for (int i = 0; i < 4; i++) {
            int col = node.col + addCol[i];
            int row = node.row + addRow[i];

            if (col >= n || row >= n || col < 0 || row < 0) {
                result[i] = null;
            } else {
                if (array[col][row].val == 1) {
                    array[col][row].dist = node.dist + 1;
                    result[i] = array[col][row];
                } else {
                    result[i] = null;
                }
            }
        }
        return result;
    }

    static class Node {
        int col;
        int row;
        int val;
        int dist;

        public Node(int col, int row, int val) {
            super();
            this.col = col;
            this.row = row;
            this.val = val;
        }

        @Override
        public String toString() {
            return "Node [col=" + col + ", row=" + row + ", val=" + val + ", dist=" + dist + "]";
        }

    }

}

문제 : https://www.acmicpc.net/problem/2178

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = Integer.parseInt(scan.next());
        int m = Integer.parseInt(scan.next());
        
        
        Queue q = new LinkedList();
        Node[][] arr = new Node[n][m];

        for(int i = 0 ; i < n ; i++) {
            String row = scan.next();
            for(int j = 0 ; j < m ; j++) {
                arr[i][j] = new Node(i,j,row.charAt(j) - '0');
            }
        }

        q.offer(arr[0][0]);
        //입력부
        
        while(!q.isEmpty()) {
            Node node = q.poll();
//            System.out.println(node);
            Node[] ajNode = find(node,n,m,arr) ;
//            //이동가능한 노드를 찾는다
            for(int i =0 ; i < 4 ; i++) {
                if(ajNode[i] != null) {
                    ajNode[i].value=-1;
                    //큐에 넣는다
                    q.offer(ajNode[i] );
                }
                
            }
        }
        scan.close();
        System.out.println(arr[n-1][m-1].dist);
    }
//    
    static Node[] find(Node node,int col, int row ,Node[][] array) {
        Node[] result = new Node[4];
        int addC[] = {0,0,-1,1};
        int addR[] = {-1,1,0,0};
        
        for(int i = 0 ; i < 4 ; i ++) {
            
            int c = node.col+addC[i];
            int r = node.row+addR[i];
            
            if(c >= col || r >= row || c < 0 || r < 0 ) {
                result[i] = null;
            }else {
                if(array[c][r].value == 1 ) {
                    array[c][r].dist = node.dist+1;
                    result[i] = array[c][r];
//                    System.out.println("삽입예정 노드" + result[i]);
                }else {
                    result[i] = null;
                }
            }
        }
        return result;
    }

    static class Node {
        int row ;
        int col ; 
        int value;
        int dist = 1;
        
        public Node(int col,int row, int value) {
            this.row = row;
            this.col = col;
            this.value = value;
        }

        @Override
        public String toString() {
            return "Node [row=" + row + ", col=" + col + ", value=" + value + "]";
        }
    }
}

문제 : https://www.acmicpc.net/problem/7576

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		// 가로
		int m = scan.nextInt();
		// 세로
		int n = scan.nextInt();
		Node arr[][] = new Node[n][m];

		int maxDay = 0;

		// 큐선언
		Queue queue = new LinkedList();
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				int value = scan.nextInt();
				arr[i][j] = new Node(j, i, value);
				if (value == 1) {
					queue.offer(arr[i][j]);
				}
			}
		}
		// 입력부

		while (!queue.isEmpty()) {
			//
			Node polledNode = queue.poll();
			Node[] toOfferNode = check(polledNode, m, n, arr);
			
			for (int i = 0; i < 4; i++) {
				if (toOfferNode[i] != null) {
					toOfferNode[i].value = 1;
					if(maxDay < toOfferNode[i].day) {
						maxDay = toOfferNode[i].day;
					}
					queue.offer(toOfferNode[i]);
				}
			}
			
//			System.out.println(polledNode);
//			System.out.println(queue.isEmpty());
		}
//		for (int i = 0; i < n; i++) {
//			for (int j = 0; j < m; j++) {
//				System.out.print(arr[i][j].value+"");
//			}
//			System.out.println();
//		}
//		
//		
//		for (int i = 0; i < n; i++) {
//			for (int j = 0; j < m; j++) {
//				System.out.printf("%2d",arr[i][j].day);
//			}
//			System.out.println();
//		}
//		
		
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				if(arr[i][j].value == 0) {
					maxDay = -1;
				}
			}
		}
		System.out.println(maxDay);
		scan.close();
	}

	static Node[] check(Node node, int m, int n, Node[][] arr) {

		Node[] result = new Node[4];
		int x[] = { 0, 0, -1, 1 };
		int y[] = { -1, 1, 0, 0 };

		for (int i = 0; i < 4; i++) {
			int chkX = node.x + x[i];
			int chkY = node.y + y[i];
			if (chkX < 0 || chkY < 0 || chkX >= m || chkY >= n) {
				result[i] = null;
			} else {
				if (arr[chkY][chkX].value == 0) {
					arr[chkY][chkX].day = node.day+1;
					result[i] = arr[chkY][chkX];
//					System.out.println("추가할 노드 : " + result[i]);
				}
			}
		}
		return result;
	}

	static class Node {
		int x;
		int y;
		int value;
		int day = 0;

		public Node(int x, int y, int value) {
			this.x = x;
			this.y = y;
			this.value = value;
			if(value == -1 ) {
				this.day = -1;
			}
		}

		@Override
		public String toString() {
			return "Node [x=" + x + ", y=" + y + ", value=" + value + ", day="+day+"]";
		}
	}
}

문제 : https://www.acmicpc.net/problem/1475 

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {

        int[] number = new int[10];
        Scanner scan = new Scanner(System.in);
        String input = scan.nextLine();
        
        int max =0 ;
        
        for (int i = 0; i < input.length(); i++) {
            number[input.charAt(i)-'0']++;
        }
        number[6] = (int)Math.ceil((number[6]+(double)number[9])/2);
        number[9] = 0;
        
        for(int num : number) {
            if(num > max) {
                max = num;
            }
        }        
        System.out.println(max);
        scan.close();
    }
}

문제 : https://www.acmicpc.net/problem/2775 

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {

        int[][] room = new int[15][14];
        
        for (int i = 1; i <= 14; i++) {
            room[0][i - 1] = i;
            room[i][0] = 1;
        }

        for (int i = 1; i < 15; i++) {

            for (int j = 1; j < 14; j++) {
                room[i][j] = room[i][j - 1] + room[i - 1][j];
            }
        }
        
        Scanner scan = new Scanner(System.in);
        int input = scan.nextInt();
        int [] result = new int [input];
        
        
        for( int i = 0 ; i < input ; i ++) {
            int k = scan.nextInt();
            int n = scan.nextInt();
            result[i] = room[k][n-1];
        }
        
        for(int res : result) {
            System.out.println(res);
        }
    }
}