Rabbit blog

Rabbit blog
0%

Posted on Edited on In , ,

문제정의

서로 마주보고 탕수육을 번갈아 말하는 게임을 해본적이 있을 것이다. 이 문제도 딱 그런 느낌이다. 수와 박을 번갈아가면서 n번 말했을 때 문자열을 출력하면 된다.

문제풀이

전체 코드는 다음과 같다. 

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

    public static void main(String[] args)
    {
        int n = 3;
        StringBuffer buff = new StringBuffer();
        for(int i = 0; i < n; i++)
        {
            if(i % 2 == 0)
                buff.append("수");
            else
                buff.append("박");
        }
        String answer = buff.toString();
        System.out.print(answer);
    }
    
}
0이 첫번째 숫자이자 짝수이므로 0부터 n-1까지 짝수인지 홀수인지 판별하여 수와 박을 버퍼에 붙여준다. 총 시간복잡도는 O(n)이다.

테스트



Posted on Edited on In , ,

문제정의

최대 자연수 값 n이 주어질 때 [1,n]에서 소수가 몇 개 있는지 출력하는 문제이다. 필자의 경우 첫번째 시도를 시간초과로 틀렸다. 그래서 질문하기를 보니 에라토테네스의 체(어떤 사람을 이걸 에라이체라고 하더라)를 활용하면 풀 수 있다고 했다. 이용했더니 한번에 풀림! 에라토테네스의 체는 큰 수가 소수가 맞는지 아닌지에 대한 판별을 할 때 유용하다고 한다. 간단히 설명을 하자면 25가 소수인지 알고 싶을 때, 2~24까지 전부 나눠보는 것이 아니라 그의 제곱근인 5를 2~5로 나눠보면 된다는 것이다. 왜 제곱근까지 나눠보면 되냐면 우리가 어떠한 수를 나눌 때 몫이 생긴다. 이 몫이 그 수의 제곱근이하이기 때문이라고 한다(더 자세히 알고 싶은 사람은 검색해보자.). 아무튼 이 원리를 이용하고 효율성 검사까지 모두 통과하였다.

문제풀이

전체 코드는 다음과 같다. 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public class PrimeNum {
    
    public static void main(String[] args)
    {
        int n = 10;
        int answer = 0;
        boolean add = true;
        for(int i = 2; i <= n; i++)
        {
            add = true;
            for(int j = 2; j <= Math.sqrt(i); j++)
            {
                if(i%j==0)
                {
                    add = false;
                    break;
                } 
            }
            if(add)
                answer++;
                
        }
    }
}
1은 소수가 아니므로 2부터 n까지 i가 소수인지 검토하는 프로그램을 짰다. 원래 두번째 for문에서 i-1까지 나눠보는 걸로 하였는데, 에라토테네스의 체로 제곱근까지 나눠본다. 이때 등호를 넣어준 이유는 제곱근이 자연수로 딱 떨어지는 경우가 있기 때문이다. 가령 4가 소수인지 판별하기 위해선 2까지 해당하는 약수가 있는지 봐야한다. 소수판별은 위와 같이 가능하다. 소수 판별을 한다는 것을 저장하기 위해 add라는 플래그를 세워두었다. 만약 약수가 하나라도 존재하면 add는 false가 되어 answer++문을 넘어간다. 총 시간복잡도는 O(nn)이다.

테스트



Posted on Edited on In , ,

문제정의

'김서방은 ?에 있다.'라는 형식으로 출력하면 된다. 여기서 ?는 배열에서 "Kim"이 있는 위치이다.

문제풀이

전체 코드는 다음과 같다. 

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

    public static void main(String[] args)
    {
        String[] seoul = {"Jane", "Kim"};
        int idx = -1;
        for(int i = 0; i < seoul.length; i++)
        {
            if(seoul[i].equals("Kim"))
            {
                idx = i;
                break;
            }
                
        }
        StringBuffer buff = new StringBuffer();
        buff.append("김서방은 ");
        buff.append(Integer.toString(idx));
        buff.append("에 있다");
        String answer = buff.toString();
        System.out.print(answer);
    }
    
}

배열을 순회하면서 "Kim"이 있는 위치를 찾는다. Kim을 찾는 순간 더 이상 배열을 탐색할 필요가 없으므로 break문을 통해 탈출하고 정답을 출력한다. 총 시간복잡도는 O(n)이다.

테스트



Posted on Edited on In , ,

문제정의

주어진 문자열이 특정 조건을 만족하는지 확인하는 문제이다. 문자열은 4또는 6의 길이를 갖고 있어야하며, 전부 숫자로 이루어져 있어야한다.

문제풀이

전체 코드는 다음과 같다. 

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

    public static void main(String[] args)
    {
        String s = "a234";
        boolean answer = false;
        if(s.length() == 4 || s.length() == 6)
        {
            answer = true;
            for(int i = 0; i < s.length(); i++)
            {
                char c = s.charAt(i);
                int ascii = (int)c;
                if(c > 57 || c < 48)
                    answer = false;
            }
                
        }
    }
    
}
첫번째로 문자열의 길이가 4또는 6을 만족하는지 확인한다. 길이를 만족하면 true로 답을 바꾼다. 그 다음 조건으로 모든 문자열의 문자가 숫자인지 아스키코드로 확인한다. 만약 만족하지 않는 문자가 존재한다면 answer를 false로 바꾼다. 총 시간복잡도는 O(n)이다.

