Rabbit blog

Rabbit blog
0%

Posted on Edited on In , ,

문제정의

어떤 십진수 n이 들어올 때 이를 3진법으로 바꾼뒤 이를 뒤집는다. 뒤집은 3진법을 다시 10진수로 출력한다.

문제풀이

10진법을 2진법을 바꾸는 방법을 떠올려보자. 계속 나누어가다가 몫이 0이 되면 나머지들을 최근것부터 합치면 된다. 이 문제에서는 3진법을 거꾸로 뒤집으라 했으므로 나오는 나머지들을 스택에 쌓으면 원래 3진법에서 뒤집어진다. 뒤집은 수를 10진법으로 바꾸는 방법은 3^(자릿수)에 해당 값을 곱하면된다. 이를 다 합산하면 우리가 바라던 정답이다.

전체 코드는 다음과 같다. 

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

public class Flip3Digit {
    
    public static void main(String[] args)
    {
        int n = 45;
        int answer = 0;
        int q = 1, r = 0;
        Stack<Integer> s = new Stack<>();
        while(q != 0)
        {
            q = n/3;
            r = n%3;
            n /= 3;
            s.push(r);
            
        }
        int digit = 0;
        while(!s.empty())
        {
            answer += Math.pow(3,digit) * Integer.parseInt(s.peek().toString());
            digit++;
            s.pop();
        }
        System.out.print(answer);
    }
    
}
부분부분 살펴보자 
1
2
3
4
5
6
7
8
9
10
11
12
int n = 45;
int answer = 0;
int q = 1, r = 0;
Stack<Integer> s = new Stack<>();
while(q != 0)
{
    q = n/3;
    r = n%3;
    n /= 3;
    s.push(r);
        
}
10진법을 3진수로 바꾸는 과정이다. q는 몫이고 r은 나머지이다. 몫이 0이 될 때 까지 나머지를 구하고 이를 스택에 쌓는다. 
1
2
3
4
5
6
while(!s.empty())
{
    answer += Math.pow(3,digit) * Integer.parseInt(s.peek().toString());
    digit++;
    s.pop();
}
스택에 나머지값이 쌓이면 스택에 쌓인 값 순서대로 10진수로 변환하는 과정을 거친다. 이 때 자릿수를 나타내는 digit은 0으로 초기화한다. 그리고 3*(자릿수)를 각 나머지에 곱하고 digit을 늘려간다.

총 시간복잡도는 3진수로 바꿨을 때 최대 자릿수를 n이라하면 \(O(n)\)이다.

테스트



Posted on Edited on In , ,

문제정의

2016년의 월과 일을 입력하면 요일을 출력해주는 프로그램을 짜는 문제이다.

문제풀이

물론 제일 쉬운 방법은 스위치문이나 if-else문으로 모든 경우의 수를 짜는 것이겠지만(실제로 문제를 풀고 다른 사람 풀이 중에 그렇게 푼 사람이 있었다! 정말 존경한다.), 필자는 1월 1일부터 며칠이나 떨어져있는지 계산한 후 그 날을 요일로 바꾸는 연산을 하였다.

전체 코드는 다음과 같다. 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public class Year2016 {

    public static void main(String[] args)
    {
        int a = 1;
        int b = 3;
        String answer = "";
        int[] months = {0,31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30};
        String[] days = {"MON", "TUE", "WED", "THU", "FRI", "SAT", "SUN"};
        int day = 4;
        int month = 1;
        while(month != a)
        {
            day += months[month];
            month++;
        }
        day += b-1;
        day %= 7;
        answer = days[day];
        System.out.println(answer);
    }
    
}
코드가 짧으므로 오늘은 부분적으로 코드를 끊어서 보지 않겠다. 일단 월마다 더하는 달을 배열로 저장해둔다. 예를 들어 1월 1일에서 2월 1일로 넘어가기 위해선 31일이 필요하다. 0월이란 수는 없으므로 months의 첫번째 수는 0으로 채운다. 그리고 days에는 요일을 저장해둔다. 문제에서 2016년 1월 1일은 금요일이라 했으므로 금요일의 배열 인덱스인 4를 기본값으로한다. 이제 a와 b에 따라 요일을 출력해보자. 초기 달은 1월인데 만약 원하는 달이 1월이 아닌 경우 months의 일수를 더해간다. 그리고 b일 -1을 더해준다(1일에서 넘어가기 시작하는거기 때문이다.). 총 일수를 구했으니 이를 7로 나머지 연산을 하면 요일을 구할 수 있다.

