Solve003

문제번호: 2630(색종이 만들기)

• 문제링크
• 깃허브

풀이

1. 0, 0, n을 시작으로 해당 구역에 서로 다른 값이 들어가 있는지 확인한다
2. 만약 다른 값이 들어가 있다면 재귀를 이용해서 4분할을 해준다
   • 이때 재귀함수를 호출하면 그 다음 반복문을 실행하면 안되므로 return으로 해당 함수 종료
3. 그 후에 해당 구역이 파란색인지 하얀색인지 구분해주기 위해 flag를 사용해서 각각 카운팅

public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static int[][] arr;
    static boolean flag;
    static int white = 0;
    static int blue = 0;

    public static void main(String[] args) throws IOException {
        int n = Integer.parseInt(br.readLine());
        arr = new int[n][n];
        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            for (int j = 0; j < n; j++) {
                arr[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        recur(0, 0, n);
        System.out.println(white);
        System.out.println(blue);
    }

    static void recur(int x, int y, int n) {
        for (int i = x; i < x + n; i++) {
            for (int j = y; j < y + n; j++) {
                if (arr[i][j] != arr[x][y]) {
                    recur(x, y, n / 2);
                    recur(x + n / 2, y, n / 2);
                    recur(x, y + n / 2, n / 2);
                    recur(x + n / 2, y + n / 2, n / 2);

                    return;
                }
                if(arr[i][j] == 1){
                    flag = true;
                }
                else if(arr[i][j] == 0){
                    flag = false;
                }
            }
        }
        if (flag == true)
            blue++;
        else
            white++;
    }
}

문제번호: 1927(최소 힙)

• 문제링크
• 깃허브

풀이

1. 처음에 ArrayList를 선언해서 0이 아닌 수가 들어올때 정렬을 해주었다.
   • 시간초과 발생
2. priorityqueue를 이용하면 큐에 입력될때마다 오름차순으로 자동으로 정렬이 된다.

public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
//    static ArrayList<Integer> arr = new ArrayList<>();
    static PriorityQueue<Integer> arr = new PriorityQueue<>();

    public static void main(String[] args) throws IOException {
        int n = Integer.parseInt(br.readLine());
        for (int i = 0; i < n; i++) {
            int x = Integer.parseInt(br.readLine());
            if (x != 0) {
                arr.add(x);
            } else {
                if (arr.isEmpty()) {
                    System.out.println(0);
                } else {
                    System.out.println(arr.poll());
                }
            }
        }
    }
}

문제번호: 11279(최대 힙)

• 문제링크
• 깃허브

풀이

최소 힙 풀이
1. 처음에 ArrayList를 선언해서 0이 아닌 수가 들어올때 정렬을 해주었다.
- 시간초과 발생
2. priorityqueue를 이용하면 큐에 입력될때마다 오름차순으로 자동으로 정렬이 된다.

• 최소 힙 풀이에서 priorityqueue의 우선순위를 정반대로 해주면 내림차순으로 정렬이 된다.

public class boj_1927 {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
//    static ArrayList<Integer> arr = new ArrayList<>();
    static PriorityQueue<Integer> arr = new PriorityQueue<>(Comparator.reverseOrder());

    public static void main(String[] args) throws IOException {
        int n = Integer.parseInt(br.readLine());
        for (int i = 0; i < n; i++) {
            int x = Integer.parseInt(br.readLine());
            if (x != 0) {
                arr.add(x);
            } else {
                if (arr.isEmpty()) {
                    System.out.println(0);
                } else {
                    System.out.println(arr.poll());
                }
            }
        }
    }
}

문제번호: 9095(1, 2, 3 더하기)

• 문제링크
• 깃허브

풀이

• DP 문제는 일단 앞의 항들과의 연관성을 찾아보자.

1. 1일때 = 1
2. 2일때 = 2
3. 3일때 = 4
4. 4일때 = 7
5. 5일때 = 13

앞의 세개의 값을 더하면 구하고자 하는 index의 값을 구할 수 있다.

public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static int[] result;

    public static void main(String[] args) throws IOException {
        int n = Integer.parseInt(br.readLine());
        result = new int[11];
        result[1] = 1;
        result[2] = 2;
        result[3] = 4;

        for(int i = 4; i < 11; i++){
            result[i] = result[i - 3] + result[i - 2] + result[i - 1];
        }

        for(int i = 0; i < n; i++){
            System.out.println(result[Integer.parseInt(br.readLine())]);
        }
    }
}