테스트



다른 사람의 풀이를 보니 NumberFormatException을 활용하여 문제를 푼 사람이 있었다. 문자열을 int로 파싱하는데 에러가 나면 answer를 false로 바꾸는 것이다.

Posted on Edited on In , ,

문제정의

주어진 문자열을 내림차순으로 정렬하는 문제이다.

문제풀이

전체 코드는 다음과 같다. 

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

public class strDesOrder {

    public static void main(String[] args)
    {
        String s = "Zbcdefg";
        char[] arr = new char[s.length()];
        for(int i = 0; i < s.length(); i++)
        {
            arr[i] = s.charAt(i);
        }
        Arrays.sort(arr);
        String answer = new StringBuilder(new String(arr)).reverse().toString();
    }
    
}

문자열을 char[]로 쪼개어 정렬한 뒤, 역순으로 정렬하였다. 총 시간복잡도는 O(n)이다.

테스트



자바메소드 중 toCharArray()라는 메소드가 있었다. 앞으론 그 메소드를 활용하여 풀어야겠다.

Posted on Edited on In , ,

문제정의

문자열 내에 p와 y의 개수를 세어 둘 다 동일하면 true를 그렇지 않다면 false를 반환한다.

문제풀이

전체 코드는 다음과 같다. 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public class CntpCnty {
    
    public static void main(String[] args)
    {
        String s = "pPoooyY";
        boolean answer = true;
        int p = 0, y = 0;
        s = s.toLowerCase();
        for(int i = 0; i < s.length(); i++)
        {
            if(s.charAt(i) == 'p')
                p++;
            else if(s.charAt(i) == 'y')
                y++;
        }
        
        if(p!=y)
            answer = false;
    }
}
toLowerCase를 이용해 문자열에 있는 모든 문자를 소문자로 바꾸었다. 그리고 하나씩 비교하여 p와 y의 개수를 센다. 만약 두 수가 같지 않다면 answer를 false로 바꾼다. 총 시간복잡도는 O(n)이다.

테스트



p와 y의 변수를 따로 해서 계산하였는데, 다른 사람의 풀이를 보니 변수르 하나로 하여 증감을 이용해 푸는 것을 보았다. 변수 하나 차이긴 하지만 코드를 줄일 수 있는 방법 중에 하나로 기억해놔야겠다.

Posted on Edited on In , ,

문제정의

새로운 기준으로 문자열을 정렬하는 문제이다. 문자열의 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
import java.util.*;

public class SortString {

    public static void main(String[] args)
    {
        String[] strings = {"abce", "abcd", "cdx"};
        int n = 1;
        
        Arrays.sort(strings, new Comparator<String>(){
            @Override
            public int compare(String o1, String o2){
                if(o1.charAt(n) > o2.charAt(n))
                    return 1;
                else if(o1.charAt(n) < o2.charAt(n))
                    return -1;
                else
                {
                    return o1.compareTo(o2);
                }
            }
        });

    }
}
문제 그대로 comparator를 정의하여 sort했다. 최종적으로 시간복잡도는 O(nlogn)이다.

테스트



필자와 같이 비교하는 연산을 새로 정의하여 쓸 수도 있지만, 다른 사람 풀이 중에 흥미로운 게 있어서 여기에 적어둔다. 문자열 배열에 n번째 문자를 단어의 맨 앞에 추가하여 저장한다. 그리고 이를 정렬하면 따로 비교자를 정의하지 않고도 정렬을 할 수 있다.

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
22
23
24
25
26
27
28
29
import java.util.*;

public class Mod0Arr {

    public static void main(String[] args)
    {
        int[] arr = {5, 9, 7, 10};
        int divisor = 5;
        ArrayList<Integer> list = new ArrayList<>();
        for(int num : arr)
        {
            if(num%divisor == 0)
                list.add(num);
        }
        if(list.size() == 0)
        {
            int[] answer = {-1};
        }
        else
        {
            Collections.sort(list);
            int[] answer = new int[list.size()];
            for(int i = 0; i < list.size(); i++)
                answer[i] = Integer.parseInt(list.get(i).toString());
        }
    }
    
}

부분부분 살펴보자 
1
2
3
4
5
6
7
8
int[] arr = {5, 9, 7, 10};
int divisor = 5;
ArrayList<Integer> list = new ArrayList<>();
for(int num : arr)
{
    if(num%divisor == 0)
        list.add(num);
}
어레이리스트를 선언하고 배열을 순회하면서 만약 딱 나누어 떨어지는 수라면 리스트에 원소를 집어넣는다. 이 부분의 시간복잡도는 O(n)이다.

