Rabbit blog

Rabbit blog
0%

Posted on Edited on In , ,

문제정의

a를 가로길이로 b를 세로길이로 하는 직사각형을 만드는 문제이다. 직사각형을 별문자를 통해 나타낸다.

문제풀이

전체 코드는 다음과 같다. 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
import java.util.Scanner;

public class MakeRectangle {

    //프로그래머스 문제 풀이 level1 직사각형 별찍기
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int a = sc.nextInt();
        int b = sc.nextInt();
        
        for(int i = 0; i < b; i++)
        {
            for(int j = 0; j < a; j++)
                System.out.print("*");
            System.out.println();
        }
    }
}

열(a)만큼 별을 찍어준 다음에는 줄바꾸기를 해야하므로 위와 같이 코드를 작성하였다. 시간복잡도는 \(O(a*b)\)이다.

테스트



Posted on Edited on In , ,

문제정의

x가 초항이자 공차인 등차수열을 n만큼 만드는 것이다.

문제풀이

전체 코드는 다음과 같다. 

1
2
3
4
5
6
7
8
9
10
11
12
13
public class NNumXSpace {

    //프로그래머스 문제 풀이 level1 x만큼 간격이 있는 n개의 숫자
    public static void main(String[] args)
    {
        int x = 2, n = 5;
        long[] answer = new long[n];
        answer[0] = x;
        for(int i = 1; i < n; i++)
            answer[i] = answer[i-1]+x;
    }
    
}
정답배열의 첫번째 항을 x로 초기화 한 뒤, 등차수열을 만들 듯 이전 항에 x만큼 더하면 된다. 시간복잡도는 \(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
public class AddMatrix {

    //프로그래머스 문제풀이 level1 행렬의 덧셈
    public static void main(String[] args)
    {
        int[][] arr1 = {
            {1, 2},
            {2, 3}
        };
        int[][] arr2 = {
            {3, 4},
            {5, 6}
        };

        int[][] answer = new int[arr1.length][arr1[0].length];
        for(int i = 0; i < arr1.length; i++)
        {
            for(int j = 0; j < arr1[0].length; j++)
                answer[i][j] = arr1[i][j] + arr2[i][j];
        }
    }
    
}
2중 for문으로 모든 원소를 돌아보며 합을 구하면 된다. 주어진 행렬의 행을 n, 열을 m이라고 할 때, 모든 원소를 순회하므로 시간복잡도는 \(O(n*m)\)이다.

테스트



Posted on Edited on In , ,

문제정의

휴대폰 번호의 마지막 4자리를 제외하고 *로 가리는 문자열을 만드는 문제이다.

문제풀이

전체 코드는 다음과 같다. 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public class PhoneNumBlind {

    //프로그래머스 문제 풀이 level1 휴대폰 번호 가리기
    public static void main(String[] args)
    {
        String phone_number = "01033334444";
        StringBuilder buff = new StringBuilder();
        for(int i = 0; i < phone_number.length()-4; i++)
            buff.append("*");
        buff.append(phone_number.substring(phone_number.length()-4, phone_number.length()));
        String answer = buff.toString();

        System.out.print(answer);
    }
    
}
스트링 버퍼를 생성하여 끝에 4자리를 남겨두고 *을 추가한 다음에 나머지 4자리를 원래 문자열에서 잘라붙여 만들었다. 이 알고리즘의 총 시간복잡도는 휴대폰 번호의 총 길이를 n이라 할 때 \(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
public class HarshardNum {

    //프로그래머스 문제풀이 level1 하샤드 수
    public static void main(String[] args)
    {
        int x = 10;
        boolean answer = true;
        int n = x;
        int q = 0;
        while(n > 0)
        {
            q += n%10;
            n /= 10;
        }
        if(x % q != 0)
            answer = false;

        System.out.print(answer);
    }
    
}
나누는 수 q를 구하는 부분을 주목해서 보면 된다. 각 자릿수를 더하는 것은 10으로 나머지 연산을 하고 10으로 나누면 된다. 이 알고리즘의 총 시간복잡도는 자릿수만큼 반복하므로 \(O(log10(n))\)이다.

테스트



Posted on Edited on In , ,

문제정의

평균을 구하는 문제이다.

문제풀이

전체 코드는 다음과 같다. 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public class GetAverage {

    public static void main(String[] args)
    {
        int[] arr = {1, 2, 3, 4};
        double answer = 0;
        int sum = 0;
        for(int i = 0; i < arr.length; i++)
            sum += arr[i];
        answer = (double)sum / (double)arr.length;
        System.out.print(answer);
    }
    
}
간단하다 모든 원소의 합을 배열의 크기로 나누면 된다. 시간복잡도는 배열의 크기를 n이라 할 때, \(O(n)\)이다.

테스트



Posted on Edited on In , ,

문제정의

콜라츠 추측을 몇 번 반복해야 1이 나오는지 계산하는 문제이다. 짝수인 경우 2로 나누고, 홀수인 경우 3을 곱하고 1을 더한다. 500번을 계산해도 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
24
25
26
27
28
29
public class CollatzGuess {

    //프로그래머스 문제풀이 level1 콜라스 추측
    public static void main(String[] args)
    {
        int num = 6;
        int answer = 0;
        int cnt = 0;
        long ll = num;
        while(cnt <= 500)
        {
            if(ll == 1)
                break;
            else if(ll % 2 == 0)
                ll /= 2;
            else
                ll = ll*3+1;
            cnt++;
        }
        if(cnt <= 500)
            answer = cnt;
        else
            answer = -1;

        System.out.print(answer);

    }
    
}
문제에서 제시한대로 코드를 짜면 된다. cnt를 0으로 초기화하고, 짝수면 나누기, 홀수면 곱하기 더하기 연산을 하면된다. 중요한 부분은 int를 쓰지 않고 long을 쓴 것을 볼 수 있는데, 이유는 곱하기 연산을 하면서 int값을 초과할 수 있기 때문이다. 필자는 이것 때문에 한번 틀렸었다. 이 문제 정의에서 이 알고리즘의 시간복잡도는 \(O(1)\)이다. 왜냐하면 500이라는 횟수가 최대 실행 횟수이기 때문이다.

테스트



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
public class BigDivSmallMul {

    //프로그래머스 문제 풀이 level1 최대공약수와 최소공배수
    public static void main(String[] args)
    {
        int n = 3, m = 12;
        int[] answer = new int[2];
        int min, max;
        min = Math.min(n, m);
        max = Math.max(n, m);
        int big_div = -2, small_mul = -2;
        for(int i = 1; i <= min; i++)
        {
            if(min%i == 0 && max%i == 0)
                big_div = i;
        }
        int temp = max;
        while(true)
        {
            if(temp % min == 0 && temp % max == 0)
            {
                small_mul = temp;
                break;
            }
            temp++;
        }
        answer[0] = big_div;
        answer[1] = small_mul;
    }
    
    
}
부분부분 보도록 하자 
1
2
3
4
5
6
7
8
9
10
11
int n = 3, m = 12;
int[] answer = new int[2];
int min, max;
min = Math.min(n, m);
max = Math.max(n, m);
int big_div = -2, small_mul = -2;
for(int i = 1; i <= min; i++)
{
    if(min%i == 0 && max%i == 0)
        big_div = i;
}
n과 m중에 크고 작은 값을 각각 min, max에 담았다. 최대공약수는 min값보다 클 수 없으므로 1에서 min까지 보면서 나눌 수 있는 최대를 big_div에 담는다. 여기서 n,m중 더 작은 값을 a라고 하면 시간복잡도는 \(O(a)\)로 볼 수 있다.

1
2
3
4
5
6
7
8
9
10
int temp = max;
while(true)
{
    if(temp % min == 0 && temp % max == 0)
    {
        small_mul = temp;
        break;
    }
    temp++;
}

최소공배수는 max값이상이어야 한다. temp값을 max로 한 뒤, temp를 증가하면서 처음으로 나누어떨어지는 수가 있으면 최소공배수 값을 업데이트하고 반복문을 탈출한다. 이 부분에서도 시간복잡도는 \(O(a)\)라는 것을 알 수 있다. 왜냐하면 최소공배수가 가장 큰 경우가 n*m이기 때문이다. 따라서 총 알고리즘의 시간복잡도는 \(O(a)\) \(a = min(n,m)\)이다.

테스트



Posted on Edited on In , ,

문제정의

주어진 숫자가 홀수이면 "Odd"를 출력하고 짝수라면 "Even"을 출력하는 문제이다.

문제풀이

전체 코드는 다음과 같다. 

1
2
3
4
5
6
7
8
9
10
11
12
public class EvenOdd {

    //프로그래머스 문제 풀이 level1 짝수와 홀수
    public static void main(String[] args)
    {
        int num = 3;
        String answer = num % 2 == 0 ? "Even" : "Odd";
        System.out.print(answer);
    }
    
}

2로 나누어서 0이 나온다면 짝수이므로 "Even"을 넣고 0이 아니라면 홀수라는 의미이므로 "Odd"를 넣는다. 따라서 전체 시간복잡도는 \(O(1)\)이다.

테스트



Posted on Edited on In , ,

문제정의

키패드를 어느 쪽 손으로 눌러야 하는 가에 대한 문제이다. 초기 왼손의 위치는 *에 오른손의 위치는 #에 위치해있다. 1,4,7은 무조건 왼손으로 누르고 3,6,9는 오른손으로 누른다. 손가락은 상하좌우로만 움직일 수 있다. 2,5,8,0은 왼손과 오른손 중 더 가까이 있는 손가락으로 누르며, 만약 두 손가락이 움직이는 거리가 같은 경우 주로 쓰는 손으로 누른다. 눌러야할 번호들이 주어지면 어느쪽 손으로 누르는지 "L"과 "R"로 구성된 문자열로 나타내라.



## 문제풀이

전체 코드는 다음과 같다. 

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
public class KeyPad {

    public static void main(String[] args)
    {
        int[] numbers = {1, 3, 4, 5, 8, 2, 1, 4, 5, 9, 5};
        String hand = "right";

        StringBuilder buff = new StringBuilder();
        int left_pos = 10, right_pos = 11;
        boolean isleft = false;
        int[][] moves = {
            {0, -1, 3, -1, -1, 2, -1, -1, 1, -1}, //0
            {4, -1, 1, -1, -1, 2, -1, -1, 3, -1}, //1
            {3, -1, 0, -1, -1, 1, -1, -1, 2, -1}, //2
            {4, -1, 1, -1, -1, 2, -1, -1, 3, -1}, //3
            {3, -1, 2, -1, -1, 1, -1, -1, 2, -1}, //4
            {2, -1, 1, -1, -1, 0, -1, -1, 1, -1}, //5
            {3, -1, 2, -1, -1, 1, -1, -1, 2, -1}, //6
            {2, -1, 3, -1, -1, 2, -1, -1, 1, -1}, //7
            {1, -1, 2, -1, -1, 1, -1, -1, 0, -1}, //8
            {2, -1, 3, -1, -1, 2, -1, -1, 1, -1}, //9
            {1, -1, 4, -1, -1, 3, -1, -1, 2, -1}, //10(*)
            {1, -1, 4, -1, -1, 3, -1, -1, 2, -1} //11(#)
        };
        
        for(int num : numbers)
        {
            if(num == 1 || num == 4 || num == 7)
                isleft = true;
            else if(num == 3 || num == 6 || num == 9)
                isleft = false;
            else
            {
                int left_dist = moves[left_pos][num];
                int right_dist = moves[right_pos][num];
                if(left_dist < right_dist)
                    isleft = true;
                else if(right_dist < left_dist)
                    isleft = false;
                else
                {
                    if(hand.equals("left"))
                        isleft = true;
                    else
                        isleft = false;
                }
            }
            if(isleft)
            {
                buff.append("L");
                left_pos = num;
            }
            else
            {
                buff.append("R");
                right_pos = num;
            }
        }
        
        String answer = buff.toString();
        System.out.print(answer);
    }
    
}
부분부분 보도록 하자 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
StringBuilder buff = new StringBuilder();
int left_pos = 10, right_pos = 11;
boolean isleft = false;
int[][] moves = {
    {0, -1, 3, -1, -1, 2, -1, -1, 1, -1}, //0
    {4, -1, 1, -1, -1, 2, -1, -1, 3, -1}, //1
    {3, -1, 0, -1, -1, 1, -1, -1, 2, -1}, //2
    {4, -1, 1, -1, -1, 2, -1, -1, 3, -1}, //3
    {3, -1, 2, -1, -1, 1, -1, -1, 2, -1}, //4
    {2, -1, 1, -1, -1, 0, -1, -1, 1, -1}, //5
    {3, -1, 2, -1, -1, 1, -1, -1, 2, -1}, //6
    {2, -1, 3, -1, -1, 2, -1, -1, 1, -1}, //7
    {1, -1, 2, -1, -1, 1, -1, -1, 0, -1}, //8
    {2, -1, 3, -1, -1, 2, -1, -1, 1, -1}, //9
    {1, -1, 4, -1, -1, 3, -1, -1, 2, -1}, //10(*)
    {1, -1, 4, -1, -1, 3, -1, -1, 2, -1} //11(#)
};
정답을 담을 StringBuilder buff를 선언한다. 초기 왼손은 *에 있고 오른손은 #에 있을때 이를 각각 10과 11로 지정한다. 그리고 moves를 작성한다. 번거로울 수 있지만, 마땅한 식이 떠오르지 않을 때 빠르게 문제를 풀 수 있다. 행이 시작점을 나타내고 열을 끝나는 점이라고 했을 때, 움직이는 횟수를 기록하였다. 예를들면 1에서 0으로 가기까지는 moves[1][0]에 해당하는 수이므로 4가 된 것을 볼 수 있다. 다음으로 boolean값에 해당하는 isleft를 선언한다. 이는 왼손으로 키패드를 눌러야하는지 나타내는 변수로 초기화는 아무렇게나 해도 상관없다. 필자는 false로 초기화하였다.

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
for(int num : numbers)
{
    if(num == 1 || num == 4 || num == 7)
        isleft = true;
    else if(num == 3 || num == 6 || num == 9)
        isleft = false;
    else
    {
        int left_dist = moves[left_pos][num];
        int right_dist = moves[right_pos][num];
        if(left_dist < right_dist)
            isleft = true;
        else if(right_dist < left_dist)
            isleft = false;
        else
        {
            if(hand.equals("left"))
                isleft = true;
            else
                isleft = false;
        }
    }
    if(isleft)
    {
        buff.append("L");
        left_pos = num;
    }
    else
    {
        buff.append("R");
        right_pos = num;
    }
}
    
String answer = buff.toString();

논리적으로 어려운 부분은 없다. 1,4,7인경우에는 왼손으로 누르므로 isleft를 true값으로 변경한다. 3,6,9인 경우 false로 바꾼다. 만약 중간에 있는 키패드인 경우 moves 값을 비교하여 판별한다. 만약 값이 같은 경우 어느 손잡이인지 보면 된다. 키패드를 누를 때마다 현재 있어야 하는 위치값을 업데이트 하는 것을 잊지 말자. numbers의 길이를 n이라고 하면 이 알고리즘의 시간복잡도는 \(O(n)\)이다.

테스트



옛날에 멋모르고 인턴에 지원했다가 이 문제만 2-3시간 풀고 포기한 경험이 있다. 그래서 그 때의 안 좋은 감정이 차올랐는데, 이번에는 30분정도 걸렸다. 내가 성장하고 있는 걸 느껴서 기쁘다. 첨언을 하자면 키패드를 자세히 보면 3으로 나머지연산과 나누기 연산을 하면 키패드의 어느 위치에 있는지 쉽게 알 수 있다. 이걸 활용하면 코드를 더 간결하게 만들 수 있을거라 생각한다.