프로그래머스 2016년 (99클럽 코딩테스트 16일차 TIL)

목표

오늘 문제는 비교적 쉽게 접해볼 수 있는 문제였다. 순환알고리즘, 누적합 알고리즘, 나머지 연산 알고리즘을 이용해서 문제를 푸는형식이였다. 아직 문제에 익숙하지 않지만 하루에 한개씩 꾸준히 풀다보면 이런 문제도 근방풀지 않을까 생각된다. 그래서 하루에 하나씩 꾸준히 코딩테스트를 풀려고 노력중이다.

문제

내가 생각했을때 문제에서 원하는부분

두 수 a ,b를 입력받아 2016년 a월 b일이 무슨 요일인지 리턴하는 함수
일의 이름은 일요일부터 토요일까지 각각 SUN,MON,TUE,WED,THU,FRI,SAT 이다.
예를 들어 a=5, b=24라면 5월 24일은 화요일이므로 문자열 "TUE"를 반환하세요.

내가 이 문제를 보고 생각해본 부분

데이터의 특징 파악
2016년은 윤년이라 2월이 29일까지 있음
1월 1일이 금요일로 고정되어 있음
문제 해결을 위한 핵심 로직
각 월의 일 수를 저장하는 배열 또는 상수 활용
a월 b일까지의 누적 일수 계산 로직
누적 일수와 7의 나머지 연산으로 요일 계산
문제 제약 조건 숙지
유효하지 않은 날짜(13월 26일 등)는 입력으로 들어오지 않음
반환 값은 요일 문자열이어야 함
문제의 목적 이해
주어진 날짜가 무슨 요일인지 알아내는 것이 문제의 핵심 목적
검증 방법 생각해보기
윤년, 평년을 고려한 다양한 테스트 케이스 작성해보기

코드로 구현

class Solution {
    public String solution(int a, int b) {
        String[] answer = {"FRI","SAT","SUN","MON","TUE","WED","THU"};
        
        int totalDays = 0;
        
        for(int i = 1; i < a; i++) {
            int daysInMonth = 0;
            switch(i) {
                case 1: case 3: case 5: case 7: case 8: case 10: case 12:
                    daysInMonth = 31;
                    break;
                case 4: case 6: case 9: case 11:
                    daysInMonth = 30;
                    break;
                case 2:
                    daysInMonth = 29;
                    break;
            }
            totalDays += daysInMonth;
        }
        totalDays += b - 1;
        int dayIndex = totalDays % 7;
        return answer[dayIndex];
    }
}

2016년 1월 1일 금요일을 기준으로 요일 순서를 상수로 정의
a월 b일까지 총 경과 일수를 구함
총 경과 일수를 7로 나눈 나머지가 요일 인덱스

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

장점

입력 데이터의 크기와 상관없이 일정한 시간이 소요되므로 알고리즘 성능이 매우 뛰어나다.
시간 복잡도 관점에서 가장 효율적인 알고리즘이다.

단점

입력값에 대한 사전 계산 (Look-up Table 등)이 필요할 수 있다.
문제 상황에 따라 O(1) 알고리즘을 설계하기 어려울 수 있다.
입력 데이터 범위가 제한되어 있어야 가능하다.

이 문제의 경우에는
요일은 7가지 경우의 수로 굉장히 제한적이다.
2016년 날짜 정보는 미리 계산 가능하다.
그래서 O(1) 알고리즘을 설계할 수 있다. 하지만 더 많은 입력 데이터가 주어지거나 범위가 제한되지 않는다면 O(1) 보다는 O(n) 정도의 알고리즘을 설계하는 것이 바람직하다.

마무리

평소에 이런 문제를 접할 수 있어서 풀어보긴했지만 조금 까다로운 문제였던것같다. 특히 각 날짜부터 31일 30일 29일 구분해서 나눠줘야하기 때문에 조금 복잡해보였다. 그래도 다행히 문제는 푸는데 지장은 없었다.