1
2
3
4
5
6
7
8
9
10
11
if(list.size() == 0)
{
    int[] answer = {-1};
}
else
{
    Collections.sort(list);
    int[] answer = new int[list.size()];
    for(int i = 0; i < list.size(); i++)
        answer[i] = Integer.parseInt(list.get(i).toString());
}

만약 아무 원소도 들어가있지 않다면 -1을 넣어 반환하고 그렇지 않다면 리스트를 정렬하여 정답배열에 답을 넣는다. 이 부분에서 시간복잡도는 정렬이 있기 때문에 O(nlogn)이다.

테스트



화면이 작아 약간 잘렸는데 아무튼 다 맞았다.

Posted on Edited on In , ,

문제정의

배열이 주어졌을 때, 중복을 제거한 배열을 반환하는 문제이다. 단, 배열의 순서는 유지되어야 한다.

문제풀이

디큐를 활용하여 문제를 풀자 디큐는 스택과 큐의 성질을 동시에 가지고 있는 자료구조이다. 그렇다면 이 문제는 스택과 큐의 성질을 둘다 이용하고 싶기 때문에 이용했다고 보면된다. 중복을 제거하는 방법은 조금만 생각해보면 쉽게 알 수 있다. 바로 그 전 숫자와 같은지 같지 않은지 확인하면 된다. 그러면 스택으로만 풀 수 있다고 반문하는 사람이 있겠지만 이 역시 아니다 스택을 활용할 경우 중복은 제거할 수 있지만, 순서를 유지할 수 없다. 스택은 LIFO이기 때문이다. 그래서 큐의 성질이 FIFO가 필요하고 이것이 디큐를 사용한 이유이다. 물론 스택을 굳이 사용하겠다면 방법은 있다. 스택을 통해 중복을 제거한뒤 배열에 거꾸로 담거나, 역전을 시켜주거나 방법은 많다. 여러 방법으로 이 문제를 풀어보고 시간복잡도도 함께 계산해보면 좋은 공부가 될 수 있을 것이다.

전체 코드는 다음과 같다. 

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 NoSameNum {

    public static void main(String[] args)
    {
        int[] arr = {1,1,3,3,0,1,1};
        Deque<Integer> dq = new ArrayDeque<>();
        dq.add(arr[0]);
        for(int i = 1; i < arr.length; i++)
        {
            if(Integer.parseInt(dq.getLast().toString()) != arr[i])
                dq.add(arr[i]);
        }
        int[] answer = new int[dq.size()];
        int j = 0;
        while(dq.size() != 0)
        {
           answer[j++] = Integer.parseInt(dq.poll().toString());
        }
    }
    
}
부분부분 살펴보자 
1
2
3
4
5
6
7
Deque<Integer> dq = new ArrayDeque<>();
dq.add(arr[0]);
for(int i = 1; i < arr.length; i++)
{
    if(Integer.parseInt(dq.getLast().toString()) != arr[i])
        dq.add(arr[i]);
}
디큐를 선언하고 0번째 값을 디큐에 넣어놓는다. 디큐의 add는 끝부터 채워진다. 디큐의 가장 마지막 원소와 현재 들어갈 원소값을 비교하여 연달아 나타나지 않을 때 값을 집어넣는다. 이 부분에서 시간 복잡도는 O(n)이다.

1
2
3
4
5
6
int[] answer = new int[dq.size()];
int j = 0;
while(dq.size() != 0)
{
    answer[j++] = Integer.parseInt(dq.poll().toString());
}

이제 디큐의 앞에서부터 값을 꺼내서 int형태로 바꾸어 answer에 저장하면 된다. 이부분 역시 시간복잡도는 O(n)이다. 이로써 총 시간복잡도는 O(n)이 된다.

테스트



화면이 작아 약간 잘렸는데 아무튼 다 맞았다.

Posted on Edited on In , ,

문제정의

어떤 문자열이 주어졌을 때 문자열의 가운데 문자를 반환하는 문제이다 만약 문자열이 짝수일 경우 가운데 두 글자를 반환한다.

문제풀이

문자열의 사이즈를 구해서 /2를 하는 식으로 가운데 문자를 출력해줘야한다. 짝수인경우와 홀수인 경우를 다르게 해서 구해주면 된다.

전체 코드는 다음과 같다. 

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

public class BringMiddleLetter {

    public static void main(String[] args)
    {
        String s = "power";
        String answer = "";
        int l = s.length();
        if(l%2 == 1)
        {
            answer = String.valueOf(s.charAt(l/2));
        }
        else
        {
            answer = String.valueOf(s.charAt((l/2)-1)) + String.valueOf(s.charAt(l/2));
        }
        System.out.print(answer);
    }
    
}

문자열이 홀수인 경우 문자열의 길이/2로 구할 수 있다. 짝수의 경우 문자열의 길이/2-1과 문자열의 길이/2로 구할 수 있다.

이 문제의 시간복잡도는 O(1)이다.

테스트



홀수 길이와 짝수 길이로 분기처리를 하지 않고도 문제를 풀 수 있는 방법이 있었다. substring을 반환하는 함수의 범위를 [(문자열의 길이-1)/2, (문자열의 길이)/2 +1)로 하면 된다.