Rabbit blog

Rabbit blog
0%

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
package level2;

import java.util.ArrayList;

public class PhoneBook {

    //프로그래머스 문제풀이 level2 전화번호 목록
    public static void main(String[] args) {
        String[] phone_book = {"119", "97674223", "1195524421"};
        boolean answer = true;
        ArrayList<ArrayList<String>> list = new ArrayList<ArrayList<String>>(10);
        for (int i = 0; i < 10; i++)
            list.add(new ArrayList<String>());
        for(String s : phone_book)
        {
            int idx = Integer.parseInt(s.substring(0,1));
            for(int i = 0; i < list.get(idx).size(); i++)
            {
                String comp = list.get(idx).get(i);
                if(s.indexOf(comp) == 0 || comp.indexOf(s) == 0)
                {
                    answer = false;
                    break;
                }
            }
            list.get(idx).add(s);
        }
        System.out.println(answer);
    }
    
}
해쉬를 활용하라고 해서 많이 고민했다. 딱 맞는 Key값을 찾는다는게 결국 접두어를 찾는것이기 때문이다. 고민을 하다 2중 for문을 통해 brute force를 해봤는데 효율성에서 나아지지 않았다. 그래서 시간을 조금이라도 줄여보고자 adjacency list를 활용했다. 0~9로 시작하는 번호들을 각각 저장할 10개의 list를 생성하고 그 안에서 비교하도록 했다.

실은 이것도 모두 같은 숫자로 시작하면서 서로 접두사가 아닌 케이스인 경우 결국 \(O(n^2)\)이다.

테스트



시간복잡도가 준 것은 아닌데 테스트를 통과해서 떨떠름하다. 다른 풀이를 보니 그냥 이중 포문을 사용해서 푼 경우도 있었다. 필자의 경우 indexOf를 했는데 그 분은 stratWith로 한 차이 밖에 없었다. 사용한 함수에 따라 달라질 수도 있다는건지,, 효율성을 평가하는 부분에서 약간 의아함이 들었다.

Posted on Edited on In , ,

문제정의

어떤 과학자의 H 인덱스를 구하는 문제이다. H 인덱스란 어떠한 학자가 발표한 논문 n편중에 h번이상 발표한 논문이 h편이상일 때 이 h의 최대값이다. 이해가 어려울 수도 있는데 그런 사람을 위해 질문하기에 있었던 링크를 첨부한다.

문제풀이

전체 코드는 다음과 같다. 

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
import java.util.*;

public class HIndex {

    //프로그래머스 문제풀이 level2 H-Index

    public static void main(String[] args) {
        int[] citations = {22, 42};
        int answer = 0;
        Arrays.sort(citations);
        for(int i = citations.length-1; i >= 0; i--)
        {
            if(citations.length-i >= citations[i])
            {
                answer = citations.length-i-1;
                break;
            }
        }
        if(citations[0] > citations.length)
            answer = citations.length;
        System.out.println(answer);

    }
    
}
필자의 경우 처음으로 h를 만족하지 않을 때를 찾아내어 그 값에 -1을 해주었다. 먼저 피인용수를 정렬한 뒤에, 피인용수보다 논문수가 많아지거나 같아지는 지점을 찾았다. 하지만 이렇게 짜면 문제점이 발생하는데 {22,42}와 같이 전부 만족하는 경우이다. 이 경우 가장 작은 피인용수가 논문 전체 수보다 큰 경우 이므로 이 때는 논문 수를 넣어주면 된다.

정렬을 사용하였으므로 최종 시간복잡도는 \(O(nlogn)\)이다.

테스트



실은 이 문제를 풀기전에 두 문제 정도 했었는데, 2시간 안에 둘다 풀지 못했다. 그리디는 나름 자신있다고 생각했는데, 새삼 겸손해진다. 나머지 레벨2 문제를 풀어보고 다시 도전해봐야겠다.

Posted on Edited on In , ,

문제정의

모든 음식이 스코빌 지수 k를 넘기게 하기 위해 맵지 않은 음식을 섞어서 더 맵게 만들려고 한다.

