프로그래머스_아날로그시계_Day4

알고리즘 챌린지 4일 차이다. 오늘부터 설 명절 연휴가 시작되었다. 오전에 가족들과 당일치기로 강릉을 다녀와서 그런지 너무 피곤해가지고 오늘은 스킵할까 고민해 봤지만, 꾹 참고 그래도 한 문제만 풀기 위해 컴퓨터를 켰다. 

오랜만에 알고리즘을 푸는 것이라 천천히 감을 되찾으려고 프로그래머스 level2만 먼저 풀어보고 있는데,,, 오늘 고른 문제는 진짜 안그래도 피곤해서 그런지 포기할까 싶었다. ㅋㅋㅋ Level2치고 너무 어려운 거 아닌가...? 싶을 정도였다. 

정답률이 11%이길래 긴가민가 하다가 얼마나 어렵겠어 했는데 따져야 할 조건이 너무 어렵고, 접근 자체도 간단한 듯 간단하지 않았다. 이해가 어려울 것 같기 때문에 하나하나 차근차근 최대한 상세하게 설명해 보도록 하겠다. 오늘은 파이썬 말고,, 자바로만 풀었다. 연휴인데 이 정도는 이해해 줘라 나 자신.. 

https://school.programmers.co.kr/learn/courses/30/lessons/250135?language=java

프로그래머스

문제와 이미지만 봤을 때, 그냥 침끼리 겹치는 타이밍만 구하면 되는거 아닌가?라고 간단하게 생각했지만, 겹치는 시간이 1초보다 작은 단위인 것을 예시로 보고 나서 심상치 않음을 느꼈다. 

그러다 보니 초를 기준으로 문제를 푸는 것은 안 될 것 같고. 각 침이 한 바퀴, 즉 360도를 일정 주기로 돌기 때문에 각도를 기준으로 한 속력을 구해야 한다고 생각해서 단위를 일원화시켜보았다.

시침은 24시간에 360도, 분침은 60분에 360도, 초침은 60초에 360도를 돈다고 기준을 잡으면 될 것 같다.  

각 침의 속력	1초	1분	1시간
초침	6도	360도	21600도
분침	0.1도	6도	360도
시침	1/120도	0.5도	30도

위의 표를 참고해서 시간을 다루는 Util 클래스를 아래와 같이 하나 만들어 두었다. 각 메서드의 역할은 주석을 참고하자. 

static class TimeUtil{
        int h, m, s;
        TimeUtil(int h, int m, int s) {
            this.h = h;
            this.m = m; 
            this.s = s;
        }
        
        //주어진 시각을 초로 변환하더라도 초기화할 수 있도록 생성자 정의 
        TimeUtil(int seconds) {
            this.h = seconds / 3600; 
            this.m = (seconds % 3600) / 60;
            this.s = (seconds % 3600) % 60;
        }
        
        //모든 시간을 초로 변환 (= 단위의 일원화)
        public int toSeconds() {
            return h*3600 + m * 60 + s;
        }
        
        //각 침의 각도를 계산해서 List로 반환 
        List<Double> getDegree(){
            //시침의 범위가 0~23. 15시나 03시나 각도는 같다. 따라서 %12를 해준다.
            //위의 표를 참고하여 초기화한 값에 따라 각 침의 속력을 반영하여 현재 침의 각도를 구하자.
            Double hDegree = (h%12) *30d + m*0.5d + s * (1/120d); 
            Double mDegree = m * 6d + s * 0.1d;
            Double sDegree = s * 6d; 
            
            return List.of(hDegree, mDegree, sDegree);
        }
    }

 

문제의 예시에 나와있는 것처럼 각 침이 겹치는 시간이 1초보다 작은 단위에서 이루어지기 때문에 겹침을 판단하는 기준이 필요하다. 시침/분침/초침중에서 속력이 가장 빠른 침이 무엇인가? 압도적으로 초침이 빠르다. 

그리하여 초침을 기준으로, 시침과 초침이 겹치는 경우, 분침과 초침이 겹치는 경우 셋 모두 겹치는 경우를 판단해야 한다. 

이때, 침이 겹치는 것을 판단하는 것은 1초 단위로 반복을 돌려보면서 현재 침의 위치와 1초 후의 침의 위치를 판단하는 것이다. 

1초 간격으로 초침이 분침 혹은 시침보다 뒤에 있다가(=각도가 작았다가), 1초 후에 초침이 시침 혹은 분침보다 앞으로 간다면(=각도가 커져서 추월했다면) 1초 사이에 두 침이 겹쳤다고 판단할 수 있다.
그림으로 보면 아래와 같다.

검은선이 초침, 빨간 선이 분침 혹은 시침이라고 했을 때, 1초 이후의 모습이 저렇게 바뀌었다면, 1초 사이에 초침이 역전하면서 한 번 겹친 것이다. 

위의 이미지가 이 문제를 풀기 위한 핵심 로직이라고 볼 수 있다. 
여기에서 추가로 예외 케이스를 살펴보아야 한다. 

