자몽 스토리

주어진 String 배열들 중 접두사인 경우가 존재하는지 찾는 문제이다.

1. 코드

풀이방법 1 :

이중 for문을 통한 완전탐색으로 코드를 작성했다.

startsWith로 접두어인지 검사한다.

(※startsWith는 타겟단어로 시작하는 말인지 검사, contain은 타겟단어를 포함하는 문자인지 검사)

class Solution {
    public boolean solution(String[] phone_book) {
        boolean answer = true;
        
        for(int i=0;i<phone_book.length;i++){
            for(int j=i+1;j<phone_book.length;j++){
                String now = phone_book[i];
                String now2 = phone_book[j];
                
                if(now.startsWith(now2)||now2.startsWith(now)){
                    return false;
                } 
            }
        }
        
        return answer;
    }
}

효율성 테스트 3,4를 통과하지 못했다.

풀이방법 2:

Arrays.Sort()로 String 배열을 정렬한다.

배열의 앞뒤 인덱스끼리 비교한다.

ex ) [123, 88, 888, 12, 12345]

Sort 정렬 : [12, 123, 12345, 88, 888]

import java.util.Arrays;

class Solution {
    public boolean solution(String[] phone_book) {
        boolean answer = true;
        Arrays.sort(phone_book);
        
       for(int i=0; i<phone_book.length -1 ; i++){
           if(phone_book[i+1].startsWith(phone_book[i]))
               return false;
       }
        
       return true;
    }
}

이 코드로 효율성검사까지 통과하였다.

주어진 int 배열(nums)의 중복을 제거하는 문제이다.

중복값을 담지 않는 HashSet이용하여 문제를 풀었다.

1. 문제해설

배열의 길이의 1/2만큼 폰켓몬을 가져가기 때문에 최대 가져갈수 있는 값을 maxCnt로 선언한다.

HashSet에 배열의 종류를 담고, 담긴 Set의 길이와 maxCnt를 비교하여 리턴한다.

2. 코드

import java.util.*;

class Solution {
    public int solution(int[] nums) {
        int answer = 0;
        HashSet<Integer> hs =new HashSet<Integer>();
        int maxCnt = nums.length/2;
        
        //HashSet에 배열값을 담음(중복제거)
        for(int a : nums){
            hs.add(a);
        }
        
        //Set사이즈가 더 클경우 maxCnt를 리턴한다.
        if(hs.size() > maxCnt){
            answer = maxCnt;  
        }else{
            answer = hs.size();
        }
        
        
        return answer;
    }
}

임의의 수에 대해 k만큼의 갯수의 수를 제거하고 그 중에서 가장 큰 수를 찾는 문제이다.

나는 Greedy(탐욕법) 탐색을 통해 문제를 풀었다.

1. 문제 해설

이중 for문을 사용하여

number = "1234123"

k = 3 일때

첫번째 for문의 조건은 반환해야하는 숫자의 자릿수만큼 loop를 돌려준다.

따라서 i는 0부터 number.length()-k  전 까지 돌려준다. ( 예시로 치면 0~3까지 )

이중 for문의 안쪽 for문은 기준 인덱스부터 뒤에 붙여야하는 자릿수의 전 인덱스까지 loop를 돌려준다.

따라서 j는 index부터 i+k까지 돌려준다. (예시로 치면 0~3, 4~4...)   

또한 String을 이어붙이는 것이 아니라 Stringbuilder를 사용하면 좀 더 효율적으로 String을 이어붙여 리턴 할 수 있다.

2. 코드

class Solution {
    public String solution(String number, int k) {
        int index=0;
        int max=0;
        //StringBuilder를 사용하면 효율성 증가
        StringBuilder sb = new StringBuilder();
        
        for(int i=0; i<number.length()-k; i++){
            max =0;
            for(int j=index; j<=i+k; j++){
                if(max < number.charAt(j) -'0'){
                    max = number.charAt(j) - '0';
                    index = j+1; //다음 인덱스부터 검사하도록
                }
            }
            sb.append(max);
        }
        
        return sb.toString();
    }
}

number.charAt(j)를 int값과 비교를 하기위해서는

number.charAt(j)값이 아스키코드값을 반환하기때문에 '0'(아스키코드값 48)을 빼줌으로 써

int값과 비교가 가능해진다.

임의의 값이 주어지면 피보나치 수를 구해 그 값을 1234567로 나누는 문제이다.

나는 재귀적 함수 호출 방법으로 첫번째 답변을 작성했다.

1. 재귀적 방법

class Solution {
    public int solution(int n) {
        int answer = 0;
        int a = fibo(n);
        answer = a % 1234567;     
        return answer;
    }
    
    //재귀함수
    public int fibo(int n){
        if(n<=1){
            return n;
        }else{
            return fibo(n-1)+fibo(n-2);
        }
    }
}

위와 같은 방법으로 답변을 제출하니 몇가지 케이스에 대해 시간초과가 발생하였다.

2. 반복문 사용

class Solution {
    public int solution(int n) {
        int answer = 0;
        int fn1 = 0;
        int fn2 = 1;
        
        for(int i=2;i<=n;i++){
            answer = (fn1 + fn2) % 1234567;
            fn1 = fn2;
            fn2 = answer;
        }      
        return answer;
    }
}

위와 같이 반복문을 사용하니 효율성면에서 통과되었다.

재귀적방법이 직관적이나, 연산이 많이 필요하여 효율성이 떨어진다.

따라서 이 피보나치 수의 경우에는 반복문으로 통한 풀이가 효율성 측면에서 더 낫다.