섞은 음식의 스코빌 지수 = 가장 맵지 않은 음식의 스코빌 지수 + (두 번째로 맵지 않은 음식의 스코빌 지수 * 2)

모든 음식을 K이상의 스코빌 지수로 만들려고 할 때 섞어야 하는 최소 횟수를 계산하는 문제이다. 만약 불가능하다면 -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
import java.util.*;

public class MoreSpicy {

    //프로그래머스 level2 문제풀이 더 맵게

    public static void main(String[] args) {
        int[] scoville = {1, 2, 3, 9, 10, 12};
        int K = 7;
        int answer = 0;
        boolean isPossible = true;
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        for(int food : scoville)
            pq.add(food);
        while(pq.size() > 1)
        {
            if(pq.peek() >= K)
            {
                isPossible = true;
                break;
            }
            else
            {
                Integer food1 = pq.poll();
                Integer food2 = pq.poll();
                pq.add(food1 + food2*2);
                answer++;
            }
            
        }
        if(pq.peek() < K)
            answer = -1;
        System.out.println(answer);
    }
    
}

이 문제는 우선순위 큐만 알면 쉽게 해결할 수 있다. 일단 모든 음식을 큐에 넣은 다음 맨 앞 음식을 확인하여 K미만 이라면 큐에서 두 음식을 꺼내 계산식에 넣은 결과를 다시 넣는다. 만약 가장 안 매운 음식이 K를 넘는다면 반복문을 탈출하고 else문에 들어간 횟수를 반환한다. 만약 모든 음식을 섞어도 스코빌 지수를 만족하지 못한다면 큐에는 하나의 음식만 남게 되고 while문 조건에 의해 반복문을 탈출한다. 큐에서 가장 안 매운 음식을 꺼냈을 때 K보다 작으므로 -1이 된다. 만약 모든 음식이 K를 넘는다면 answer은 0이 될 것이다.

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

테스트



질문하기를 둘러보니 직접 힙을 구현한 경우 통과가 안되고 라이브러리 힙을 사용해야 통과되는 경우가 더러 있었다고 한다. 이 부분에서는 효율성 평가 개선이 이루어져야 한다고 생각한다.

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
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
public class ConvertBracket {
    
    //프로그래머스 문제풀이 level2 괄호 변환
    
    public static void main(String[] args) {
        String p = "()))((()";
        String answer = "";

        if(isCorrectBracket(p))
            answer = p;
        else
            answer = ChangeBracket(p);

        System.out.println(answer);
    }
    public static boolean isCorrectBracket(String s)
    {
        char[] arr = s.toCharArray();
        int open = 0;
        int close = 0;
        for(char c : arr)
        {
            if(c == '(')
                open++;
            else
                close++;
            if(close > open)
                return false;
        }
        return true;
            
    }
    public static String ChangeBracket(String s)
    {
        //1. 입력이 빈 문자열인 경우 빈 문자열을 반환합니다.
        if(s.equals(""))
            return "";
        else
        {
            //2. u, v로 분리
            String u = "";
            String v = "";
            char[] arr = s.toCharArray();
            int open = 0;
            int close = 0;
            for(char c : arr)
            {
                if(c == '(')
                    open++;
                else
                    close++;
                if(open == close)
                    break;
            }
            int idx = open*2;
            u = s.substring(0, idx);
            if(idx < s.length())
                v = s.substring(idx);

            String temp = ChangeBracket(v);
            
            //3.u가 올바른 문자열일 경우
            if(isCorrectBracket(u))
                return u + temp;
            //4.u가 올바른 문자열이 아닐 경우
            else
            {
                StringBuilder buff = new StringBuilder();
                //4-1.
                buff.append("(");
                //4-2.
                buff.append(temp);
                //4-3.
                buff.append(")");
                //4-4.
                u = u.substring(1, u.length()-1);
                if(!u.equals(""))
                {
                    char[] array = u.toCharArray();
                    for(int i = 0; i < array.length; i++)
                        array[i] = array[i] == '(' ? ')' : '(';
                    buff.append(array);
                }
                //4-5.
                return buff.toString();
                
            }
            
        }
    }
}
일단 코드 길이에 겁먹지 말자. 필자도 처음에 이런 문제를 보면 멘붕이와서 자괴감에 빠지다가 아무것도 못했다. 이러한 문제는 차근차근 단계를 나누어하면 조금 시간이 걸려도 풀 수 있다. 부분부분 코드를 보면 생각보다 어렵지 않을 것이다.

