문제 링크
https://school.programmers.co.kr/learn/courses/30/lessons/250135
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
문제 이해 자체는 되게 간단했는데, 풀려면 수학적인 계산이 좀 필요했다.
솔직히 설명 없이 코드만 적혀있으면, 왜 이렇게 풀었는지 전혀 모를 거 같다.
썸네일
문제 핵심 및 풀이
각도의 관점으로 접근
이 문제에서 바라는 것은, 초침이 각각 시침과 분침과 겹치는지를 판단하는 것이다.
이를 알아내기 위해서는 어떻게 해야 할까? 특정 시간만으로 판단할 순 없다.
왜냐하면 초침이 움직일 때마다, 시침과 분침이 조금씩 움직이기 때문이다.
이를 알아내기 위해서는 아날로그시계가 원 모양이고,
시침, 분침, 초침이 모두 360도 회전한다는 것을 이용해야 한다.
1초당 시침, 분침, 초침은 몇 도씩 움직일까? 이는 쉽게 계산할 수 있다.
초침의 경우, 60초(1분)가 되면 360도를 돌아야 한다.
따라서 1초에 360/60 = 6도씩 움직이게 된다.
이를 다른 모든 시침, 분침, 초침에 적용해 보자
모든 계산을 해보면 위와 같이 나온다.
초당 움직이는 모든 침을 계산하면, 아래와 같다.
초침 = 6도
분침 = 0.1도
시침 = 1/120도
주어진 시간을 통해 침의 각도 계산
위에서 각 초, 분당 몇 도씩 움직이는지를 알아냈으니,
주어진 시간만으로 모든 침들의 각도를 계산할 수 있다.
만약 주어진 시간이 02:43:45라고 하자.
초침 = 45 x 6
분침 = (43 x 6) + (45 x 0.1)
시침 = (2 x 30) + (43 x 0.5) + (45 x 1/120))
위와 같이 계산할 수 있다.
이를 일반화해 보자.
주어진 시간이 h:m:s라고 가정한다면
초침 = 6s
분침 = 6m + 0.1s
시침 = (h%12) x 30 + 0.5m + (1/120) s
이렇게 계산할 수 있다.
여기서 h % 12를 해주는 이유는, 시간이 0 ~ 23시까지 존재하기 때문이다.
또한 시침은 12시간마다 360도를 돌아 원위치로 돌아온다.
15시나 03시나 둘 다 각도는 같기 때문에 h % 12를 해주는 것이다.
1초 미만의 겹침을 알아내는 방법
그럼 이제 1초 단위로 각도가 일치하는지만 판단하면 될까?
사실 그렇지 않다. 아래와 같은 케이스가 있기 때문이다.
우리가 여태껏 구한 것의 최소 단위는 1초당 움직이는 각도이다.
이 방식으로는 1시 5분 5초 ~ 1분 5분 6초 사이에 일어나는 겹침을 판단할 수 없다.
이를 알아내기 위해서는 1초 전의 모든 침의 각도와
1초 후인, 현재의 각도를 비교해줘야 한다.
말로는 어려우니까 그림으로 한번 살펴보자.
검은색 선은 초침이고, 빨간색 선은 분침이라고 가정하자.
왼쪽 상태에서 N초 이후, 오른쪽 상태가 됐을 때
분침과 초침이 겹친 적이 있다고 할 수 있을까?
논리적으로 그럴 수밖에 없다.
분침보다 뒤에 있던 초침이 N초 후, 분침보다 앞으로 이동했다.
이렇게 되기 위해서는 N초 사이에서 초침과 분침이 겹침이 발생했을 수밖에 없다.
이를 각도의 관점에서 이야기해 보자.
초침 각도가 분침 각도보다 작았다.
그리고 N초 후, 초침 각도가 분침 각도보다 커졌다.
그렇다면 초침과 분침은 N초 사이에서 겹친 적이 있다.
이 N초를 1초라고 생각한다면,
1초보다 작은 시간 간격 사이에 겹침이 발생했는지를 판단할 수 있다.
이를 일반화해 보면 이렇게 된다.
현재의 분/초침 각도를 각각 mDegree, sDegree라고 하고,
1초 후의 분/초침 각도를 각각 n_mDegree, n_sDegree라고 하자.
(mDegree > sDegree) && (n_mDegree <= n_sDegree)
위 조건을 만족한다면, i초와 i+1초 사이에서 분침과 초침이 겹쳤다는 것을 의미한다.
이는 분침뿐만이 아니라, 시침에도 똑같이 적용하면 된다.
이런 식으로 겹침을 판단해 나가면 된다.
실수하기 쉬운 부분
시침, 분침, 초침이 겹칠 때
까먹기 쉬운 조건이 있는데, 예제에서 넌지시 알려줬다.
0시 정각과 12시 정각에 모든 침들이 겹칠 때는 딱 한번 겹친 것으로 판정된다.
이 점을 빼먹지 않고 잘 체크해줘야 한다.
초침이 0시/12시 정각으로 되돌아올 때
위 초침을 구하는 계산 공식대로라면 0분 59초에서 1분으로 갈 때,
354 -> 360도가 되는 것이 아니라, 354 -> 0도가 된다.
이렇게 되면 각도의 크기를 통해 겹침을 판단하는 로직을 사용할 수 없다.
그래서 이 경우는 예외로 따로 처리해 주는 것이 좋다.
코드 구현
C++ 구현 코드
↓
#include <iostream>
#include <vector>
#include <cmath>
using namespace std;
// 각 시간과 시간과 관련된 로직을 가지는 Time 클래스 정의
class Time {
public:
int h, m, s;
// 초로 변환된 시간을 가지고도 Time을 만들 수 있도록 생성자 정의
Time(int seconds) {
this->h = seconds / 3600;
this->m = (seconds % 3600) / 60;
this->s = (seconds % 3600) % 60;
}
// 모든 시간을 초로 변환
int toSeconds() {
return h * 3600 + m * 60 + s;
}
// 각도를 계산해서 List 형태로 반환
vector<double> getDegree() {
double hDegree = (h % 12) * 30.0 + m*0.5 + s * (1/120.0);
double mDegree = m * 6.0 + s * (0.1);
double sDegree = s * 6.0;
return vector<double>{hDegree, mDegree, sDegree};
}
};
// 시침가 초침의 겹침을 판단
bool hourMatch(vector<double> cnt, vector<double> next){
if(cnt[0] > cnt[2] && next[0] <= next[2]){
return true;
}
// 초침이 354도에서 0도로 넘어갈 때 예외 케이스
if(cnt[2] == 354 && cnt[0] > 354){
return true;
}
return false;
}
// 분침과 초침의 겹침을 판단
bool minuteMatch(vector<double> cnt, vector<double> next){
if(cnt[1] > cnt[2] && next[1] <= next[2]){
return true;
}
// 초침이 354도에서 0도로 넘어갈 때 예외 케이스
if(cnt[2] == 354 && cnt[1] > 354){
return true;
}
return false;
}
int solution(int h1, int m1, int s1, int h2, int m2, int s2) {
int answer = 0;
// 시작 시간과, 종료 시간을 초 단위로 변경
int start = Time(h1*3600 + m1*60 + s1).toSeconds();
int end = Time(h2*3600 + m2*60 + s2).toSeconds();
// 시작 시간부터 1초씩 올려가며 계산(마지막 초는 포함되면 안됨)
// 마지막 초 + 1까지 판단해버림
for(int i = start; i < end; i++){
vector<double> cnt = Time(i).getDegree();
vector<double> next = Time(i+1).getDegree();
bool hMatch = hourMatch(cnt,next);
bool mMatch = minuteMatch(cnt,next);
// 초침이 분침과 시침과 겹침이 발생했을 때,
if(hMatch && mMatch){
// 시침과 분침의 각도가 같다면 +1만 해줘야함
if(next[0] == next[1]) answer++;
// 아니라면 +2
else answer +=2;
}
// 둘 중 하나라도 겹치면 +1
else if(hMatch || mMatch) answer++;
}
// 위 로직은 시작시간에 대한 검사를 안해줬음
// 그래서 0시 또는 12시에 시작한다면, 한번 겹치고 시작하는 것이기 때문에 +1
if(start == 0 || start == 43200) answer++;
return answer;
}
Java 구현 코드
↓
import java.util.*;
class Solution {
// 각 시간과 시간과 관련된 로직을 가지는 Time 클래스 정의
static class Time{
int h,m,s;
Time(int h, int m, int s){
this.h = h;
this.m = m;
this.s = s;
}
// 초로 변환된 시간을 가지고도 Time을 만들 수 있도록 생성자 정의
Time(int seconds){
this.h = seconds / 3600;
this.m = (seconds % 3600) / 60;
this.s = (seconds % 3600) % 60;
}
// 모든 시간을 초로 변환
int toSeconds(){
return h * 3600 + m * 60 + s;
}
// 각도를 계산해서 List 형태로 반환
List<Double> getDegree(){
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);
}
}
public int solution(int h1, int m1, int s1, int h2, int m2, int s2) {
int answer = 0;
// 시작 시간과, 종료 시간을 초 단위로 변경
int start = new Time(h1,m1,s1).toSeconds();
int end = new Time(h2,m2,s2).toSeconds();
// 시작 시간부터 1초씩 올려가며 계산(마지막 초는 포함되면 안됨)
// 마지막 초기 포함되면 마지막 초 + 1까지 판단해버림
for(int i = start; i <end; i++){
// 현재 시간이 i초일 때의
List<Double> cnt = new Time(i).getDegree();
List<Double> next = new Time(i+1).getDegree();
boolean hMatch = hourMatch(cnt,next);
boolean mMatch = minuteMatch(cnt,next);
// 초침이 분침과 시침과 겹침이 발생했을 때,
if(hMatch && mMatch){
// 시침과 분침의 각도가 같다면 +1만 해줘야함
if(Double.compare(next.get(0),next.get(1)) == 0) answer++;
// 아니라면 +2
else answer +=2;
}
// 둘 중 하나라도 겹치면 +1
else if(hMatch || mMatch) answer++;
}
// 위 로직은 시작시간에 대한 검사를 안해줬음
// 그래서 0시 또는 12시에 시작한다면, 한번 겹치고 시작하는 것이기 때문에 +1
if(start == 0 || start == 43200) answer++;
return answer;
}
// 시침가 초침의 겹침을 판단
boolean hourMatch(List<Double> cnt, List<Double> next){
if(Double.compare(cnt.get(0),cnt.get(2)) > 0
&& Double.compare(next.get(0),next.get(2)) <= 0){
return true;
}
// 초침이 354도에서 0도로 넘어갈 때 예외 케이스
if(Double.compare(cnt.get(2),354d) == 0
&& Double.compare(cnt.get(0),354d) > 0){
return true;
}
return false;
}
// 분침과 초침의 겹침을 판단
boolean minuteMatch(List<Double> cnt, List<Double> next){
if(Double.compare(cnt.get(1),cnt.get(2)) > 0
&& Double.compare(next.get(1),next.get(2)) <= 0){
return true;
}
// 초침이 354도에서 0도로 넘어갈 때 예외 케이스
if(Double.compare(cnt.get(2),354d) == 0
&& Double.compare(cnt.get(1),354d) > 0){
return true;
}
return false;
}
}
시행착오
이게 Level 2면 너무 어려운데..
푸는데 정말 오래 걸렸다.
원리를 파악하고 나서도 체크해줘야 할 조건이 많아서 힘들었다.
설마 각도 계산해서 풀겠어라고 생각했는데, 진짜 각도 계산으로 푸는 거였네
이거 말고 다른 방식이 있을까 궁금하기도 하다.
howudong님에게 보내주세요
토스아이디로 안전하게 익명 송금하세요.
toss.me