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

public class RemoveMin {
    
    //프로그래머스 문제풀이 level1 제일 작은 수 제거하기
    public static void main(String[] args)
    {
        int[] arr = {4,3,2,1};
        
        ArrayList<Integer> sorted_list = new ArrayList<Integer>();
        for(int n : arr)
            sorted_list.add(n);
        ArrayList<Integer> unsorted_list = new ArrayList<Integer>();
        unsorted_list = (ArrayList<Integer>)sorted_list.clone();
        Collections.sort(sorted_list);
        
        Integer min = sorted_list.get(0);
        unsorted_list.remove(min);
        
        int[] answer = new int[unsorted_list.size() == 0 ? 1 : unsorted_list.size()];
        if(answer.length == 1)
            answer[0] = -1;
        else
        {
            for(int i = 0; i < unsorted_list.size(); i++)
                answer[i] = Integer.parseInt(unsorted_list.get(i).toString());
        }
    }
}
부분부분 살펴보자 
1
2
3
4
5
6
7
8
int[] arr = {4,3,2,1};
        
    ArrayList<Integer> sorted_list = new ArrayList<Integer>();
    for(int n : arr)
        sorted_list.add(n);
    ArrayList<Integer> unsorted_list = new ArrayList<Integer>();
    unsorted_list = (ArrayList<Integer>)sorted_list.clone();
    Collections.sort(sorted_list);
어레이리스트를 두개 선언하였다. 하나는 정렬을 하고 하나는 정렬하지 않은 것이다. 배열 내에서 제일 작은 수를 알기 위해 정렬을 하는 것인데, 결과 배열은 순서가 흐트러지면 안되므로 두개의 배열을 선언한것이다. 여기서의 시간복잡도는 O(nlogn)이다. 
1
2
Integer min = sorted_list.get(0);
unsorted_list.remove(min);
정렬한 배열의 첫번째 값을 가져와서 정렬하지 않은 배열에서 그 값을 제거한다. 시간복잡도는 O(n)이다. 
1
2
3
4
5
6
7
8
int[] answer = new int[unsorted_list.size() == 0 ? 1 : unsorted_list.size()];
if(answer.length == 1)
    answer[0] = -1;
else
{
    for(int i = 0; i < unsorted_list.size(); i++)
        answer[i] = Integer.parseInt(unsorted_list.get(i).toString());
}
제거한 값을 배열로 만들기 위해 위 코드와 같이 처리한다. 값을 제거한 배열이 빈 배열일 경우 -1을 집어넣어야 하므로 사이즈를 1로 지정하고 그게 아니라면 결과 사이즈로 int배열을 선언한다. 정답 배열의 크기가 1일 경우 -1을 넣고 그게 아니라면 배열을 그대로 담는다. 시간복잡도는 O(n)이다. 따라서 전체 시간복잡도는 O(nlogn)이다.

테스트



테스트케이스는 전부 통과하였지만 만약 테스트케이스가 [1,1,3]인 경우 내 알고리즘은 틀리게 된다. 그래도 통과가 된걸보니 그러한 케이스는 없었던 것 같다.

Posted on Edited on In , ,

문제정의

제곱근이 정수인지 판별하는 문제이다. 만약 제곱근이 정수라면 제곱근의+1의 제곱을 출력한다.

문제풀이

전체 코드는 다음과 같다. 

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

    //프로그래머스 문제풀이 level1 정수 제곱근 판별
    public static void main(String[] args)
    {
        long n = 121;
        long answer = 0;
        double fp;
        int ip;
        double root = Math.sqrt(n);
        ip = (int)root;
        fp = root - ip;
        if(fp > 0)
            answer = -1;
        else
            answer = (long)Math.pow(ip+1, 2);
        System.out.print(answer);
    }
    
}

제곱근이 정수라는 것은 소수부분이 0이어야 한다는 것이다. 주어진 정수 n의 제곱근을 구해 정수부와 소수부로 나눈다. 만약 소수부가 0보다 크면 정수가 아니라는 의미이므로 -1을 반환한다. 만약 소수부가 0이라면 정수부분의 +1하여 제곱한 값을 넘겨준다. 총 시간복잡도는 O(1)이다.

테스트



Posted on Edited on In , ,

문제정의

숫자를 입력받아 거꾸로 출력하는 문제이다.

문제풀이