1
2
3
4
5
6
7
8
9
String p = "()))((()";
String answer = "";

if(isCorrectBracket(p))
    answer = p;
else
    answer = ChangeBracket(p);

System.out.println(answer);

함수를 실행하는 부분이다. p는 입력이고 p가 만약 올바른 괄호 문자열이라면 p그대로를 정답으로 한다. 그렇지 않으면 변환 프로그램을 거친다. 먼저 올바른 괄호 문자열인지 판별해 주는 isCorrectBracket함수를 살펴보자.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public static boolean isCorrectBracket(String s)
{
    char[] arr = s.toCharArray();
    int open = 0;
    int close = 0;
    for(char c : arr)
    {
        if(c == '(')
            open++;
        else
            close++;
        if(close > open)
            return false;
    }
    return true;
            
}

올바른 괄호 문자열인지 판별하는 방법은 간단하다. 닫은 괄호가 연 괄호보다 많아지는 순간 그 문자열은 올바르지 않다. 이를 그대로 코드로 구현하였다. open과 close를 이용해 닫는 괄호가 여는 괄호보다 많아지면 거짓을 반환하고 그렇지 않다면 참을 반환하도록 했다.

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
57
58
public static String ChangeBracket(String s)
{
    //1. 입력이 빈 문자열인 경우 빈 문자열을 반환합니다.
    if(s.equals(""))
        return "";
    else
    {
        //2. u, v로 분리
        String u = "";
        String v = "";
        char[] arr = s.toCharArray();
        int open = 0;
        int close = 0;
        for(char c : arr)
        {
            if(c == '(')
                open++;
            else
                close++;
            if(open == close)
                break;
        }
        int idx = open*2;
        u = s.substring(0, idx);
        if(idx < s.length())
            v = s.substring(idx);

        String temp = ChangeBracket(v);
            
        //3.u가 올바른 문자열일 경우
        if(isCorrectBracket(u))
            return u + temp;
        //4.u가 올바른 문자열이 아닐 경우
        else
        {
            StringBuilder buff = new StringBuilder();
            //4-1.
            buff.append("(");
            //4-2.
            buff.append(temp);
            //4-3.
            buff.append(")");
            //4-4.
            u = u.substring(1, u.length()-1);
            if(!u.equals(""))
            {
                char[] array = u.toCharArray();
                for(int i = 0; i < array.length; i++)
                    array[i] = array[i] == '(' ? ')' : '(';
                buff.append(array);
            }
            //4-5.
            return buff.toString();
                
        }
            
    }
}

제일 긴 괄호 변환 프로그램인데 해당 과정마다 주석을 달아놨다. 코드를 찬찬히 읽어보면 이해가 갈 것이다. 2과정에서 u는 더 이상 나누어지지 않는 균형잡힌 괄호 문자열이므로 처음으로 균형이 잡히면 반복문을 탈출한다.

이 코드의 시간 복잡도를 생각해보면 ')('가 여러 개 반복되는 패턴이다(재귀를 최대한 호출하기 때문이다.). 재귀의 반복횟수는 p의 길이를 N이라 할 때, \(log_{2}N\)이고, 재귀 안에서의 시간복잡도는 \(O(N)\)이므로, \(O(Nlog_{2}N)\)이 최종 시간복잡도이다.

테스트



카카오를 지원했을 때 2-3시간이 지나도 잘 못 풀었던 문제들을 풀어나가서 기쁘다. 비록 이것도 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
31
32
33
34
35
36
37
38
39
40
41
42
import java.util.*;

public class BiggestNum {
    
