[99club/TIL] 4주차 - 화요일 TIL(Today I Learned)

안녕하세요. delay100 입니다!

오늘의 TIL 시작합니다.

---

미들러 문제

---

목요일 - 2번. 개인정보 수집 유효기간

https://school.programmers.co.kr/learn/courses/30/lessons/150370

프로그래머스

부끄럽지만 이 문제를 푸는데 하루가 걸렸습니다... 그마저도 다른 블로그를 보고 해결 방안을 보고 풀었지요...ㅠㅠ

직접 year, month, day를 계산하려면 이것저것 생각할 것이 많아 복잡하더군요 ..

예를들어, 만료일이 2020년 12월 28일이어야 할 경우.. 년, 월을 2021년 01월에서 -1을 해줘야 하므로 골치아프게 됩니다.

이런 예시가 매우 많이 있는데..

제가 사용했던 프로그래머스 150370번 반례도 같이 첨부해두겠습니다!

프로그래머스 150370번 반례

 아무튼 문제 해결의 핵심은

1. 0년 0월 0일에서부터 today까지 총 며칠이 지났는지? todayTotal
2. 0년 0월 0일부터 privacies[i]까지 총 며칠이 지났는지? currentTotal
3. today보다 privacies[i]가 작거나 같은 경우에는 만료된 것 todayTotal >= currentTotal 

import java.io.*;
import java.util.*;

class Solution {
    public int[] solution(String today, String[] terms, String[] privacies) {
        int dayForM = 28;
        ArrayList<Integer> al = new ArrayList<>();
        
        // 1. 약관종류 - 유효기간에 대한 HashMap 만들기
        HashMap<Character, Integer> map = new HashMap<Character, Integer>();
        
        for(int i=0; i<terms.length; i++) {
            String[] s = terms[i].split(" ");
            map.put(s[0].charAt(0), Integer.parseInt(s[1]));
        }
        
        // 2. 오늘에 대한 값 String -> int 변환
        String[] todayStringList = today.split("\\."); // 2022와 05와 19로 분리
        int todayYear = Integer.parseInt(todayStringList[0]);
        int todayMonth = Integer.parseInt(todayStringList[1]);
        int todayDay = Integer.parseInt(todayStringList[2]);
        int todayTotal = todayYear * dayForM * 12 + todayMonth * dayForM + todayDay;
            
        // 3. 개인정보 수집 일자에 따라 파기/보관 여부 결정
        for(int i=0; i<privacies.length; i++) {
            String[] s1List = privacies[i].split(" "); // 2021.05.02와 A로 분리
            String[] s2 = s1List[0].split("\\."); // 2021와 05와 02로 분리
            int[] s2Int = new int[s2.length]; // s2를 int형으로 변환한 list
            int term = map.get(s1List[1].charAt(0)); // A -> 6
            
              for(int j=0; j<s2.length; j++) {
                s2Int[j] = Integer.parseInt(s2[j]);
            }
           
            int currentTotal = s2Int[0] * dayForM * 12 + s2Int[1] * dayForM + s2Int[2] + (term * dayForM);   
            
            if(todayTotal >= currentTotal) {
                al.add(i+1);
            }

        }
        
        int[] answer = new int[al.size()];
        
        for(int i=0; i<al.size(); i++) {
            answer[i] = al.get(i);
        }
        
        return answer;
    }
}

[반례 참고한 곳] - 프로그래머스 150370번 질문게시판

https://school.programmers.co.kr/learn/courses/30/lessons/150370/questions

프로그래머스

 

[문제 해결에 참고한 블로그]

https://dev-ddol-e.tistory.com/12

[ 프로그래머스 JAVA ] 개인정보 수집 유효 기간

---

금요일. 연속된 부분 수열의 합

https://school.programmers.co.kr/learn/courses/30/lessons/178870

프로그래머스

 

1. 실패 코드 - 시간초과

class Solution {
    public int[] solution(int[] sequence, int k) {
        int[] answer = new int[2];
        int listSize = sequence.length;
        
        for(int i=0; i<sequence.length; i++) {
            if(sequence[i] > k) break;
            int temp = 0;
            int tempSize = 0;
            for(int j=i; j<sequence.length; j++) {
                temp += sequence[j]; 
                if(temp > k) break;
                else if(temp == k) {
                    tempSize = j-i;
                    if(tempSize < listSize) {
                        listSize = tempSize;
                        answer[0] = i;
                        answer[1] = j;
                    }
                }
            }
        }
        
        return answer;
    }
}

프로그래머스 시간초과

이 코드를 실행해보면 10~16, 24~30번이 시간초과가 나고 있습니다.

 

2. 성공 코드 - 투포인터

투포인터를 이용해 O(n)으로 줄였습니다.

투포인터는 배열 내에 index를 가리키는 값이 2개로, 왼쪽 index와 오른쪽 index가 존재합니다.

여기서는 sum<=k가 될 때까지 오른쪽 index값을 증가시키면서 sum값을 증가시키고,

sum>k이면 왼쪽index값을 증가시켜서 다시 sum값을 감소했습니다.

더보기에 참고한 블로그 링크를 두었으니, 해당 링크에 가시면 상세한 설명을 보실 수 있습니다.

class Solution {
    public int[] solution(int[] sequence, int k) {
        int[] answer = new int[2];
        int sum = sequence[0]; // 부분수열의 합
        int leftPointer = 0; // 왼쪽 포인터 위치
        int rightPointer = 0; // 오른쪽 포인터 위치
        
        int minSize = sequence.length; // 가장 작은 수열의 크기 -> 변동하는 값 
        int n = sequence.length; // sequence의 크기
        
        while(true) {
            // System.out.println("leftPointer= "+leftPointer+"/ rightPointer= "+rightPointer+"/ sum= "+sum+"/ minSize= " + minSize);
            if(leftPointer == n && rightPointer == n) break;
            
            // sum값이 k와 같고 && 가장 작은 수열의 크기보다 작은 경우
            if(sum==k && minSize > (rightPointer-leftPointer)) {
                minSize = rightPointer - leftPointer;
                answer[0] = leftPointer;
                answer[1] = rightPointer;
            }
            
            // 현재까지 합이 k보다 작거나 같으면 
            if(sum <= k && rightPointer < n) {
                rightPointer++; // 오른쪽으로 먼저 이동
                if(rightPointer < n) sum += sequence[rightPointer]; // 오른쪽 값 추가
            } else {
                if(leftPointer < n) sum -= sequence[leftPointer]; // 현재 위치 값 제거
                leftPointer++; // 오른쪽으로 이동
            } 
        }
        
        return answer;
    }
}

while문 아래의 print문을 출력 시 아래와 같은 결과가 나옵니다.

테스트1 투포인터 이용 방법

 

[참고한 블로그]

https://ksb-dev.tistory.com/302

프로그래머스 - 연속된 부분 수열의 합(Java)

 

---

+ 비기너 문제

약수의 합 (https://school.programmers.co.kr/learn/courses/30/lessons/12928)

프로그래머스

 

+ 챌린저 문제

퍼즐 조각 채우기 (https://school.programmers.co.kr/learn/courses/30/lessons/84021)

프로그래머스

---

 

어제 오늘 푼 2문제는 혼자서 풀지 못했습니다...

그래도 문제를 푸는데 있어서 투포인터라는 개념과 날짜는 0년 0월 0일부터 해당 날짜까지 숫자로 치환해서 계산하는 방법을 배워서 뜻깊었습니다..!