Rabbit blog

Rabbit blog
0%

Posted on Edited on In , ,

문제정의

문자열 x에 대한 이진변환을 1이 될 때까지 시행한다. 이진 변환은 아래와 같이 정의한다. 1. x의 모든 0을 제거한다. 2. x의 길이를 c라 하면, x를 c를 2진법으로 표현한 문자열로 바꾼다.

시행 뒤에 시행 횟수와 제거된 0의 개수를 반환하면 된다.

문제풀이

전체 코드는 다음과 같다. 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
package level2;

public class RepeatBinary {

    //프로그래머스 문제풀이 level2 이진 변환 반복하기
    public static void main(String[] args) {
        String s = "110010101001";
        int[] answer = new int[2];
        int cnt = 0, l, zero = 0;
        while(!s.equals("1"))
        {
            cnt++;
            l = s.length();
            s = s.replace("0", "");
            zero += l - s.length();
            s = Integer.toBinaryString(s.length());
        }
        answer[0] = cnt;
        answer[1] = zero;
    }
    
}
cnt는 반복횟수이고, zero는 제거된 0의 개수이다. 문자열이 1이 될 때까지 cnt를 1씩 늘려가며 2진변환을 반복한다. 0의 개수를 세기 위해 문자열에서 0을 제거하고, 그전 문자열의 길이에서 1번과정을 거친 문자열의 길이를 제거한 값을 더한다. 그리고 2번과정을 시행한다.

시간복잡도를 정하기엔 애매한 부분이 있다. 0이 몇개나 생길지 모르기 때문에 절대적으로 얼마나 n이 커질지 단정짓기가 힘들다. 더 공부가 필요하다.

테스트



Posted on Edited on In , ,

문제정의

한 자연수에 대해 연속한 자연수의 합으로 나타낼 수 있는 경우의 수를 구하는 문제이다.

문제풀이

전체 코드는 다음과 같다. 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
package level2;

public class ExpressNum {

    //프로그래머스 문제풀이 level2 숫자의 표현
    public static void main(String[] args) {
        int n = 15;
        int answer = 0;
        int add = 1, sub = 1, sum = 0;
        while(add <= n)
        {
            sum += add++;
            while(sum > n)
            {
                sum -= sub;
                sub++;
            }
            if(sum == n)
                answer++;
            
        }
        System.out.println(answer);
    }
    
}
자칫 경우의 수가 많아 보일 수 있지만 생각해보면 연속한 숫자라는 것이 도움이 된다. 1부터 차례대로 더해가며 n에 딱 맞을 경우 answer를 늘려주면 되고, 만약 n을 초과했다면 뒤에서부터 작아지거나 같아질 때까지 빼주면 된다.

최종 시간복잡도는 숫자를 빼고 더하는 최대 횟수가 2n이므로 \(O(n)\)이다.

테스트



Posted on Edited on In ,

문제정의

폰켓몬의 갯수 중 절반을 가져갈 수 있을 때, 최대로 가져갈 수 있는 폰켓몬의 종류를 반환하는 문제이다. 같은 종류의 폰켓몬은 같은 자연수 값을 갖는다.

문제풀이

전체 코드는 다음과 같다. 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
package level2;

import java.util.HashMap;

public class Ponketmon {

    //프로그래머스 문제풀이 level2 폰켓몬
    public static void main(String[] args) {
        int[] nums = {3, 1, 2, 3};
        int answer = 0;
        HashMap<Integer, Integer> map = new HashMap<>();
        for(int n : nums)
        {
            map.put(n, map.getOrDefault(n, 0)+1);
        }
        if(map.size() < nums.length/2)
            answer = map.size();
        else
            answer = nums.length/2;

        System.out.println(answer);
    }
    
}
필자는 맵을 활용하여 문제를 풀었다. 종류마다 폰켓몬이 몇 마리가 있는지 센 다음에, 종류가 폰켓몬의 종류의 절반보다 작으면 맵의 사이즈를 반환하고 아닌 경우, 전체 폰켓몬 수의 절반을 답으로 하였다.