    //프로그래머스 문제풀이 level2 가장 큰 수
    public static void main(String[] args) {
        int[] numbers = {3, 30, 34, 5, 9};
        String[] arr = new String[numbers.length];
        int i = 0;
        for(int n : numbers)
        {
            arr[i++] = String.valueOf(n);
        }
        
        Arrays.sort(arr, new Comparator<String>(){
            @Override
            public int compare(String o1, String o2)
            {
                String s1 = o1 + o2;
                String s2 = o2 + o1;
                Integer i1 = Integer.parseInt(s1);
                Integer i2 = Integer.parseInt(s2);
                
                return i2.compareTo(i1);
                
            }
        });
        StringBuilder buff = new StringBuilder();
        boolean isZero = true;
        for(String s : arr)
        {
            if(Integer.parseInt(s) != 0)
                isZero = false;
            if(!isZero)
                buff.append(s);
        }
        if(buff.length() == 0)
            buff.append("0");
            
        System.out.println(buff.toString());
    }
}
코드는 어렵지 않다. 10-13줄은 int를 문자열로 바꾸어준다. 그리고 이를 정렬하면 되는데, 가장 큰 수를 만들기 위한 정렬은 두 문자를 합쳐보고 더 큰 쪽이 앞에 가도록 하면 된다. 정말 간단하다. 그 부분이 15-26번째 줄이다. 정렬한 문자열을 이제 합쳐주면 되는데 문제 조건을 보면 0이 들어갈 수 있다고 한다. 입력으로 들어온 모든 숫자가 0일 경우를 대비해 isZero를 선언하여 첫 숫자가 0인 것은 들어가지 않도록 했다.

최종 시간복잡도는 numbers의 길이를 n이라 할 때 \(O(nlogn)\)이다.

테스트



질문하기를 보고나서야 푼 문제라서 아쉬움이 남는다. 그래도 하나 배웠는데 compare안에 정렬을 새로 정의할 경우 다중 조건문을 쓰면 혼돈의 정렬이 된다는 것이다(이유는 더 공부가 필요하다.). 질문하기에서 나온 해결방법을 그대로 옮긴거라 필자의 아이디어는 아니지만, compare을 작성할 때 주의해야 할 점을 알았으니 만족한다.

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
import java.util.*;

public class FindPrimeNum
{
    //프로그래머스 문제풀이 level2 소수 찾기

    public static void main(String[] args) {
        String numbers = "17";
        Set<Integer> set = new HashSet<Integer>();
        StringBuilder buff = new StringBuilder();
        buff.append(numbers);
        for(int i = 1; i <= numbers.length(); i++)
        {
            findKDigitPrimeNum("", 0, set, i, buff);
        }
        System.out.println(set.size());

    }
    public static void findKDigitPrimeNum(String s, int size, Set<Integer> set, int k, StringBuilder buff)
    {
        if(size == k)
        {
            int n = Integer.parseInt(s);
            if(n <= 1)
                return;
            for(int i = 2; i <= Math.sqrt(n); i++)
            {
                if(n%i == 0)
                    return;
            }
            set.add(n);
        }
        else
        {
            
            for(int i = 0; i < buff.length(); i++)
            {
                StringBuilder str = new StringBuilder();
                char c = buff.charAt(i);
                str.append(s);
                str.append(c);
                findKDigitPrimeNum(str.toString(), size+1, set, k, buff.delete(i, i+1));
                str.delete(str.length()-1, str.length());
                buff.insert(i, c);
            }
        }
            
    }
}
카드 숫자로 만들 수 있는 모든 경우의 수를 조합하는 것이 이 문제의 핵심이다. 이 조합을 찾아내기 위해 다음과 같은 과정을 생각했다. 1. k개의 자릿수를 가지는 모든 숫자 조합을 만드는 함수를 만든다. 2. 조합을 완성할 때마다 소수인지 판별하여 소수라면 set에 삽입한다. 3. k값을 1부터 numbers의 크기만큼 반복한다. 4. set의 크기를 반환한다.

