프로그래머스LV2_7

연속 부분 수열 합의 개수

접근 과정

1. 원형으로 수열을 연결되게 만들어서 각 위치를 시작으로 해당 크기만큼 더한다.
2. 더한 값을 Set에 넣어 중복을 없앤다.
3. Set의 크기를 반환하면 해결

시행착오

• 문제 접근을 생각하고 구현을 못해 헤맸다. 천천히 접근대로 구현할 수 있도록 연습해야겠다.
  

해결 코드

• 구현 연습이 필수적!
• for문이 현재 3개라서 조금 더 개선을 시도하였다.
  • 생각해보면 각 인덱스로 시작하여 해당 길이만큼 for문을 도는 것이 아니라 해당 인덱스에서 길이 1부터 최대 길이까지 더하고 각 반복마다 Set에 추가하면 2중 for문으로 해결이 가능하다!

    import java.util.*;
    
    class Solution {
        public int solution(int[] elements) {
            int l = elements.length;
            int[] arr = new int[l * 2];
            for(int i = 0; i < arr.length; i++){
                arr[i] = elements[i % l];
            }
            Set<Integer> s = new HashSet<>();
            for(int i = 0; i < l; i++){
                for(int j = 1; j <= l; j++){
                    int sum = 0;
                    for(int k = i; k < i + j; k++){
                        sum += arr[k];
                    }
                    s.add(sum);
                }
            }
            return s.size();
        }
    }
    
    // 개선
    import java.util.*;
    
    class Solution {
        public int solution(int[] elements) {
            int l = elements.length;
            int[] arr = new int[l * 2];
            for(int i = 0; i < arr.length; i++){
                arr[i] = elements[i % l];
            }
            Set<Integer> s = new HashSet<>();
            for(int i = 0; i < l; i++){
                int sum = 0;
                for(int j = i; j < i + l; j++){
                    sum += arr[j];
                    s.add(sum);
                }
            }
            return s.size();
        }
    }

시간복잡도

영어 끝말잇기

접근 과정

1. 끝말잇기 진행 중 이전 단어를 생각해야 한다.
2. 또한 앞에 나왔던 단어를 체크해야 한다.
3. 앞에 나온 단어는 Set으로 확인하고 이전 단어는 prev로 저장하여 비교를 한다.
4. 걸린 사람이 나온다면 해당 사람 번호는 i % n + 1이고 걸린 턴은 i / n + 1이므로 answer에 넣고 break로 빠져 나온다.
5. 걸린 사람이 없다면 자동으로 [0, 0]이 반환된다.

시행착오

• 시행착오 없이 접근 과정대로 구현하여 해결
  

해결 코드

    import java.util.*;
    
    class Solution {
        public int[] solution(int n, String[] words) {
            int[] answer = new int[2];
            Set<String> s = new HashSet<>();
            String prev = "";
            for(int i = 0; i < words.length; i++){
                String w = words[i];
                if(prev.length() > 0 && prev.charAt(prev.length() - 1) != w.charAt(0)){
                    answer[0] = i % n + 1;
                    answer[1] = i / n + 1;
                    break;
                }
                if(s.contains(w)){
                    answer[0] = i % n + 1;
                    answer[1] = i / n + 1;
                    break;
                }
                else{
                    s.add(w);
                    prev = w;
                }
            }
            return answer;
        }
    }

시간복잡도