최종 시간복잡도는 \(O(n)\)이다.

테스트



Posted on Edited on In , ,

문제정의

어떠한 자연수 n이 주어질 때 다음으로 큰 숫자를 찾으면 된다. 다음으로 큰 숫자에 대한 조건은 3가지를 만족해야 한다. 1. n보다 커야 한다. 2. n과 해당 수를 이진수로 바꿨을 때, 1의 개수가 같아야 한다. 3. 1과 2를 동시에 만족하는 가장 작은 수여야 한다.

문제풀이

전체 코드는 다음과 같다. 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
package level2;

public class NextBigNum {

    //프로그래머스 문제풀이 level2 다음 큰 숫자

    public static void main(String[] args) {
        int n = 78;
        int answer = n;
        int one = 0, t_one = 0;
        String binary = Integer.toBinaryString(n);
        char[] arr = binary.toCharArray();
        for(char c : arr)
        {
            if(c == '1')
                one++;
        }
        while(one != t_one)
        {
            answer++;
            t_one = 0;
            String temp = Integer.toBinaryString(answer);
            char[] t_arr = temp.toCharArray();
            for(char c : t_arr)
            {
                if(c == '1')
                    t_one++;
            }
        }
        System.out.println(answer);
    }
    
}

풀이는 간단하다 n에서 1씩 늘려가며 1의 개수를 비교하며 같아질 때 답을 출력하는 것이다.

여기서 시간복잡도를 계산하기가 굉장히 애매한데 1이 같아지는 경우가 언제인지 잘 모르겠기 때문이다. 이 부분에서는 더 공부가 필요하다.

테스트



java에 bitCount로 1을 세주는 함수가 있었다. 자바에는 무궁무진한 메소드의 세계가 있는 것 같다.

Posted on Edited on In , ,

문제정의

열린괄호와 닫힌괄호로 이루어진 문자열이 올바른 괄호식인지 확인하는 문제이다. 올바른 괄호식이란 열린 괄호와 닫힌 괄호의 수가 동일해야 하며, 열렸으면 반드시 닫혀야한다.

문제풀이

전체 코드는 다음과 같다. 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
package level2;

public class CorrectBracket {

    //프로그래머스 문제풀이 level2 올바른 괄호

    public static void main(String[] args) {
        String s = "()()";
        boolean answer = true;
        int open = 0, close = 0;
        char[] arr = s.toCharArray();
        for(char c : arr)
        {
            if(c == '(')
                open++;
            else
                close++;
            if(open < close)
            {
                answer = false;
                break;
            }
        }
        if(open != close)
            answer = false;
            
        System.out.println(answer);
    }
    
}
열린괄호의 개수를 저장할 변수 open과 닫힌 괄호의 개수를 저장할 변수 close를 선언한다. 이들의 수를 세나가며 만약 close가 open보다 많아지는 경우면 모든 열린괄호가 짝지어지는 것이 아니므로 false를 반환한다. 반복문을 탈출했어도 열린괄호가 닫힌 괄호보다 많은 경우가 있으므로 이를 체크하기 위해 둘의 수가 동일한지 확인한다.

최종 시간복잡도는 문자열의 길이를 n이라 할 때, \(O(n)\)이다.

테스트



Posted on Edited on In , ,

문제정의

정사각형의 0,1로 이루어진 2차원 배열을 압축하는 문제이다. 정사각형 영역 S가 한숫자로만 이루어져 있으면 그 숫자로 압축할 수 있다. 만약 그렇지 않으면 4개의 정사각형으로 나누어 압축할 수 있는지 확인한다. 이 과정을 반복했을 때 0의 개수와 1의 개수를 배열로 담아 반환하면 된다.

문제풀이

전체 코드는 다음과 같다. 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
package level2;

public class QuadCompress {