위 과정을 코드로 담은 것이 위에 코드다 여기서 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
public static void findKDigitPrimeNum(String s, int size, Set<Integer> set, int k, StringBuilder buff)
{
    if(size == k)
    {
        int n = Integer.parseInt(s);
        if(n <= 1)
            return;
        for(int i = 2; i <= Math.sqrt(n); i++)
        {
            if(n%i == 0)
                return;
        }
        set.add(n);
    }
    else
    {
            
        for(int i = 0; i < buff.length(); i++)
        {
            StringBuilder str = new StringBuilder();
            char c = buff.charAt(i);
            str.append(s);
            str.append(c);
            findKDigitPrimeNum(str.toString(), size+1, set, k, buff.delete(i, i+1));
            str.delete(str.length()-1, str.length());
            buff.insert(i, c);
        }
    }
            
}
s는 현재 만들어진 숫자를 의미한다. size는 s의 크기를 나타내고, k는 보고자하는 자릿수이다. buff는 현재 쓸 수 있는 숫자 카드를 담아둔 변수이다. 첫번째 if문은 크기가 k를 만족할 경우 소수인지 판별하고 소수라면 set에 해당 수를 넣는 부분이다. set을 사용한 이유는 중복을 방지하기 위함이다. 만약에 size가 k에 도달하지 못했다면, 문자를 추가해야한다. 이 경우 else문으로 빠진다. buff에 들어있는 문자들을 하나씩 넣었다 빼면서, 함수를 재호출한다.

시간복잡도는 문자열의 길이를 n이라 할 때, \(O(n^{n+1})\)이다.

테스트



완전 탐색이라 시간복잡도차 최악을 도는 것을 볼 수 있다. 이러한 문제는 보통 테스트 케이스의 수가 상대적으로 작다. 이런 문제가 나올 땐 효율성에 겁내지 말고 일단 해보는 것이 중요하다.

Posted on Edited on In , ,

문제정의

문자열을 일정 단위로 끊어서 압축하려고 한다(ex. abab -> 2ab). 몇 개 단위로 끊어서 압축이 가장 많이 된 문자열의 길이를 계산하는 문제이다.

문제풀이

전체 코드는 다음과 같다. 

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
57
58
59
public class StringCompress {

    //프로그래머스 문제풀이 level2 문자열 압축

    public static void main(String[] args)
    {
        String s = "aabbcc";
        StringBuffer buff = new StringBuffer();
        int answer = 2000;
        int cnt = 1;
        if(s.length() == 1)
            answer = 1;
        for(int cut = 1; cut <= s.length()/2; cut++)
        {
            String key = s.substring(0, cut);
            buff.delete(0, buff.length());
            cnt = 1;
            for(int i = cut; i < s.length(); i += cut)
            {
                if(i + cut > s.length())
                {
                    if(cnt > 1)
                        buff.append(cnt);
                    buff.append(key);
                    buff.append(s.substring(i, s.length()));
                    break;
                }

                else if(key.equals(s.substring(i, i+cut)))
                {
                    cnt++;
                    if(i == s.length()-1 || i+cut == s.length())
                    {
                        buff.append(String.valueOf(cnt));
                        buff.append(key);
                    }
                }

                else
                {
                    if(cnt > 1)
                        buff.append(String.valueOf(cnt));
                    buff.append(key);
                    if(i + cut >= s.length())
                    {
                        buff.append(s.substring(i, s.length()));
                        break;
                    }
                    key = s.substring(i, i+cut);
                    cnt = 1;
                }
            }
            String str = buff.toString();
            answer = Math.min(answer, str.length());
        }
        System.out.println(answer);
    }
    
}
필자는 이 코드가 굉장히 마음에 안드는데 일단 많이 조잡하다. 핵심 아이디어는 간단하다. 앞에서부터 문자열을 끊어서 key으로 만든 뒤, 압축이 가능하다면 cnt를 계산하여, 넣어주고 아니면 문자열 그대로를 넣어준다. 만약 문자열이 남아버리면 한꺼번에 넣어준다. 필자는 세부적인 구현에서 if문을 덕지덕지 붙여서 통과했다. 질문하기에서 봤던 테스트 케이스를 참고해서 통과했으니, 세부적인 구현 능력을 좀 더 길러야겠다.

