1927: 최소힙

 public static class MinHeap{
        //중간 삭제/삽입이 가능해야하기때문에 ArrayList를 사용
        ArrayList<Long> list;
        MinHeap(){
            //보통 맨처음 idx는 0으로 처리
            list = new ArrayList<>();
            list.add(0l);
        }
        //가장첫번째 root에 위치한 최솟값을 return 하고
        //그 값을 삭제하는 메서드
        //logN의 시간복잡도
        public long printMin(){
            //맨처음값에 0이들어있기땜누에 size는 최소2부터 시작해야한다
            //그러니까 1이랑같거나 그 밑에면 더이상 pop할수없음을 의미한다
            //문제조건에서 얘기했던 대로 0을 출력해준다
            if(list.size()-1 < 1) return 0;
            //get(0)엔 0이들어있을테니 첫원소인1을 return해서 저장한다
            //그런데 단순히 return만 하면안된다. 값이 하나 빠졌으니 나머지 값들을 재정렬해주어야한다
            //그정렬은 맨마지막값을 빼서 root에 넣어서 다시 재정렬함으로써 해결된다
            long result = list.get(1);
            //마지막노드를 root에 넣고 마지막 노드를 삭제한다
            list.set(1,list.get(list.size()-1));
            list.remove(list.size()-1);
            //<마지막노드를 제대로 된 자리에 위치시키는 작업>
            //맨처음에 마지막 노드는 idx=1에위치한다
            int idx = 1;
            //idx*2를 아래아래줄에서 사용할서이기때문에 size보다 작은지를 항상확인해주어야한다
            //그리고 size보다 크다면 이것은 다 돌은것이기때문에 반복문을 종료해준다
            while(idx*2 < list.size()){
                //minheap에서 부모-자식은 그냥 부모가 더 작은값이기만하면된다
                //그래서 일단 자식둘중하나의 값으로 minPos와 min을 세팅하고
                int minPos = idx*2;
                long min = list.get(idx*2);
                //만약에 오른쪽에 있는애가 더 작을경우 더 작은값과 변경을 한다
                //부모, 자식2이 있을때 가장작은값이 부모가 돼야하니까
                if(idx*2+1<list.size() && list.get(idx*2+1) < min){
                    minPos = idx*2+1;
                    min = list.get(idx*2+1);
                }
                //그리고 만약에 이 얻은 값이 더 크다면 우리는 제대로 정렬을 수행하게 된 것이기때문에
                //반복을 종료한다
                if(min > list.get(idx)) break;
                //내가 얻어낸 가장작은 값과 맨처음에 root랑 바꾼 맨마지막 값을 교환한다
                list.set(minPos, list.get(idx));
                list.set(idx, min);
                //idx가 minPos를 가리켜야한다 그래야 다음 반복이 수행될 수 있다
                idx = minPos;
            }


            return result;
        }
        //logN의 시간복잡도
        public void add(long x){
            //끝단에 추가하고 계속해서 올라가는 식으로 구현
            list.add(x);
            int idx = list.size()-1;//x의 idx정보
            //idx는 아래에있고 idx/2는 위에있다
            //아래에있는게 위에있는것보다 작다면 위로 올라가야한다
            while(idx>1&& list.get(idx/2) > list.get(idx)){
                //부모보다 삽입하는 놈이 클 경우엔 둘을 change
                long temp = list.get(idx);
                list.set(idx,list.get(idx/2));
                list.set(idx/2, temp);
                
                
                //idx는 매번 절반씩 줄어야한다. 부모보다 작아서 올라갔으면 그에따른 idx도 업데이트해줘야함
                idx /= 2;
            }
        }
    }

11286: 절댓값 힙

두 수를 비교하는 방식만 다른것이지 로직은 똑같다
위의 코드에서 compage이라는 메서드를띠로 정의하기만하면된다