    //프로그래머스 문제풀이 level2 쿼드압축 후 개수 세기
    public static void main(String[] args) {
        int[][] arr = {
            {1,1,0,0},
            {1,0,0,0},
            {1,0,0,1},
            {1,1,1,1}
        };
        int[] answer = new int[2];
        answer[0] = ReturnCnt(0, arr.length-1, 0, arr.length-1, arr, 0);
        answer[1] = ReturnCnt(0, arr.length-1, 0, arr.length-1, arr, 1);
    }
    public static int ReturnCnt(int start_r, int end_r, int start_c, int end_c, int[][] arr, int comp_num)
    {
        if(start_r == end_r)
            return arr[start_r][start_c] == comp_num ? 1 : 0;
        else
        {
            boolean canCompress = true;
            for(int r = start_r; r <= end_r; r++)
            {
                for(int c = start_c; c <= end_c; c++)
                {
                    if(arr[r][c] != comp_num)
                        canCompress = false;
                }
            }
            if(canCompress)
                return 1;
            
            int middle_r = (end_r-start_r)/2 + start_r;
            int middle_c = (end_c-start_c)/2 + start_c;
            int first = 0, sec = 0, third = 0, fourth = 0;
            first += ReturnCnt(start_r, middle_r, start_c, middle_c, arr, comp_num);
            sec += ReturnCnt(start_r, middle_r, middle_c+1, end_c, arr, comp_num);
            third += ReturnCnt(middle_r+1, end_r, start_c, middle_c, arr, comp_num);
            fourth += ReturnCnt(middle_r+1, end_r, middle_c+1, end_c, arr, comp_num);
            
            return first+sec+third+fourth;
            
            
            
        }    
        
    }
    
}
전형적인 리컬시브를 활요하는 문제이다. 필자는 0이나 1이 몇개인지 알려주는 함수 ReturnCnt를 만든 뒤, 0의 개수와 1의 개수를 각각 구하였다. 함수의 매개변수로는 사각형의 시작행과 열, 끝행과 열을 알기 위해 start_r, end_r, start_c, end_c로 선언했다. comp_num은 0 또는 1이 들어간다. 압축하는 숫자가 무엇인지 알려주는 역할이다. 리컬시브 함수가 종료되는 순간은 가로 세로가 1인 정사각형이 들어왔을 때이다. 첫행과 끝행이 같을 때가 이 경우 이므로, 이때 비교하는 수가 comp_num과 같으면 1을 그렇지 않으면 0을 반환한다. 다른 종료조건으로는 영역 전체가 comp_num으로 이루어진 경우이다. 이 조건은 2중 루프를 통해 파악한다. 이 모두가 아니라면 영역을 4개로 쪼개어 확인해야한다. 영역을 쪼개기 위해 정사각형을 쪼개는 가운데 점을 찾아야하는데 그건 35-36번째 줄을 참고하길 바란다. 이렇게 만들어진 중간열과 행을 middle_r과 middle_c로 선언한다. 다음에 자른 영역으로 함수를 재호출하여 4개의 영역값을 모두 더하여 반환한다.

시간복잡도에 대해 고민을 해보았는데, 최악의 경우는 단 하나도 압축이 안되는 경우이다. 일단 함수가 쪼개지는 횟수는 정사각형의 한 변의 길이를 \(n(n \ge 2)\)일 때, 등비수열의 합 공식에 의해 \(4*(4^n-1)\over(4-1)\)번이다. 쪼개진 영역들을 검사하는 횟수를 다 합하면 한번에 \(n^2\)이다. 따라서 총 시간복잡도는 \(O(n^2*4^n)\)이다.

테스트



이번 문제는 시간복잡도를 계산하는 것이 까다로웠다. 이제 재귀에 익숙해져 가는 것 같아 뿌듯하다.

Posted on Edited on In , ,

문제정의

자연수 배열이 주어지고, 이 수들을 적절히 더하거나 빼서 타겟 넘버를 만들 수 있는 경우의 수를 구하는 문제이다.

문제풀이

전체 코드는 다음과 같다. 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
package level2;

public class TargetNumber {