전체 코드는 다음과 같다. 

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

public class NumDesc {
    
    //프로그래머스 문제 풀이 level1 정수 내림차순으로 배치하기
    public static void main(String[] args)
    {
        long n = 118372;
        long answer = 0;
        String s = Long.toString(n);
        char[] arr = s.toCharArray();
        Arrays.sort(arr);
        s = new StringBuilder(new String(arr)).reverse().toString();
        answer = Long.parseLong(s);
    }
}
숫자->문자열->정렬->문자열->숫자로 진행하였다. 총 시간복잡도는 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
import java.util.*;

public class FlipNumtoArr {

    //프로그래머스 문제풀이 level1 자연수 뒤집어 배열로 만들기
    public static void main(String[] args)
    {
        int n = 12345;
        ArrayList<Integer> list = new ArrayList<Integer>();
        while(n > 0)
        {
            long r = n%10;
            list.add((int)r);
            n /= 10;
        }
        int[] answer = new int[list.size()];
        for(int i = 0; i < list.size(); i++)
        {
            answer[i] = Integer.parseInt(list.get(i).toString());
        }
    }
    
}
어레이리스트를 만들어서 n%10한 값을 추가하고 n 나누기 10을 한다. 그리고 다시 배열로 바꾸면 된다. 총 시간복잡도는 O(log10(n))이다.

테스트



long을 int로 캐스팅 하면서 overflow가 일어나 처음에 테스트케이스를 통과하지 못했다. 그래서 처음에 나머지 연산을 하는 부분은 long으로 유지하고 값을 집어넣기 전에 int로 바꿨다.

Posted on Edited on In , ,

문제정의

숫자가 들어올 때 숫자의 자릿수를 모두 더해서 출력하는 문제이다.

문제풀이

전체 코드는 다음과 같다. 

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

    public static void main(String[] args)
    {   
        int n = 123;
        int answer = 0;
        String num = Integer.toString(n);
        char[] n_arr = num.toCharArray();
        for(char c : n_arr)
        {
            int temp = Integer.parseInt(String.valueOf(c));
            answer += temp;
        }
        System.out.print(answer);
    }
    
}

숫자를 문자열을 바꾼디 숫자를 문자배열로 쪼갠다. 그리고 전부 더하여 정답을 내면 된다. 총 시간복잡도는 O(log10(n))이다.

테스트



문자열로 바꾸지 않아도 10으로 나머지 연산을 반복함으로써 해결할 수도 있었다.

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

    //프로그래머스 level1 이상한 문자 만들기
    public static void main(String[] args)
    {
        String s = "try hello world";
        StringBuffer buff = new StringBuffer();
        int j = 0;
        for(int i = 0; i < s.length(); i++)
        {
            char c = s.charAt(i);
            String st = Character.toString(c);
            if(st.equals(" "))
                j = 0;
            if (c >='A' && c <= 'Z' || c >= 'a' && c <= 'z')
            {
                if(j%2 == 0)
                    st = st.toUpperCase();
                else
                    st = st.toLowerCase();
                j++;
            }
            buff.append(st);
            
        }
        String answer = buff.toString();
        System.out.print(answer);
    }
    
}

문자열에서 문자를 하나하나 뗀다. 또는 toCharArray()로 char배열을 생성해도 된다. 여기서 j라는 숫자는 단어를 공백에 맞춰 잘랐을 때, 단어의 인덱스를 나타내기 위함이다. 공백을 만났을 경우 이 j는 0으로 초기화된다. 알파벳을 만났을 경우 짝수나 홀수냐에 따라 대문자 또는 소문자로 바꿔준다. 나중에 다른사람의 풀이를 보니 단어를 이루고있는 요소들 중에 숫자나 특수문자는 없는 것 같았다. 하지만 테스트 케이스를 정확히 알 수 없기 때문에 필자는 문자인가에 대한 확인도 추가로 해주었다. 이렇게 변환한 문자열을 버퍼에 넣어 스트링으로 바꾸면 완성이다. 총 시간복잡도는 O(n)이다.

테스트



Posted on Edited on In , ,

문제정의

시저 암호를 프로그래밍하는 문제이다. 시저 암호를 만드는 방법은 문자열을 아스키코드로 n만큼 미뤄서 만들면 된다. 가령 abc가 있고 2가 주어진다면 cde이런식으로 만들 수 있다. 문제에서 알파벳에 대해서만 만들고 공백은 건들지 말라 했으므로, 알파벳에 대해서만 처리를 해주면 된다.