문제번호: 1780(종이의 개수)

• 문제링크
• 깃허브

풀이

1. 삼등분씩 하면서 해당 종이에 동일한 숫자가 있을때까지 반복해야 하므로 재귀를 사용한다.
   • (0, 0)부터 시작해서 숫자가 다르다면 n/3을 더해주면서 가로 세로 3등분씩 한다.
2. 재귀를 완료한 후에 해당 종이에 적혀있는 숫자를 판별해서 minus, zero, plus 변수에 각각 더해준다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class boj_1780 {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static int[][] arr;
    static int flag = 0;
    static int minus = 0;
    static int zero = 0;
    static int plus = 0;

    public static void main(String[] args) throws IOException {
        int n = Integer.parseInt(br.readLine());
        arr = new int[n][n];
        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            for (int j = 0; j < n; j++) {
                arr[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        recur(0, 0, n);
        System.out.println(minus);
        System.out.println(zero);
        System.out.println(plus);
    }

    static void recur(int x, int y, int n) {
        for (int i = x; i < x + n; i++) {
            for (int j = y; j < y + n; j++) {
                if (arr[i][j] != arr[x][y]) {
                    recur(x, y, n / 3); // 첫번째 조각
                    recur(x + n / 3 , y, n / 3); // 두번째 조각
                    recur(x + 2 * (n / 3), y, n / 3); // 세번째 조각
                    recur(x, y + n / 3, n / 3); // 4
                    recur(x + n / 3, y + n / 3, n / 3); // 5
                    recur(x + 2 * (n / 3), y + n / 3, n / 3); // 6
                    recur(x, y + 2 * (n / 3), n / 3); // 7
                    recur(x + n / 3, y + 2 * (n / 3), n / 3); // 8
                    recur(x + 2 * (n / 3), y + 2 * (n / 3), n / 3);// 9

                    return;
                }
                if(arr[i][j] == -1){
                    flag = -1;
                }
                else if(arr[i][j] == 0){
                    flag = 0;
                }
                else if(arr[i][j] == 1){
                    flag = 1;
                }
            }
        }
        if (flag == -1)
            minus++;
        else if (flag == 0)
            zero++;
        else if (flag == 1)
            plus++;
    }
}

문제번호: 1620(나는야 포켓몬 마스터 이다솜)

• 문제링크
• 깃허브

풀이

1. Hashmap을 이용해서 포켓몬 이름과 번호를 쌍으로 다 저장한다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.StringTokenizer;

public class boj_1620 {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static HashMap<String, String> mon;

    public static void main(String[] args) throws IOException {
        st = new StringTokenizer(br.readLine());
        int x = Integer.parseInt(st.nextToken());
        int y = Integer.parseInt(st.nextToken());
        mon = new HashMap<>();
        for (int i = 0; i < x; i++){
            String monster = br.readLine();
            mon.put(monster, String.valueOf(i + 1));
            mon.put(String.valueOf(i + 1), monster);
        }
        solution(y);
    }

    public static void solution(int y) throws IOException{
        for(int i = 0; i < y; i++){
            System.out.println(mon.get(br.readLine()));
        }
    }

}

문제번호: 1149(RGB거리)

• 문제링크
• 깃허브

풀이

1. 첫번째 index부터 시작해서 바로 이전 index에서 고를 수 있는 최소값을 r, g, b에 모두 더해준다
   • 첫번째에서 r을 골랐다면 이전 index에서는 g, b 중에 최소값을 골라서 r에 더해준다.
2. 만약 0번째 index에서 g, 1번째 index에서는 r을 골랐을 시에 2번쨰 index에서는 r을 고르지 않으면 된다.
3. 이런식으로 index가 증가할때마다 각각의 cost를 더해주면 최종 index에서 여러가지 선택지의 가장 최소 cost가 나타나게 된다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class boj_1149 {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static int[][] arr;

    public static void main(String[] args) throws IOException {
        int T = Integer.parseInt(br.readLine());

        arr = new int[T][3];
        for (int i = 0; i < T; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            for (int j = 0; j < 3; j++) { //red:0 ,green:1, blue:2
                arr[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        System.out.println(solution(T));
    }

    static int solution(int T) {
        for (int i = 1; i < T; i++) {
            arr[i][0] += Math.min(arr[i - 1][1], arr[i - 1][2]);
            arr[i][1] += Math.min(arr[i - 1][0], arr[i - 1][2]);
            arr[i][2] += Math.min(arr[i - 1][0], arr[i - 1][1]);
        }
        int min = Integer.MAX_VALUE;
        for (int i = 0; i < 3; i++) {
            if (min > arr[T - 1][i]) {
                min = arr[T - 1][i];
            }
        }
        return min;
    }
}

문제번호: 1932(정수 삼각형)

• 문제링크
• 깃허브

풀이

1. 1149 문제와 흡사하게 첫번째 인덱스부터 처리해준다.
2. 1번째 index는 요소가 2개고 0번째는 1개 이므로 해당 index에서 가장 처음과 끝 인덱스는 더할 수 있는 값이 한개 밖에 없다.
3. 조건문으로 해당 요소는 하나씩만 더해지도록 처리를 하고, 나머지 가운데에서 두 개의 요소중 최대값을 골라서 더해주도록 한다.

public class boj_1932 {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static ArrayList<Integer>[] arr;

    public static void main(String[] args) throws IOException {
        int T = Integer.parseInt(br.readLine());
        arr = new ArrayList[T];

        for (int i = 0; i < T; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            arr[i] = new ArrayList<>();
            while (st.hasMoreTokens()) {
                arr[i].add(Integer.parseInt(st.nextToken()));
            }
        }

        System.out.println(solution(T));
    }

    static int solution(int T) {
        for (int i = 1; i < T; i++) {
            for (int j = 0; j < i + 1; j++) {
                if (j == 0) {
                    arr[i].set(j, arr[i - 1].get(j) + arr[i].get(j));
                }
                else if (j == i) {
                    arr[i].set(j, arr[i - 1].get(j - 1) + arr[i].get(j));
                }
                else {
                    arr[i].set(j, Math.max(arr[i - 1].get(j - 1), arr[i - 1].get(j)) + arr[i].get(j));
                }
            }
        }

        int max = Integer.MIN_VALUE;
        for (int i = 0; i < T; i++) {
            if (max < arr[T - 1].get(i)) {
                max = arr[T - 1].get(i);
            }
        }
        return max;
    }
}

문제번호: 프로그래머스 Summer/Winter Coding(2018) 숫자게임

• 문제링크
• 깃허브

풀이

1. 상대를 최소의 값차이로 이길 수 있어야 한다고 생각해서 일단 정렬 시킨다.

2. A의 인덱스를 0으로 잡고 B의 인덱스는 모두 탐색하며 현재 A의 인덱스 값보다 큰 B값을 찾으면 A의 인덱스를 하나씩 올린다.

import java.util.*;

class Solution {
    public int solution(int[] A, int[] B) {
        int answer = 0;
        int cnt = 0;
        int a_index = 0;

        Arrays.sort(A);
        Arrays.sort(B);

        for(int i = 0; i < A.length; i++){
            if(A[a_index] < B[i]){
                a_index++;
                answer++;
            }
        }
        return answer;
    }
}

문제번호: 프로그래머스 Summer/Winter Coding(2018) 점프와 순간이동

• 문제링크
• 깃허브

오답 풀이

1. N+1만큼의 배열을 생성한다음, arr[1]의 값은 1로 세팅한다.
2. 반복문을 arr[2]부터 돌며 체크한다
   • 인덱스가 짝수면 해당 인덱스/2의 값을 가져온다
   • 인덱스가 홀수면 (해당 인덱스에서 1을 빼준 값)/2의 값을 가져온다.
     
     

이 방식으로 테스트를 하면 정확도 테스트는 통과하지만 효율성 테스트를 통과할 수 없다.

풀이

1. 오답 풀이와 반대로 n의 값부터 체크한다.

   • 짝수면 2로 계속 나눈다.
   • 홀수가 되면 1을 빼준다.
     • 빼준다는것은 점프를 했다는 의미이므로 ans에 1씩 더해준다.

2. n이 0이 될때까지 반복한다.

import java.util.*;

public class Solution {
    public int solution(int n) {
        int ans = 0;
        
        while(n != 0){
            if(n % 2 == 0){
                n /= 2;
            }
            else{
                n -= 1;
                ans++;
            }
        }
        
        return ans;
    }
}