    //프로그래머스 문제풀이 level2 타겟 넘버
    
    public static void main(String[] args) {
        int[] numbers = {1,1,1,1,1};
        int target = 3;
        int answer = 0;
        answer = ReturnAnswer(numbers, 0, target, 0);
        System.out.println(answer);
    }
    public static int ReturnAnswer(int[] numbers, int n, int target, int idx)
    {
        if(n == target && idx == numbers.length)
            return 1;
        else
        {
            if(idx == numbers.length)
                return 0;
            else
            {
                int plus = 0, minus = 0;
                plus += ReturnAnswer(numbers, n+numbers[idx], target, idx+1);
                minus += ReturnAnswer(numbers, n-numbers[idx], target, idx+1);
                return plus+minus;
            }
        }
    }
    
}
이 문제가 왜 dfs인지 한참 고민했는데, 생각해보니 분기를 두개로 나누어가면서 탐색해 나가는 것으로 생각할 수 있다는 결론이 났다. 이를 리컬시브를 통해 구현하였다. 만약 배열의 끝에 도달했을 때 n이 타겟 넘버라면 1을 반환한다. 만약 끝에 도달해도 타겟 넘버를 만들지 못했다면 0을 반환한다. 아직 배열의 끝에 도달하지 않은 경우면 현재 있는 인덱스의 숫자를 더하거나 빼는 두 개의 분기를 만들어 이 둘의 합을 반환한다.

이 문제의 시간복잡도는 \(O(2^n)\)이다.

테스트



Posted on Edited on In , ,

문제정의

카펫의 모양이 노란색이 중앙 그 테두리를 갈색이 감싸는 형태이다. 갈색과 노란색 타일이 주어질 때 이 카펫의 모양을 만들기 위한 가로, 세로의 길이를 구하는 문제이다.

문제풀이

전체 코드는 다음과 같다. 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
package level2;

public class Carpet {

    //프로그래머스 문제풀이 level2 카펫

    public static void main(String[] args) {
        int brown = 10;
        int yellow = 2;
        int[] answer = new int[2];
        int sum = (brown+4)/2;
        int h = 3, w = sum -3;
        while(w >= h)
        {
            if((h-2)*(w-2) == yellow)
            {
                answer[0] = w;
                answer[1] = h;
                break;
            }
            h++;
            w--;
        }
    }
    
}
가로 세로 길이를 합친 길이를 sum이라 할 때, 다음과 같이 구할 수 있다. 이 식은 가로x세로-4가 갈색 타일의 합인 식에서 유도했다. 문제에서 yellow는 1이상이므로 가로와 세로길이는 최소 3이상이어야 한다. 따라서 초기 세로의 길이는 3, 가로의 길이는 sum -3으로 한다. 다음으로는 while문을 돌면서 노란타일을 구한다. 노란타일의 수는 사각형 넓이에서 겉 테두리 영역을 제외한 것이므로 각각의 길이에 -2를 하여 구한다. 이 수가 문제에 주어진 노란타일의 수와 일치하면 가로와 세로 값을 배열에 담아 반환한다.

이 문제의 시간복잡도는 w의 초기 길이를 n이라 할 때, \(O(n)\)이다.

테스트



Posted on Edited on In , ,

문제정의

최대 2명까지 탈 수 있고 무게 제한이 limit인 구명보트를 최대한 적게 사용해서 사람들을 보트에 태우는 문제이다.

문제풀이

전체 코드는 다음과 같다. 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
package level2;

import java.util.Collections;
import java.util.PriorityQueue;

public class LifeBoat {