총 시간복잡도는 a의 크기에 따라 달라지므로 a의 크기를 n이라하면 \(O(n)\)이다.

테스트



다른 사람의 풀이를 보니 하나하나 스위치문과 if문을 통해 구현한 사람이 있었다. 정말 대단한 사람이라고 생각한다. 문제풀이를 처음 시작할 때 효율적인 방법을 몰라도 일단 풀고자 하는 마음이 중요하다.

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
public static void main (String[] args)
    {
        int n = 5;
        int[] lost = {2, 4};
        int[] reserve = {1, 3, 5};
        int answer = 0;
        int[] cnt = new int[n];
        Arrays.fill(cnt, 1);
        for(int idx : lost)
            cnt[idx-1]--;
        for(int idx : reserve)
            cnt[idx-1]++;
        for(int i = 0; i < n; i++)
        {
            if(cnt[i] > 0)
                answer++;
            else
            {
                if(i == 0)
                {
                    if(cnt[1] > 1)
                    {
                        answer++;
                        cnt[1]--;
                    }
                }
                else if(i == n-1)
                {
                    if(cnt[n-2] > 1)
                        answer++;
                }
                else
                {
                    if(cnt[i-1] > 1)
                    {
                        answer++;
                    }
                    else if(cnt[i+1] > 1)
                    {
                        answer++;
                        cnt[i+1]--;
                    }
                }
            }
        }

       System.out.print(answer);
    }

부분부분 살펴보자

1
2
3
4
5
6
7
8
9
10
int n = 5;
int[] lost = {2, 4};
int[] reserve = {1, 3, 5};
int answer = 0;
int[] cnt = new int[n];
Arrays.fill(cnt, 1);
for(int idx : lost)
    cnt[idx-1]--;
for(int idx : reserve)
    cnt[idx-1]++;