public static class MinHeap{
        //중간 요소에 대한 삽입/삭제를 쉽게하기위해 배열말고 ArrayList를 선택해였다
        ArrayList<Long> list;
        MinHeap(){
            list = new ArrayList<>();
            //0은 기본적으로 추가한다
            list.add(0l);
        }
        public void add(long x){
            //일단넣고 올라간다
            list.add(x);
            //추가된 값의 idx번호는 size-1만큼의 값이다
            int idx = list.size()-1;//추가된값의 idx
            //만약에 idx/2가 더 크다면 부모가 더 크다는것이다.
            //부모가 더 크면안된다. 부모는 가장 작은값이여야한다.
            //그러므로 반복을 수행한다
            while(idx > 1 && getBig(list.get(idx), list.get(idx/2))==1 ){
                //부모 <-> list.get(idx)값을 교환한다
                long temp = list.get(idx);
                list.set(idx, list.get(idx/2));
                list.set(idx/2, temp);

                //그리고 부모는 현재자신이 된다
                idx/=2;

            }
        }
        //a,b중 만약 a가 크다면 -1을 return한다
        //만약 b가 크다면 1을 return한다
        //둘이같을 경우엔 0을 retur한다
        public int getBig(long a, long b){
            //절댓값이 크면 그 값이 크다고 한다
            if(Math.abs(a) > Math.abs(b)) return -1;
            else if(Math.abs(a) < Math.abs(b)) return 1;
            //여기까지 내려왔으면 절댓값이 같다는얘기다. 그 경우에는 실제값을 비교한다
            if(a > b) return -1;
            else if(a < b) return 1;
            return 0;
        }
        //가장 작은 수를 return하고 이를 삭제하는 작업을 처리한다
        public long getBig(){
            //list.size가 작으면 더이상 삭제할수없다
            //list는기본적으로 idx=1부터시작하기때문에 최소 llist.size는 2부터여야한다
            if(list.size()-1 <1) return 0;
            //가장첫값이 가장작은값일것이다
            long result = list.get(1);
            //가장첫값에 가장마지막값을 대입하고 마지막값을 삭제하므로써 첫값을 삭제시킨다
            //그리고 마지막값의 idx를 내리면서 다른값들과 비교한다. 그러면서 제자리를 찾아가게 만든다
            list.set(1,list.get(list.size()-1));
            list.remove(list.size()-1);
            //일단 root에 넣은 마지막값은 idx=1이되었다. idx=1부터시작한다
            int idx = 1;
            //idx*2의 범위를 사용해주는 이유는 반복문 첫줄부터 idx*2에 대한 요소에 접근하고있기땨문이다
            while(idx*2 < list.size()-1){
                //일단 왼쪽, 오른쪽 자식중에 왼쪽값을 가장 작다고 가정한다
                int minPos = idx*2;
                //왼쪽위치에 대한 실제 값을 min이라는 변수로 받는다
                long min = list.get(minPos);
                //만약 오른쪽 값이 유효하고, 오른쪽값이 더 작다면, min의 값을 오른쪽의 정보로 update시킨다
                if(idx*2+1<list.size()&& getBig(list.get(idx*2+1), min)==1){
                    minPos = idx*2+1;
                    min = list.get(minPos);
                }
                //만약 min이 더크다면, 이는 제대로 정렬된것이므로 반복을 종료한다
                if(getBig(list.get(idx), min)==1) break;

                
                //min이 더크지않은경우에는 교환을 시행해야한다. 그래서 min값과 지금 현재 값인 idx가가리키고있는 요소를 가리키고
                //idx의 값을 update해준다
                list.set(minPos, list.get(idx));
                list.set(idx, min);
                //매번 이거 두배하는데 두배하는게 아니라 자식 둘중 하나로 결정되는것이니 minPos를 넣어주어야한다
                idx = minPos;
            }



            return result;
        }
    }

5430: AC

import java.io.*;
import java.util.ArrayList;

public class Main{
    public static String AC(ArrayList<Integer> list , String str){
        //매번 뒤집을 필요없다. 변수를 추가하고 그 변수의 값에따라 앞에있는 요소를 삭제할지 뒤에있는 요소를 삭제할지
        //거꾸로 출력할지 그대로 출력할지를 판단할 수 있다
        boolean inOrder = true;
        //에러가 나는 경우에는 반복문을 종료시키고 출력을 한다
        boolean isError = false;
        //str의 한글자한글자씩 보고 판단한다
        for(int i=0;i<str.length();i++){
            //만약 거꾸로 돌리라는 명령이있으면 inorder을 기존값의 반대되는 값을 넣어준다
            if(str.charAt(i)=='R') inOrder= !inOrder;
            if(str.charAt(i)=='D'){
                //비어있는데 pop을할순없다. 이 경우에 error가 난다
                if(list.isEmpty()) {
                    isError = true;
                    //에러가났는데 더이상진행할수없다. 반복문을끝내자
                    break;
                }
                //만약 현재 상태가 inorder(순서대로)라면 첫번째를 제거해준다
                if(inOrder) {
                    list.remove(0);
                }
                //만약 현재 상태가 !inorder(역순)이라면 마지막 요소를 제거해준다
                else {
                    list.remove(list.size()-1);
                }
            }
        }
        if(isError) return "error";
        //만약 error가 안났을 경우에 출력하는 부분이다
        else{
            //str에 추가/삭제연산은 비용이 크기때문에 stringBuilder를 사용해주었다
            String result = "[";
            StringBuilder sb = new StringBuilder(result);
            //순서대로라면 그대로 출력하면된다
            if(inOrder){
                for (Integer i : list) {
                    sb.append(i+",");
                }
            }
            else{
                for(int i=list.size()-1;i>=0;i--){
                    sb.append(list.get(i)+",");
                }
            }

            //아래조건문을빠뜨려서 오류가 났었다
            //만약길이가 1이라면 위의 , 을 추가하는 코드를 타지않을것이고
            //그렇다면 제거해주어야하는 문자열도없는것이다
            if(sb.length()>1) sb.deleteCharAt(sb.length()-1);
            //계속해서 , 이추가된경우 위의 명령처럼 마지막 문자를 제거해주는 작업을 해주어야한다
            sb.append("]");
            return sb.toString();
        }
    }
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int n = Integer.parseInt(br.readLine());