    //프로그래머스 문제풀이 level2 구명보트
    public static void main(String[] args) {
        int[] people = {70, 50, 80, 50};
        int limit = 100;
        int answer = 0;
        PriorityQueue<Integer> small = new PriorityQueue<>();
        PriorityQueue<Integer> big = new PriorityQueue<>(Collections.reverseOrder());
        for(int w : people)
        {
            if(w <= limit/2)
                small.add(w);
            else
                big.add(w);
        }
        while((!small.isEmpty()) && (!big.isEmpty()))
        {
            int s = small.peek();
            int b = big.peek();
            if(s+b > limit)
            {
                big.remove();
                answer++;
            }
            else
            {
                small.remove();
                big.remove();
                answer++;
            }
        }
        if(!small.isEmpty())
            answer += small.size() % 2 == 0 ? small.size()/2 : small.size()/2+1;
        else
            answer += big.size();

        System.out.println(answer);
    }
    
}

정렬을 사용할 수 있고 우선순위큐를 활용할 수도 있지만, 필자는 우선순위 큐를 활용하였다. 15-21번째 줄은 limit/2를 기준으로 작은것과 큰 것으로 무게를 나눠담는 과정이다. small은 오름차순으로 정렬하고 big은 내림차순으로 정렬한다. 22-37번째 줄은 두 큐에서 사람을 하나씩 뽑아 보트에 태울 수 있는지 보는것이다. 만약 태우지 못한다면 큰 사람 하나를 보트에 태워보내고, 다음으로 무거운 사람을 같이 태울 수 있는지 비교한다. 만약 같이 탈 수 있으면 둘 다 큐에서 제거하고 answer를 1증가한다. 반복문을 탈출하는 경우는 두 큐 모두 비었거나, 둘 중 하나만 빈 것이므로 이에 대한 나머지 처리도 해야한다. 만약 small이 남은 경우 무조건 둘씩 태워 보낼 수 있으므로 (small 총 개수)/2를 한다. 이때 홀수명이 남는다면 1을 추가하는 것을 잊지말자. big에 속한 사람들은 한 사람씩 밖에 못 타므로 사람수만큼 추가해주면 된다.

우선 순위 큐를 활용했으므로 총 시간복잡도는 \(O(nlogn)\)이 된다.

테스트



처음에 40번째 줄에 else가 아니라 else if문을 썼는데 효율성 테스트를 하나 통과하지 못했다. 그래서 else로 바꾸니 통과가 되었다. size를 한번 더 호출하냐 마냐가 차이인 것 같은데, 효율성 테스트가 조금 빡빡하단 생각이 들었다.

Posted on Edited on In , ,

문제정의

스파이가 위장을 하려고 한다. 옷이 종류별로 있을 때, 적어도 하나의 의상은 입고 있어야 한다. 하지만 같은 종류의 옷을 겹쳐입을 순 없다. 이 때, 스파이가 옷을 입을 수 있는 경우의 수를 구하라.

문제풀이

전체 코드는 다음과 같다. 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
package level2;

import java.util.HashMap;
import java.util.Iterator;

public class Disguise {

    //프로그래머스 문제풀이 level2 위장

    public static void main(String[] args) {
        int answer = 0;
        String[][] clothes =
        {
            {"yellow_hat", "headgear"},
            {"blue_sunglasses", "eyewear"},
            {"green_turban", "headgear"}
        };
        HashMap<String, Integer> map = new HashMap<>();
        for(int i = 0; i < clothes.length; i++)
            map.put(clothes[i][1], map.getOrDefault(clothes[i][1], 0)+1);
        
        int comb_max = map.size();
        int[] clothes_num = new int[comb_max];
        
        Iterator<String> keys = map.keySet().iterator();
        int idx = 0;
        while(keys.hasNext())
        {
            String key = keys.next();
            clothes_num[idx++] = map.get(key);
            
        }
        
        int comb_cnt = 1;
        while(comb_cnt <= comb_max)
        {
            answer += getCombNum(clothes_num, comb_cnt, 1, 0);
            comb_cnt++;
        }
        System.out.println(answer);
    }
    public static int getCombNum(int[] arr, int k, int n, int idx)
    {
        if(k == 0)
            return n;
        else
        {
            int total = 0; 
            for(int i = idx; i <= arr.length-k; i++)
            {
                total += getCombNum(arr, k-1, n*arr[i], i+1);
            }
            return total;
        }
    }
}
코드가 좀 긴데 차근차근 보도록 하자. 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
HashMap<String, Integer> map = new HashMap<>();
for(int i = 0; i < clothes.length; i++)
    map.put(clothes[i][1], map.getOrDefault(clothes[i][1], 0)+1);