문제풀이

전체 코드는 다음과 같다. 

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 class CaesarCode {
    
    //프로그래머스 문제풀이 level1 시저 암호
    public static void main(String[] args)
    {
        String s = "AB";
        int n = 1;
        StringBuffer buff = new StringBuffer();
        for(int i = 0; i < s.length(); i++)
        {
            char c = s.charAt(i);
            int ascii = (int) c;
            if(ascii >= 65 && ascii <= 90)
            {
                ascii += n;
                if(ascii > 90)
                    ascii -= 26;
            }
            else if(ascii >= 97 && ascii <= 122)
            {
                ascii += n;
                if(ascii > 122)
                    ascii -= 26;
            }
            buff.append(String.valueOf((char) ascii));
        }
        String answer = buff.toString();
    }
}

문자열을 문자로 하나씩 뜯어서 본다. 만약 대문자라면 90을 넘어갈 경우 대문자 A로 돌아가야 한다. 따라서 첫번째 if문을 보면 대문자에 속할 경우 n을 더하고 Z의 아스키코드를 넘아가면 A로 돌아가게 하였다. 두번째 if문도 똑같은 원리로 하면 된다. 공백의 경우 아스키코드를 늘릴 필요가 없으므로 그대로 추가하면 된다. 총 시간복잡도는 O(n)이다.

테스트



필자의 경우 26을 빼주는 식으로 했는데 조금 다르게 풀 수도 있다. 주어진 문자가 소문자인지 대문자인지 판별한 후에(자바에는 친절하게 이 메소드를 제공한다.) 만약 소문자라면

((c - 'a')+n)%26 + 'a'

이런식으로 구할 수도 있다.

Posted on Edited on In , ,

문제정의

어떤 자연수 n이 주어졌을 때, 약수들의 합을 구하는 문제이다.

문제풀이

전체 코드는 다음과 같다. 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public class SumDivisor {
    
    //프로그래머스 문제풀이 level1 약수의 합
    public static void main(String[] args)
    {
        int n = 12;
        int answer = 0;
        for(int i = 1; i <= n; i++)
        {
            if(n%i == 0)
                answer += i;
        }
    }
}
간단한 문제이다. 1부터 n까지 가면서 만약 나누어 떨어지는 수라면 정답에 해당 약수를 더해나가면 된다. 총 시간복잡도는 O(n)이다.

테스트



Posted on Edited on In , ,

문제정의

배열 a와 b가 주어질 때 내적을 구하는 문제이다. 내적은 같은 인덱스로 둘을 짝지어 곱한 뒤, 전부 합산하면 된다.

문제풀이

전체 코드는 다음과 같다. 

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

    //프로그래머스 문제풀이 level1 내적

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

        int answer = 0;
        for(int i = 0; i < a.length; i++)
            answer += a[i]*b[i];
        System.out.print(answer);
    }

}

a와 b의 길이는 같으므로 둘 중 하나를 기준으로 배열을 순회하며 a와 b값을 곱해 더해나간다. 총 시간복잡도는 O(n)이다.

테스트



Posted on Edited on In , ,

문제정의

문자열을 정수로 변환하는 문제이다. 앞에는 부호(+,-)가 붙을 수 있다. 이 문제는 앞에 부호가 붙어있는지 확인한 다음, 그에 따라 달리 처리를 해주면 된다.

문제풀이

전체 코드는 다음과 같다. 

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

    public static void main(String[] args)
    {
        String s = "1234";
        int answer = 0;
        if(s.charAt(0) == '+')
            answer = Integer.parseInt(s.substring(1));
        if(s.charAt(0) == '-')
            answer = Integer.parseInt(s.substring(1)) * (-1);
        else
            answer = Integer.parseInt(s);
    }
    
}
'+'가 붙은 경우, 부호를 뺀 나머지를 int로 바꿔준다. '-'가 붙은 경우 '+'와 마찬가지로 문자열을 잘라내지만 int로 바꾼뒤에 -1을 곱해준다. 만약 아무 부호도 없을 경우 자연수이므로 문자열 전체를 int로 바꿔준다. 총 시간복잡도는 O(1)이다.

테스트