시간복잡도는 문자열의 길이를 n이라 할 때, 최대 \(n^2/2\) 만큼 반복하므로 \(O(n^2)\)이다.

테스트



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
public class KaKaoFriendColoringBook {
    
    //프로그래머스 문제풀이 level2 카카오프렌즈 컬러링북

    public static void main(String[] args)
    {
        int m = 6, n = 4;
        int[][] picture = {
            {1,1,1,0},
            {1,2,2,0},
            {1,0,0,1},
            {0,0,0,1},
            {0,0,0,3},
            {0,0,0,3}
        };
        int numberOfArea = 0;
        int maxSizeOfOneArea = 0;
        int[] answer = new int[2];
        boolean[][] visited = new boolean[m][n];
        for(int i = 0; i < m; i++)
        {
            for(int j = 0; j<n; j++)
            {
                if(visited[i][j] == false && picture[i][j] != 0)
                {
                    numberOfArea++;
                    maxSizeOfOneArea = Math.max(maxSizeOfOneArea, getRegion(visited, i, j, picture, 0, picture[i][j], m, n));
                }
            }
        }        
        answer[0] = numberOfArea;
        answer[1] = maxSizeOfOneArea;

    }
    public static int getRegion(boolean[][] visited, int r, int c, int[][] picture, int area, int c_id, int m, int n)
    {
        if(r == m || c == n || r < 0 || c < 0)
            return area;
        if(picture[r][c] != c_id)
            return area;
        else if(visited[r][c] == true)
            return area;
        else
        {
            visited[r][c] = true;
            area++;
            int left = getRegion(visited, r, c-1, picture, 0, c_id, m, n);
            int right = getRegion(visited, r, c+1, picture, 0, c_id, m, n);
            int up = getRegion(visited, r-1, c, picture, 0, c_id, m, n);
            int down = getRegion(visited, r+1, c, picture, 0, c_id, m, n);
            
            return area+left+right+up+down;
        }
    }
}
단순 탐색이기 때문에 리컬시브 함수만 이용한다면 빠르게 풀 수 있다. 필자는 getRegion을 통해 한 영역의 넓이를 계산할 생각이다. 리컬시브 코드를 볼 때는 항상 종료 조건을 잘 봐야한다. 어떠한 로봇이 있다고 상상하고 그 로봇이 동시에 한 블럭에서 동시에 상하좌우로 뻗어나가며 같은 영역인지 판단한다고 해보자. 그렇다면 3가지의 종료 조건을 생각할 수 있다. 1. 로봇이 그림 밖으로 나갔을 경우 2. 다른 색깔이 칠해져있는 경우 3. 이미 다른 로봇이 지나갔던 곳일 경우 이를 세가지의 if문으로 표시하였다. c_id는 현재 영역의 색깔을 나타내고 visited는 그 영역이 첫방문인지 알려주는 변수이다. 이 종료조건을 모두 통과했을 경우 현재 로봇이 서 있는 곳은 같은 영역으로 표시해야하는 것이다. 이럴 경우 방문했다는 것을 알려주기 위해 해당 visited를 true로 바꿔주고, area를 늘린다. 그리고 그 위치에서 상하좌우로 로봇을 보내기 위해 함수를 호출한다. 전체 영역은 현재 영역에서 상하좌우로 이어진 영역의 합을 구하는 것이므로 left,up,down,right에 각각의 영역을 담아 더하면 된다.

시간복잡도는 모든 영역이 칠해져 있을 때가 최악의 경우이다. 왜냐하면 mxn영역을 다보는데 mxn번 만큼 함수가 계속 호출되기 때문이다. 따라서 최종 시간복잡도는 \(O((m*n)^2)\)이다.

테스트



Posted on Edited on

문제정의

밑변과 높이의 길이가 n인 삼각형이 있고 이를 맨 위 꼭짓점에서부터 반시계방향으로 달팽이를 채우기 하고 열대로 숫자를 담아 출력하는 문제이다. 자세한 그림이 궁금한 사람은 링크를 참고해보길 바란다.