세 침이 모두 겹치는 경우
-> 문제에서 1번만 카운트하라고 했기 때문에 이는 조건에 따라 분기를 해야 한다. 

초침이 354도(59초)이면서 분침 혹은 시침이 354도보다 큰 경우
-> 이는 위의 로직에서 제외되는 예외 케이스다. 초침이 59초 인경우 1초 후에 354 -> 360도가 되는 것이 아니라 354 -> 0도가 되어 버린다. 
그래서 1초 후에 초침이 분침 혹은 시침보다 각도가 커진다는 핵심 로직에서 벗어나기 떄문에 이 또한 별도로 카운트해줘야 한다. 

시작시간부터 침이 겹치면서 시작하는 경우
-> 0시와 12시에는 시침/분침/초침이 12에서 모두 겹친 상태로 시작한다. 문제에서 말한 것처럼 1만 카운트하라고 했으니 1을 더해준다. 

여기까지 이해하는 데 고생했다! 이제는 코드로 살펴보자.

import java.util.*;
class Solution {
    static class TimeUtil{
        int h, m, s;
        TimeUtil(int h, int m, int s) {
            this.h = h;
            this.m = m; 
            this.s = s;
        }
        
        //주어진 시각을 초로 변환하더라도 초기화할 수 있도록 생성자 정의 
        TimeUtil(int seconds) {
            this.h = seconds / 3600; 
            this.m = (seconds % 3600) / 60;
            this.s = (seconds % 3600) % 60;
        }
        
        //모든 시간을 초로 변환 
        public int toSeconds() {
            return h*3600 + m * 60 + s;
        }
        
        //각 침의 각도를 계산해서 List로 반환 
        List<Double> getDegree(){
            //시침의 범위가 0~23. 15시나 03시나 각도는 같다. 1시간에 30도, 1분에 30 / 60도, 1초에 30 / 3600도가 돌아간다. 
            Double hDegree = (h%12) *30d + m*0.5d + s * (1/120d);
            //1분에 6도, 1초에 6 / 60도 돌아간다. 
            Double mDegree = m * 6d + s * 0.1d;
            //1초에 6도 돌아간다. 
            Double sDegree = s * 6d; 
            
            return List.of(hDegree, mDegree, sDegree);
        }
    }
    
    public int solution(int h1, int m1, int s1, int h2, int m2, int s2) {
        int answer = 0;
        //시작 시간과 종료 시간을 초단위로 변경
        int start = new TimeUtil(h1, m1, s1).toSeconds();
        int end = new TimeUtil(h2, m2, s2).toSeconds();
        
        //시작 시간부터 1초씩 증가하면서 판단하기. 1초 미만의 시간동안 겹칩을 판단하기 위해 범위는 end -1까지이다. 
        for (int i=start; i<end; i++) {
            //현재 시간이 i초 일때의 각각의 각도를 구하자. 
            List<Double> now = new TimeUtil(i).getDegree(); 
            List<Double> next = new TimeUtil(i+1).getDegree();
            
            boolean hourMatchWithSec = hMatch(now, next);
            boolean minuteMatchWithSec = mMatch(now, next);
            
            //시침과 초침/ 분침이 겹쳤을 때
            if(hourMatchWithSec && minuteMatchWithSec) {
                //시침과 분침의 각도 즉 모든 침의 각도가 같다면 1만 카운트 하기 
                if(Double.compare(next.get(0), next.get(1)) == 0) answer++;
                else answer += 2;
            }else if (hourMatchWithSec || minuteMatchWithSec) {
                answer++;
            }
        }
        //시작 시간부터 겹치는 경우의 수도 있음 0시 & 12시 
            if(start == 0 || start == 43200) answer++;
        return answer;
    }
    //초침과 시침의 겹침 판단
    /*
    	Double.compare()
        0: 두 값이 같음
        양수: 첫 번째 값이 두 번째 값보다 큼
        음수: 첫 번째 값이 두 번째 값보다 작음
    */
    boolean hMatch(List<Double> now, List<Double> next) {
        if(Double.compare(now.get(0), now.get(2)) > 0 && 
          Double.compare(next.get(0), next.get(2)) <= 0){
            return true;
        }
        
        //예외 케이스
        //초침이 354도 일때 (59초)
        if(Double.compare(now.get(2), 354d) == 0 && 
          Double.compare(now.get(0), 354d) > 0) {
            return true; 
        }  
        return false;
    }
    
    //분침과 초침의 겹침을 판단 
    public boolean mMatch(List<Double> now, List<Double> next){
        if(Double.compare(now.get(1), now.get(2)) > 0 && 
          Double.compare(next.get(1), next.get(2)) <= 0) {
            return true; 
        }
        
        
        if(Double.compare(now.get(2), 354d) == 0 && 
          Double.compare(now.get(1), 354d) > 0) {
            return true; 
        }  
        return false; 
    }
}