학생마다 가지고 있는 체육복의 개수를 알아내기 위해 cnt 배열을 선언한다. 초기화는 모두 1로 한다. 그리고 체육복을 도둑맞은 학생의 개수는 줄이고 여분을 가지고 있는 학생의 개수는 1 증가한다. 이 부분에서 시간이 제일 오래 걸리는 부분은 fill이 \(O(n)\)만큼 걸리기 때문에 이 부분에서 시간복잡도는 \(O(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
for(int i = 0; i < n; i++)
{
    if(cnt[i] > 0)
        answer++;
    else
    {
        if(i == 0)
        {
            if(cnt[1] > 1)
            {
                answer++;
                cnt[1]--;
            }
        }
        else if(i == n-1)
        {
            if(cnt[n-2] > 1)
                answer++;
        }
        else
        {
            if(cnt[i-1] > 1)
            {
                answer++;
                continue;
            }
            else if(cnt[i+1] > 1)
            {
                answer++;
                cnt[i+1]--;
            }
        }
    }
}

초기 answer를 0으로 한다. 그리고 모든 학생을 보며 만약 체육복을 가지고 있다면 answer를 증가하고 넘긴다. 만약 학생이 체육복을 가지고 있지 않다면 체육복을 빌린다. 맨 앞에 있는 학생의 경우 자신보다 앞이 없으므로 뒷번호의 학생에게 밖에 빌릴 수 없다(i == 0). 맨 뒤에 있는 학생의 경우 자신보다 뒷번호가 없으므로 앞에서 밖에 빌릴 수 없다(i == n-1). 사이에 있는 학생의 경우 둘 다 빌릴 수 있다. 따라서 자신보다 앞에 있는 학생한테 체육복을 빌릴 수 있는지 확인한 후, 빌릴 수 있는 경우에 answer를 증가한다. 만약 앞에 학생한테 체육복을 빌릴 수 없으면 뒤에 있는 학생한테 빌려본다. 전체 n만큼 반복하므로 최종 시간복잡도는 \(O(n)\)이 된다.

테스트



코드를 보면 알겠지만, 약간 지저분한 느낌이 든다. 맨 첫번째 학생과 맨 뒤에 학생을 따로 처리해줘서 그런데, 이 경우 배열의 크기를 n+2로 하면 이러한 연산을 없앨 수 있다. 앞으로 코드를 작성할 때 기억해야겠다.

Posted on Edited on In , ,

문제정의

배열이 주어지고 명령어가 들어올 때 해당하는 숫자들을 배열에 모아 반환해야 한다. 명령어는 총 3부분인데 [i, j, k]라고 하면 배열의 i에서 j번째까지 자른 다음에 이를 정렬한다. 그리고 이 부분 배열중에서 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
import java.util.*;

public class KthNum {
    
    public static void main(String[] args)
    {
        int[] array = {1, 5, 2, 6, 3, 7, 4};
        int[][] commands = {
            {2, 5, 3},
            {4, 4, 1},
            {1, 7, 3}
        };
        ArrayList<Integer> num = new ArrayList<Integer>();
        for(int i = 0; i < commands.length; i++)
        {
            int[] subarr = Arrays.copyOfRange(array, commands[i][0]-1, commands[i][1]);
            Arrays.sort(subarr);
            num.add(subarr[commands[i][2]-1]);
        }
        int[] answer = new int[num.size()];
        for(int i = 0; i < num.size(); i++)
        {
            answer[i] = Integer.parseInt(num.get(i).toString());
            //System.out.print(answer[i]);
        }
    }

}

부분부분 살펴보자

1
2
3
4
5
6
7
ArrayList<Integer> num = new ArrayList<Integer>();
for(int i = 0; i < commands.length; i++)
{
    int[] subarr = Arrays.copyOfRange(array, commands[i][0]-1, commands[i][1]);
    Arrays.sort(subarr);
    num.add(subarr[commands[i][2]-1]);
}

부분배열 subarr를 만들기위해 copyOfRange를 사용한다. copyOfRange의 경우 [i,j)이기 때문에 i-1을 입력해야한다. 배열은 0부터 시작한다. 잊지말자. end부분에는 -1할 필요가 없다. 애초에 포함이 안된다. 그 다음 부분배열을 정렬해주고 k번째에 해당하는 수는 num에 넣어준다. 이 부분에서 시간복잡도는 일단 commands의 길이를 m이라하고 array의 길이를 n이라고 한다면, \(O(mnlogn)\)이 된다. i와 j로인해 잘리는 최대 크기가 n이기 때문이다. copyOfRange에서 \(O(n)\)의 시간이 걸리고 sort에서 \(O(nlogn)\)의 시간복잡도를 가진다. add는 \(O(1)\)이다.

테스트



이번 포스팅은 문제의 요구사항을 그대로 코드로 옮기는 것이라 그렇게 어려운 부분이 없다. 하지만 여전히 Integer를 int로 바꾸는 것은 익숙치 않다.

Posted on Edited on In , ,

문제정의

수포자 3명의 찍기 패턴이 주어지고 정답이 주어질 때 가장 문제를 많이 맞춘 수포자를 찾아내면 되는 문제이다.

문제풀이

수포자들의 찍기 패턴이 주어져있지만 이 패턴은 시간복잡도를 최적화하는 것과는 관련이 없다. 결국 모두 봐야한다.

전체 코드는 다음과 같다. 

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

public class Test {

    public static void main(String[] args)
    {
        int[] answers = {1,2,3,4,5};
        int[] student1 = {1, 2, 3, 4, 5};
        int[] student2 = {2, 1, 2, 3, 2, 4, 2, 5};
        int[] student3 = {3, 3, 1, 1, 2, 2, 4, 4, 5, 5};
        int[] result = {0, 0, 0};
        int[] idx = {0, 0, 0};
        for(int ans : answers)
        {
            if(ans == student1[idx[0]])
                result[0]++;
            if(ans == student2[idx[1]])
                result[1]++;
            if(ans == student3[idx[2]])
                result[2]++;
            
            idx[0]++;
            idx[1]++;
            idx[2]++;
            
            idx[0] %= 5;
            idx[1] %= 8;
            idx[2] %= 10;
            
            
        }
        int max = 0;
        for(int cnt : result)
        {
            if(max < cnt)
                max = cnt;
        }
        Vector<Integer> v = new Vector<Integer>();
        for(int i = 0; i < 3; i++)
        {
            if(max == result[i])
                v.add(i);
                
        }
        int[] answer = new int[v.size()];
        for(int i = 0; i < v.size(); i++)
        {
            answer[i] = Integer.parseInt(v.get(i).toString()) + 1;
        }

    }
    
}

부분부분 살펴보자

1
2
3
4
5
6
int[] answers = {1,2,3,4,5};
int[] student1 = {1, 2, 3, 4, 5};
int[] student2 = {2, 1, 2, 3, 2, 4, 2, 5};
int[] student3 = {3, 3, 1, 1, 2, 2, 4, 4, 5, 5};
int[] result = {0, 0, 0};
int[] idx = {0, 0, 0};

수포자 1,2,3의 패턴을 담은 student배열을 만들었다. result배열에는 학생의 시험 점수를 담는 배열이고 idx는 각 패턴배열에서 몇번째를 봐야하는지 나타내는 배열이다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
for(int ans : answers)
{
    if(ans == student1[idx[0]])
        result[0]++;
    if(ans == student2[idx[1]])
        result[1]++;
    if(ans == student3[idx[2]])
        result[2]++;
    
    idx[0]++;
    idx[1]++;
    idx[2]++;
    
    idx[0] %= 5;
    idx[1] %= 8;
    idx[2] %= 10;
    
    
}

정답을 맞춰보는 코드이다. 만약 학생들의 찍기와 맞다면 result값을 올린다. idx를 증가한다. 이때 나머지 연산통해 배열의 사이즈를 벗어나서 참조하지 않도록 한다. 이 부분의 시간복잡도는 answers의 길이를 n이라 할 때 \(O(n)\)이다.

1
2
3
4
5
6
int max = 0;
for(int cnt : result)
{
    if(max < cnt)
        max = cnt;
}

시험결과중 가장 높은 점수를 max에 저장한다. 이 때 result의 길이는 3으로 고정되어 있기 때문에 시간복잡도는 \(O(1)\)이다.

1
2
3
4
5
6
7
8
9
10
11
12
Vector<Integer> v = new Vector<Integer>();
for(int i = 0; i < 3; i++)
{
    if(max == result[i])
        v.add(i);
        
}
int[] answer = new int[v.size()];
for(int i = 0; i < v.size(); i++)
{
    answer[i] = Integer.parseInt(v.get(i).toString()) + 1;
}

result중에 max값과 같은 경우가 있다면 해당 학생을 벡터 v에 넣는다. c++에선 벡터를 주로 사용하였기 때문에 벡터를 썼는데, 자바에서는 벡터보다는 어레이리스트가 많이 쓰인다고 한다. 속도면에서 차이가 있다고 하는데 다음에는 어레이리스트로 작성해봐야겠다. 벡터는 Integer형식이기 때문에 int로 바꿔주는 작업과 동시에 +1을 해준다. 수포자0,1,2가 이나라 수포자 1,2,3이기 때문이다. 이 부분의 시간복잡도는 최대 3으로 고정되므로 \(O(1)\)이다.

최종 시간복잡도는 \(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
25
26
27
28
29
30
31
32
33
34
35
36
37
38
import java.util.*;

public class NotCompletePlayer {

    public static void main(String[] args)
    {
        String[] participant = {"leo", "kiki", "eden"};
        String[] completion = {"eden", "kiki"};

        String answer = "";
        PriorityQueue<String> pq = new PriorityQueue<>();
        PriorityQueue<String> comp = new PriorityQueue<>();
        for(int i = 0; i < participant.length; i++)
        {
            pq.add(participant[i]);
        }
        for(int i = 0; i < completion.length; i++)
        {
            comp.add(completion[i]);
        }
        
        for(int i = 0; i < completion.length; i++)
        {
            String name1 = pq.poll();
            String name2 = comp.poll();
            if(!name1.equals(name2))
            {
                answer = name1;
                break;
            }
        }
        if(answer.equals(""))
            answer = pq.poll();

        System.out.println(answer);
    }
    
}

부분부분 살펴보자

1
2
PriorityQueue<String> pq = new PriorityQueue<>();
PriorityQueue<String> comp = new PriorityQueue<>();

자바에서 기본적으로 정렬함수를 제시하지만 필자는 우선순위 큐를 활용하였다. 이건 각자의 취향인듯하니 넘기자. 이렇게 선언하면 알파벳이 낮은 순서(오름차순)로 정렬된다.

1
2
3
4
5
6
7
8
for(int i = 0; i < participant.length; i++)
{
    pq.add(participant[i]);
}
for(int i = 0; i < completion.length; i++)
{
    comp.add(completion[i]);
}

이제 참가자와 완주자명단을 우선순위 큐에 차례대로 집어넣는다. 우선순위큐에 넣는 것은 \(O(logn)\)만큼 걸린다. 따라서 participant의 길이를 n이라고 하면 시간복잡도는 \(O(nlogn)\)이다.

1
2
3
4
5
6
7
8
9
10
11
12
for(int i = 0; i < completion.length; i++)
{
    String name1 = pq.poll();
    String name2 = comp.poll();
    if(!name1.equals(name2))
    {
        answer = name1;
        break;
    }
}
if(answer.equals(""))
    answer = pq.poll();

둘 다 정렬되어 있는 상태라면 완주하지 못한 선수가 끼어있는 부분부터 이름이 다를 것이다는 것을 이용하였다. 큐에서 이름을 하나하나 빼면서 처음으로 이름이 안맞는 부분이 있으면 정답에 참가자 이름을 넣고 반복문을 탈출하도록 한다. 하지만 이러한 케이스는 어떨까?

participation : [aaa, bbb, ccc]

completion : [aaa, bbb]

이 경우 반복을 마쳐도 answer에 아무것도 들어가지 않는다. completion의 길이만큼 반복이 진행됨을 눈여겨 보자. 이 경우를 고려하여 if문이 들어간다. 이렇게 되면 ccc도 완주하지 못한 선수로 골라낼 수 있다.

시간복잡도는 \(O(nlogn)\)이며, 최종 시간복잡도 역시 같다.

테스트



해시

문제의 유형이 해시로 나타나 있는데 hashmap를 이용할 경우 \(O(n)\)으로 문제를 풀 수 있다. hashmap에 선수의 이름을 key값으로 하고 value를 1로 하여 넣는다. 만약에 동명이인이 있는 선수라면 getOrDefault를 이용하여 2,3,4...이런식으로 value를 업데이트한다. 참가자 명단에 대해 위 과정을 수행하면 다음엔 완주자 명단에 있는 사람들의 이름을 key값으로 (value-1)값을 다시 hashmap에 넣는다. 이렇게 되면 value가 1인 사람은 한명이 남는다. 완주하지 못한 선수를 찾기 위해 hashmap의 keySet을 이용하여 value가 1인 선수를 answer에 담으면 된다.

Posted on Edited on In , ,

문제정의

정수 배열 numbers가 주어질 때 서로 다른 인덱스에 있는 두 개의 숫자를 뽑아 더해서 만들 수 있는 모든 경우의 수를 배열로 담아 반환하는 문제이다.

문제풀이

간단한 문제이다. 두 수를 모두 더해보면서 배열에 넣으면 된다. 다만, 중복인 배열이 있으면 안되므로 set를 활용한다.

전체 코드는 다음과 같다. 

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

public class PickTwoSum {

    public static void main(String[] args)
    {
        int[] numbers = {2, 1, 3, 4, 1};

        HashSet<Integer> set = new HashSet<Integer>();
        for(int i = 0; i < numbers.length; i++)
        {
            for(int j = i+1; j < numbers.length; j++)
            {
                set.add(numbers[i]+numbers[j]);
            }
        }
        
        List<Integer> list = new ArrayList<>(set);
        list.sort(null);
        Integer arr[] = new Integer[list.size()];
        arr = list.toArray(arr);
        int[] answer = new int[arr.length];
        for(int i = 0; i < arr.length; i++)
        {
            answer[i] = Integer.parseInt(arr[i].toString());
        }

        

    }
    
}

부분부분 살펴보자

1
2
3
4
5
6
7
8
HashSet<Integer> set = new HashSet<Integer>();
for(int i = 0; i < numbers.length; i++)
{
    for(int j = i+1; j < numbers.length; j++)
    {
        set.add(numbers[i]+numbers[j]);
    }
}

중복을 방지하기 위해 배열이 아닌 set을 선언한다. 두 수를 더해서 set에 더해간다. set에 add를 하는 것은 \(O(1)\)이다. 따라서 for문에 의해 이부분은 \(O(n^2)\)이다.

1
2
3
4
5
6
7
8
9
List<Integer> list = new ArrayList<>(set);
list.sort(null);
Integer arr[] = new Integer[list.size()];
arr = list.toArray(arr);
int[] answer = new int[arr.length];
for(int i = 0; i < arr.length; i++)
{
    answer[i] = Integer.parseInt(arr[i].toString());
}

set은 순서에 상관하지 않기 때문에 정렬이라는 개념이 없다. 그래서 이를 list로 바꿔준뒤 int형태로 바꿔주는 과정이다. list에 있는 sort는 \(O(nlogn)\)이고 for문은 \(O(n)\)이므로 이 부분에서 시간복잡도는 \(O(nlogn)\)이다.

따라서 총 걸리는 시간 복잡도는 \(O(n^2)\)이다.

테스트

pick_two_sum_result

c++로 코딩을 하다가 다시 자바를 하려니 까먹은 자료구조나 메소드가 많다. 앞으로 천천히 익혀나가야겠다.

Posted on Edited on In , ,

문제정의

말그대로 인형뽑기 게임이다. 게임판은 2차원 배열(board)이 주어진다. 그리고 인형을 뽑는 순서로 1차원 배열(moves)이 주어진다. 뽑은 인형은 바구니에 쌓이고 만약 새로 뽑은 인형이 바구니의 가장 위에 있는 인형과 동일한 인형일 경우 인형은 터진다. 이때 터진 인형의 개수를 반환하면 된다.

문제풀이

이 문제를 해결하기 위해 가장 brute force적인 방법을 생각해보면 1. moves의 원소를 순회하면서 0이 아닌 지점까지 아래로 파고든다 2. 인형을 꺼낸 뒤, 해당 위치를 0으로 만든다. 3. 뽑은 인형은 스택에 저장한다. 만약 스택의 가장 위에 있는 인형과 똑같은 id를 공유한다면, 스택에서 pop한 뒤 answer에 2를 더해준다.

이 경우 시간복잡도는 \(O(n^2)\)이 된다.

같은 \(O(n^2)\)이긴 하지만, 필자는 시간을 더 줄이기 위해 top이란 1차원 배열을 추가로 생성한다. top의 원소는 각 열에서 인형이 놓여있는 가장 높은 위치를 말한다.

crane_game_101

이 경우의 top은 각각 [3,2,1,3,1]이다(맨 윗줄이 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
import java.util.*;

public class CrainDoll {
    public static void main(String[] args) {
        int[][] board = {
            {0,0,0,0,0},{0,0,1,0,3},{0,2,5,0,1},{4,2,4,4,2},{3,5,1,3,1}
        };
        int[] moves = {1,5,3,5,1,2,1,4};
        int answer = 0;
        int[] top = new int[board.length];
        Arrays.fill(top, 40);
        for(int c = 0; c < board.length; c++)
        {
            for(int r = 0; r < board.length; r++)
            {
                if(board[r][c] != 0)
                {
                    top[c] = r;
                    break;
                }
                    
            }
        }
        Stack<Integer> stack = new Stack<>();
        for(int i = 0; i < moves.length; i++)
        {
            if(top[moves[i]-1] < board.length)
            {
                int doll = board[top[moves[i]-1]][moves[i]-1];
                if(stack.empty())
                    stack.push(doll);
                else if(stack.peek() == doll)
                {
                    stack.pop();
                    answer += 2;
                }
                else
                    stack.push(doll);
                
                top[moves[i]-1]++;
            }
        }
        System.out.println(answer);
    }
  }

전체코드

1
2
3
4
5
6
7
int[][] board = {
    {0,0,0,0,0},{0,0,1,0,3},{0,2,5,0,1},{4,2,4,4,2},{3,5,1,3,1}
};
int[] moves = {1,5,3,5,1,2,1,4};
int answer = 0;
int[] top = new int[board.length];
Arrays.fill(top, 40);

문제 세팅을 위한 코드이다 board와 moves를 설정하고 터트려질 인형의 수를 answer라고 한다. 그리고 top의 길이는 board의 가로 또는 세로 사이즈로 설정한다. 이때 top을 0으로 초기화하면 안되는 이유는 유효한 값이기 때문이다. 문제에서 보드판은 30*30까지 될 수 있고 이말은, 0~29까지는 실제 인형이 있는 위치를 나타내는 숫자이다. 따라서 이 범위내에 있지 않은 숫자로 초기화한다.

1
2
3
4
5
6
7
8
9
10
11
12
for(int c = 0; c < board.length; c++)
{
    for(int r = 0; r < board.length; r++)
    {
        if(board[r][c] != 0)
        {
            top[c] = r;
            break;
        }
            
    }
}

top을 초기화하는 코드이다 board를 순회하는데 순회는 위에서 아래로 한줄씩 본다. 만약 처음으로 0이 아닌 숫자가 나오면 그 위치를 저장하고 다음 줄로 넘어간다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
Stack<Integer> stack = new Stack<>();
for(int i = 0; i < moves.length; i++)
{
    if(top[moves[i]-1] < board.length)
    {
        int doll = board[top[moves[i]-1]][moves[i]-1];
        if(stack.empty())
            stack.push(doll);
        else if(stack.peek() == doll)
        {
            stack.pop();
            answer += 2;
        }
        else
            stack.push(doll);
        
        top[moves[i]-1]++;
    }
}
System.out.println(answer);

바구니를 나타낼 stack을 선언한다 밑에 있는 for문은 앞서말한 3번과정을 나타낸다. 뽑아야하는 열이 주어질 때 top이 유효범위 내에 있다면 인형의 id를 저장한다. 만약 바구니가 비어있다면 스택에 인형을 집어넣는다. 만약 바구니의 맨 위에 있는 인형과 뽑은 인형이 같다면(else if문) 스택에서 인형을 꺼내고, 답을 2증가한다. 맨 위에있는 인형과 뽑은 인형이 같지 않다면 바구니에 넣어준다. 인형을 뽑고나면 top의 해당원소를 1증가하여 인형이 뽑혔다는 것을 저장한다.

테스트

crane_game_result

코딩테스트를 너무 늦게 준비해서 조급한 마음도 있지만 1레벨부터 찬찬히 풀어가야겠다.