int comb_max = map.size();
int[] clothes_num = new int[comb_max];

Iterator<String> keys = map.keySet().iterator();
int idx = 0;
while(keys.hasNext())
{
    String key = keys.next();
    clothes_num[idx++] = map.get(key);
    
}

int comb_cnt = 1;
while(comb_cnt <= comb_max)
{
    answer += getCombNum(clothes_num, comb_cnt, 1, 0);
    comb_cnt++;
}
일단 옷의 종류를 key로 하여 종류별로 몇 벌의 옷이 있는지 map에 저장한다. 이 때 getOrDefault함수는 아주 유용하게 쓰인다 처음 들어가는 key이면 초기화를 해주고 아닐 경우 해당 값의 1증가한 값을 넣어준다. 필자의 아이디어는 k개의 조합의 수를 구해다주는 함수가 있을 때, 1부터 옷의 모든 종류 수로 k를 늘려가면서 조합의 수를 다 더해주면 된다고 생각했다. 이 함수에 대한 세부 설명은 뒤로 미루고, clothes_num을 선언해 종류별 옷의 개수를 담아준다. 그리고 comb_cnt를 1부터 comb_max로 늘려주면서 getCombNum까지 조합의 수를 다 더해준다.

이제 함수를 보도록하자. 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public static int getCombNum(int[] arr, int k, int n, int idx)
{
    if(k == 0)
        return n;
    else
    {
        int total = 0; 
        for(int i = idx; i <= arr.length-k; i++)
        {
            total += getCombNum(arr, k-1, n*arr[i], i+1);
        }
        return total;
    }
}
조합의 수를 구해주는 함수이다 arr는 옷의 개수 k는 몇 개의 조합을 원하는지 알려주는 변수이다. n은 현재까지 계산된 조합의 수이며, idx는 arr에서 새로 시작해야하는 index이다. 종료 조건은 k가 0이 될 때이다. 종류개수를 전부 만족했으므로 여태까지 계산한 n을 반환하면 된다. 아닐 경우 조합을 만들어야 한다. total을 0으로 하고, idx부터 length-k까지 n에 arr[i]를 곱해 함수를 재호출한다. 이때 i의 범위가 이해가 잘 안 갈수도 있는데 만약 1,2,3,4,5가 들어간 배열이 있고 2개의 조합을 찾으려고 할 때, 앞에서부터 조합을 만들어간다고 가정하면 1,2,3,4가 가능하다. 여기서 3을 만약 선택했다면 그 다음 조합은 4,5중에 하나를 선택해야한다. 중복없는 모든 조합을 찾기 위한 방법이니 이 참에 잘 공부했으면 좋겠다.

필자는 처음에 이렇게 코드를 짜고 싶지 않았는데 왜냐하면 이렇게 프로그램을 짜는 경우 시간복잡도가 어마무시하게 늘어나기 때문이다. 옷의 종류가 총 n개라고 하고 k개를 선택한다고 하면 함수는 조합 수 만큼 호출되기 때문에 \(O(n^k)\)만큼 호출될 것이다. k의 최대값은 n이므로 결국 \(O(n^n)\)이 된다.

테스트



살인적인 시간복잡도를 보고 기겁을 할 수도 있는데, 다행히 통과는 했다. 일부러 1번 케이스를 보여줬는데, 통과는 되었다만 엄청난 시간복잡도를 자랑한다.. 다른 사람의 풀이를 보니 곱할 때 아무것도 선택하지 않은 것도 옵션으로 넣어 \(O(n)\)으로 끝내는 것을 보고 역시 수학을 잘해야 유리하다는 생각이 들었다. 아무튼 풀어냈지만, 수학 공부도 게을리 하지 말아야겠다.