문제풀이

전체 코드는 다음과 같다. 

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
public class TriSnail {
    
    //프로그래머스 문제풀이 level2 삼각 달팽이

    public static void main(String[] args)
    {
        int n = 4;
        int[][] paper = new int[2*n-1][2*n-1];
        int len = n;
        int num = 1;
        int l_d_move = n%3;
        int r_move = l_d_move-1 < 0 ? 2: l_d_move-1;
        int r = 0, c = (2*n-1)/2;
        while(len != 0)
        {
            int move_id = len%3;
            if(move_id == l_d_move)
            {
                for(int i = 0; i < len; i++)
                    paper[r++][c--] = num++;
                r--;
                c++;
            }
            else if(move_id == r_move)
            {
                for(int i = 0; i < len; i++)
                {
                    c+=2;
                    paper[r][c] = num++;
                }
            }
            else
            {
                for(int i = 0; i < len; i++)
                    paper[--r][--c] = num++;
                ++r;
                --c;
            }
            len--;
        }
        int idx = 0;
        int[] answer = new int[num-1];
        for(int i = 0; i < 2*n-1; i++)
        {
            for(int j = 0; j < 2*n-1; j++)
            {
                if(paper[i][j] != 0)
                    answer[idx++] = paper[i][j];
            }
        }
    }
}
처음엔 같은 행에 속한 요소들끼리 무언가 규칙이 있을까 찾아봤지만, 너무 복잡하였다. 그래서 문제에서 주어진 달팽이를 그대로 2차원 배열에 그린 뒤, 맨 위에서부터 0이 아닌 값을 읽어들여 배열에 넣는 방법을 생각했다. 그럼 반시계 방향으로 달팽이 채우기를 하는 알고리즘이 필요한데, 이해를 돕기 위해 그림을 첨부한다.



그림을 보면 반시계 방향으로 꺽으면서 이동횟수가 1씩 감소하는 것을 볼 수 있다. 삼각형을 그리면서 움직이므로 여기서 규칙을 찾아낼 수 있다. 바로 이동횟수를 3으로 나누고 난 나머지 값을 활용해 어느 방향으로 가야하는지 알 수 있다는 것이다. n=4일 때의 달팽이 채우기를 보자, 4와 1일 때는 왼쪽 아래로 향하는 것을 볼 수 있다. n=5일 때도 보면 같은 규칙이 적용되는 것을 볼 수 있다. 5와 2는 3으로 나눈 나머지가 모두 2이므로, 2일 때 왼쪽 아래로 움직여야 하는 것을 알 수 있다.

규칙을 찾아냈으니 달팽이 채우기를 그릴 틀이 필요하다. 필자는 이것을 paper라고 선언했다. nn으로 2차원배열을 선언하고자 할텐데, 종이와 달리 배열은 중간에 낀 수가 없기 때문에 이렇게 해선 안된다. 2n-1이 길이여야 하는데 이는 아래 그림을 참고하면 왜 그런지 알 수 있다.



핵심 아이디어를 다 익혔으니 코드 세부 구현을 보자. 

1
2
3
4
5
6
7
int n = 4;
int[][] paper = new int[2*n-1][2*n-1];
        int len = n;
        int num = 1;
        int l_d_move = n%3;
        int r_move = l_d_move-1 < 0 ? 2: l_d_move-1;
        int r = 0, c = (2*n-1)/2;