        for(int i=0;i<n;i++){
            String str = br.readLine();
            int m = Integer.parseInt(br.readLine());
            String temp = br.readLine();
            String input[] = temp.substring(1, temp.length()-1).split(",");
            ArrayList<Integer> list = new ArrayList<>();
            for(int k=0;k<m;k++){
                list.add(Integer.parseInt(input[k]));
            }
            bw.write(AC(list,str) + "\n");
        }


        bw.flush();
        bw.close();
    }


}

1914: 하노이탑

시도1

public static void hanoi(int start, int end, int n){
        if(n==1) {
            System.out.println(start + " " + end);
            return;
        }
        hanoi(1, 2, n-1);
        System.out.println("1 3");
        //1 -> 3으로 1개를 옮긴다
        hanoi(2, 3,n-1);
    }

• 이런식으로 하면 2->3으로 이동해야하는건데도 1->2 2->3을 거친다

정답

  public static void hanoi(int from, int to, int via, int n){
        if(n==1) {
            System.out.println(from + " " + to);
            return;
        }
        //1->2로 이동
        hanoi(from, via, to, n-1);
        System.out.println(from + " " + to);
        //1 -> 3 이동
        hanoi(via, to, from, n-1);
    }

2630: 색종이만들기

힌트

• 재귀
• 4등분
• x,y,size를 넘겨서 푼다

코드

import java.io.*;
import java.math.BigInteger;
import java.util.ArrayList;

public class Main{
    //어차피 일회용으로만 사용할것이기때문에, 그리고 매번 넘겨주는것보단 차라리 전역변수로 정의해주는것이 이해하기 더 쉬움
    //blue칸의개수를 셀 blue라는 변수
    static int blue = 0;
    //하얀박스를 셀 white라는 변수
    static int white = 0;
    //모두 white나 blue로 채워져있으면 true를 return하고 그렇지않으면 false를 return한다
    //false를 return한 경우, 더 쪼개야함을 의미한다
    public static boolean all(int x, int y, int size, boolean[][] isBlue){
        //all blue를 의미하는 변수
       boolean allB = true;
       //all white를 의미하는 변수
       boolean allW = true;
       
        //x,y로 시작해서 오른쪽으로 size만큼, 아래쪽으로만큼 size만큼의 박스가 있다고 가정하자
        //그리고 그 박스 내부의 요소에 접근해서 하나라도 blue가있으면 allwhite를 false처리,
        //하나라도 white가 있으면 allblue를 false처리해준다
        for(int i=x;i<x+size;i++){
           for(int k=y;k<y+size;k++){
               if(!isBlue[i][k]) {
                   allB = false;
               }
               if(isBlue[i][k]){
                   allW = false;
               }
           }
       }
        //전역변수 ++
        if(allW) {
            white++;
        }
        if(allB) {
            blue++;
        }
        //return값은 더쪼개야함을 의미한다
        if(allB || allW) return true;
        else return false;
    }
    public static void solve(boolean[][] isBlue, int x, int y, int size){
        //x,y기준으로 오른쪽으로, 아래로 size만큼 큰 박스가 있다고 가정하고 이것이 all white or all blue일때 재귀함수를 멈춘다
        if(all(x,y,size, isBlue)){
            return;
        }
        //size를 반절로 줄여준다. 왜냐하면 all-blue, all-white가 아니기때문이다
        size /= 2;
        //사분면을 모두 조사한다
        solve(isBlue, x, y, size);
        solve(isBlue, x+size,y,size);
        solve(isBlue, x,y+size,size);
        solve(isBlue, x+size,y+size,size);

    }
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int n = Integer.parseInt(br.readLine());
        boolean isBlue[][] = new boolean[n][n];
        for(int i=0;i<n;i++){
            String input[] = br.readLine().split(" ");
            for(int k=0;k<n;k++){
                if(input[k].equals("1")) isBlue[i][k] = true;
            }
        }
        solve(isBlue, 0,0, n);
        bw.write(white+"\n");
        bw.write(blue+"\n");
        bw.flush();
        bw.close();
    }


}