왼쪽아래 움직임을 l_d_move라 표현했다. 그리고 r_move는 오른쪽으로 움직이는 경우의 나머지값을 나타낸 것이다. l_d_moved에서 1을 뺀 값이지만, 만약 l_d_move가 0인 경우, r_move는 2이기 때문에 이에 대한 처리도 함께한다. 초기 1이 위치하는 값은 (0,(2*n-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
while(len != 0)
{
    int move_id = len%3;
    if(move_id == l_d_move)
    {
        for(int i = 0; i < len; i++)
            paper[r++][c--] = num++;
        r--;
        c++;
    }
    else if(move_id == r_move)
    {
        for(int i = 0; i < len; i++)
        {
            c+=2;
            paper[r][c] = num++;
        }
    }
    else
    {
        for(int i = 0; i < len; i++)
            paper[--r][--c] = num++;
        ++r;
        --c;
    }
    len--;
}

move_id에 따라 종이에 숫자를 채워가는 코드이다. r과 c값을 조정해나가면 된다. 범위 때문에 r이나 c값이 이상해지지 않도록 반복문 탈출 뒤 조정해주는 과정도 거친다. 여기서 필자보다 깨끗하게 코드를 짤 수 있을거라 생각하기 때문에, 이 부분에서 더 세부적인 내용은 생략한다. 여기서 시간복잡도는 \(O(n)\)이 되겠다.

1
2
3
4
5
6
7
8
9
10
int idx = 0;
int[] answer = new int[num-1];
for(int i = 0; i < n; i++)
{
    for(int j = 0; j < 2*n-1; j++)
    {
        if(paper[i][j] != 0)
            answer[idx++] = paper[i][j];
    }
}

이제 paper를 순회하면서 0이 아닌 값을 발견할 때 마다, answer에 값을 넣어주면 된다. 행은 n까지만 보면 되므로, 행의 최대값은 n으로 한다. 이 부분에서 시간복잡도는 \(O(n^2)\)이다. 따라서 최종 시간복잡도는 \(O(n^2)\)이다.

테스트



어떠한 규칙을 찾아내는 냐에 따라 코드가 천차만별인 것 같다. 코드를 좀 더 줄일 수 있는 규칙이 추가로 있는지 고민해봐야겠다.

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
import java.util.*;

public class Printer {
    
    //프로그래머스 문제풀이 level2 프린터

    public static void main(String[] args)
    {
        int[] priorities = {1, 1, 9, 1, 1, 1};
        int location = 0;
        int answer = 0;
        ArrayList<Integer> papers = new ArrayList<>();
        int order = 1;
        boolean isFirst;
        for(int i = 0; i < priorities.length; i++)
            papers.add(i);
        while(papers.size() != 0)
        {
            isFirst = true;
            int idx = papers.get(0);
            
            for(int i = 1; i < papers.size(); i++)
            {
                if(priorities[papers.get(i)] > priorities[idx])
                {
                    papers.remove(0);
                    papers.add(idx);
                    isFirst = false;
                    break;
                }
            }
            if(isFirst)
            {
                if(idx == location)
                {
                    answer = order;
                    break;
                }
                else
                {
                    papers.remove(0);
                }
                order++;
            }
                
        }
        System.out.print(answer);
    }
    
}
필자는 어레이리스트로 문제를 풀었다. 시간을 줄이고 싶었지만, 잘 모르겠어서 문제가 시키는 그대로 했다. papers에 각 문서의 위치를 담고, 맨 앞부터 차례대로 보는 것이다. 22-31번째 줄을 보면, 우선순위를 탐색하는 코드가 있다. 만약 현재 맨 앞에 있는 것보다 우선순위가 큰 문서가 있으면, 현재 문서를 맨 뒤로 보내고, 대기문서의 첫번째에 있지 않기 때문에 isFisrt를 false로 한다. 만약에 인쇄될 문서보다 우선순위가 높은 것이 없으면 isFirst는 true가 될 것이다. 이때 이 문서가 내가 인쇄요청한 문서라면, 답을 반환하고 그렇지 않다면 order를 증가하고 해당 문서를 제거(출력)한다.

이 문제의 시간복잡도는 내가 인쇄 요청한 문서가 오름차순 우선순위의 가장 마지막 문서일 경우이다. 이 경우 문서의 개수를 n이라 하면, \(O(n^2)\)이다.

테스트



다른 사람의 풀이를 보니 answer를 앞에서부터 볼 인덱스로 하고 l을 내가 요청한 문서가 현재 위치한 곳을 나타내는 것으로 하여 일일이 priority를 다 비교하지 않아도 문제를 풀었다. 정말 대단하다고 생각한다. 나도 멋진 아이디어가 생각날 때까지 갈고 닦아야겠다.