프로그래머스 | Level 2 | 아날로그 시계

Programmers | Level 2 | 아날로그 시계

Problems

• 📘 Src: Programmers
• 🗂️ Cat: Math

󰧭 Description

시침, 분침, 초침이 있는 아날로그시계가 있습니다. 시계의 시침은 12시간마다, 분침은 60분마다, 초침은 60초마다 시계를 한 바퀴 돕니다. 따라서 시침, 분침, 초침이 움직이는 속도는 일정하며 각각 다릅니다. 이 시계에는 초침이 시침/분침과 겹칠 때마다 알람이 울리는 기능이 있습니다. 당신은 특정 시간 동안 알람이 울린 횟수를 알고 싶습니다.

다음은 0시 5분 30초부터 0시 7분 0초까지 알람이 울린 횟수를 세는 예시입니다.

• 가장 짧은 바늘이 시침, 중간 길이인 바늘이 분침, 가장 긴 바늘이 초침입니다.
• 알람이 울리는 횟수를 세기 시작한 시각은 0시 5분 30초입니다.
• 이후 0시 6분 0초까지 초침과 시침/분침이 겹치는 일은 없습니다.

• 약 0시 6분 0.501초에 초침과 시침이 겹칩니다. 이때 알람이 한 번 울립니다.
• 이후 0시 6분 6초까지 초침과 시침/분침이 겹치는 일은 없습니다.

• 약 0시 6분 6.102초에 초침과 분침이 겹칩니다. 이때 알람이 한 번 울립니다.
• 이후 0시 7분 0초까지 초침과 시침/분침이 겹치는 일은 없습니다.

0시 5분 30초부터 0시 7분 0초까지는 알람이 두 번 울립니다. 이후 약 0시 7분 0.584초에 초침과 시침이 겹쳐서 울리는 세 번째 알람은 횟수에 포함되지 않습니다.

다음은 12시 0분 0초부터 12시 0분 30초까지 알람이 울린 횟수를 세는 예시입니다.

• 알람이 울리는 횟수를 세기 시작한 시각은 12시 0분 0초입니다.
• 초침과 시침, 분침이 겹칩니다. 이때 알람이 한 번 울립니다. 이와 같이 0시 정각, 12시 정각에 초침과 시침, 분침이 모두 겹칠 때는 알람이 한 번만 울립니다.

• 이후 12시 0분 30초까지 초침과 시침/분침이 겹치는 일은 없습니다.

12시 0분 0초부터 12시 0분 30초까지는 알람이 한 번 울립니다.

알람이 울리는 횟수를 센 시간을 나타내는 정수 h1, m1, s1, h2, m2, s2가 매개변수로 주어집니다. 이때, 알람이 울리는 횟수를 return 하도록 solution 함수를 완성해주세요.

 Constraints

• 0 ≤ h1, h2 ≤ 23
• 0 ≤ m1, m2 ≤ 59
• 0 ≤ s1, s2 ≤ 59
• h1시 m1분 s1초부터 h2시 m2분 s2초까지 알람이 울리는 횟수를 센다는 의미입니다.
  • h1시 m1분 s1초 < h2시 m2분 s2초
  • 시간이 23시 59분 59초를 초과해서 0시 0분 0초로 돌아가는 경우는 주어지지 않습니다.

󰦕 Examples

h1	m1	s1	h2	m2	s2	result
0	5	30	0	7	0	2
12	0	0	12	0	30	1
0	6	1	0	6	6	0
11	59	30	12	0	0	1
11	58	59	11	59	0	1
1	5	5	1	5	6	2
0	0	0	23	59	59	2852

Solutions

󰘦 Code

import java.util.*;

class Solution {
    // 각 바늘의 초당 이동 각도 (도/초 단위)
    private static final double secSpeed = 360.0 / 60;  // 초침의 속도: 6도/초
    private static final double minSpeed = 360.0 / (60 * 60);  // 분침의 속도: 0.1도/초
    private static final double hrsSpeed = 360.0 / (12 * 60 * 60); // 시침의 속도: 약 0.0083333도/초
    
    public int solution(int h1, int m1, int s1, int h2, int m2, int s2) {
        // 시작 시간과 종료 시간을 초 단위로 변환하여 설정
        int start = h1 * 60 * 60 + m1 * 60 + s1;
        int end = h2 * 60 * 60 + m2 * 60 + s2;
        
        int alarmCount = 0; // 알람 횟수 초기화
        
        // 시작 시간이 정각이면 알람을 한 번 울림
        if (start % 360 == 0) alarmCount++;
        
        // 시작 시각부터 종료 시각까지 각 초마다 겹침 검사
        while (start < end) {
            // 현재 시점의 각도 (초침, 분침, 시침)
            double[] curr = angle(start, 0);
            // 다음 시점의 각도 (초침, 분침, 시침)
            double[] next = angle(start, 1);
            
            // 초침이 분침을 넘는 순간 감지
            if (curr[0] < curr[1] && next[0] >= next[1]) alarmCount++;
            // 초침이 시침을 넘는 순간 감지
            if (curr[0] < curr[2] && next[0] >= next[2]) alarmCount++;
            // 분침과 시침이 동시에 겹치는 경우 중복 알람 제거
            if (next[1] == next[2]) alarmCount--;
            
            start++; // 다음 초로 이동
        }
        
        // 계산된 알람 횟수를 반환
        return alarmCount;
    }
    
    // 각도를 계산하는 함수
    private double[] angle(
            int time, // 현재 시각(초 단위)
            int adjustment  //  현재 또는 다음 초 구분 인자: `0`= 현재 || `1`= 다음
    ) {
        double[] angles = new double[3];  // 각도 배열 (초침, 분침, 시침 순서)
        
        // 초침, 분침, 시침의 각도 계산 (0 ~ 360도 범위로 유지)
        angles[0] = (time + adjustment) * secSpeed % 360;  // 초침 각도
        angles[1] = (time + adjustment) * minSpeed % 360;  // 분침 각도
        angles[2] = (time + adjustment) * hrsSpeed % 360;  // 시침 각도
        
        // adjustment가 1인 경우: 1초 후 바늘의 위치가 정각 위치로 돌아온 경우 값을 360° 으로 조정
        if (adjustment != 0) {
            angles[0] = angles[0] == 0 ? 360 : angles[0];
            angles[1] = angles[1] == 0 ? 360 : angles[1];
            angles[2] = angles[2] == 0 ? 360 : angles[2];
        }
        
        return angles;  // 초침, 분침, 시침의 각도를 담은 배열 반환
    }
}

 Approaches

이 문제는 시계 바늘이 겹치는 순간을 계산하여 특정 시간 구간 동안 알람이 울리는 횟수를 구하는 문제입니다. 각 바늘의 각도를 일정 속도로 계산해, 초침이 분침과 시침을 지나치는 순간을 파악하는 것이 핵심입니다.

1. 문제 분석

아날로그 시계의 초침, 분침, 시침은 각각 고유한 속도로 회전하므로, 초 단위로 각 바늘의 위치(각도)를 계산할 수 있습니다. 여기서 초침이 분침 또는 시침과 "정확히 겹치는 순간"을 찾으려면 미세한 소수점 단위의 차이를 계산해야 하기 때문에 부동소수점 연산 오차로 인해 정확한 겹침을 감지하기 어렵습니다.

이를 해결하기 위해 초침이 다른 바늘과의 각도 차이를 점검하면서 초침이 다른 바늘을 넘어가는 순간을 겹치는 것으로 간주하는 방식을 사용합니다. 예를 들어, 특정 초에 초침이 분침보다 작다가 다음 초에 초침이 분침과 같거나 커지는 경우, 이 순간을 겹치는 시점으로 판단하여 알람이 울리도록 설정합니다.

이 접근 방식이 엄밀하게 바늘이 겹치는 시점을 찾는 방법이라 할 수는 없지만, 문제의 요구사항을 만족하기 위한 현실적인 해결책이 됩니다. 따라서 이 문제를 해결하기 위해서는 주어진 시간 구간을 초 단위로 변환하고, 각 초마다 초침, 분침, 시침의 각도를 계산하여 초침이 분침 또는 시침과 겹치거나 넘어가는 순간을 감지해 알람을 울리는 횟수를 누적하면 됩니다.

2. 접근 방식

이 문제는 초 단위로 각 바늘의 각도를 계산하여, 초침이 다른 바늘과 "겹치는 순간"을 감지하는 방식으로 해결할 수 있습니다. 계산 단위를 통일하고 초 단위로 탐색하면서 초침이 다른 바늘을 넘어가는 순간을 알람으로 간주합니다. 이를 단계별로 정리하면 다음과 같습니다:

1. 시간 변환: 시작 시간 h1, m1, s1과 종료 시간 h2, m2, s2를 초 단위로 변환하여, 시작과 종료 시점을 연속적인 숫자로 표현합니다. 이렇게 변환된 시간을 통해 매 초마다 초침, 분침, 시침의 위치를 계산할 수 있습니다.
2. 각 바늘의 이동 속도 설정: 각 바늘이 초마다 이동하는 각도를 설정합니다.
3. 초 단위 탐색: 변환된 시작 시간부터 종료 시간까지 초 단위로 탐색하면서 매 초마다 각 바늘의 각도를 계산합니다. 이를 통해 매 순간 초침과 분침, 시침의 상대적 위치를 파악할 수 있습니다.
4. 알람 조건 체크: 매 초마다 초침이 다른 바늘과 겹치는 순간을 다음 조건을 통해 감지합니다. 현재 초에서 초침의 각도가 분침 또는 시침의 각도보다 작고, 다음 초에 같거나 커지는 순간이 발생하면 이를 겹치는 순간으로 판단하여 알람 횟수를 증가시킵니다. 이 조건을 통해 실제로 겹치는 순간이 아니라 초침이 다른 바늘을 넘어가는 순간을 포착할 수 있습니다.

이 방법은 매 초마다 초침과 다른 바늘의 상대적 위치 변화를 비교하여 정확한 소수점 겹침을 요구하지 않고도 문제의 요구를 충족하는 현실적인 해법을 제공합니다.

3. 각 바늘의 이동 속도 설정

각 바늘이 초 단위로 이동하는 각도를 정의합니다. 초침, 분침, 시침의 이동 속도는 각각 360도를 한 바퀴로 하는 회전 주기를 기준으로 계산할 수 있습니다. 이를 통해 각 초마다 바늘의 위치를 정확히 계산할 수 있습니다.

• 초침의 속도:
  • 초침은 60초에 한 바퀴를 돌기 때문에, 초당 6° 도씩 이동합니다.
  • 360° ÷ 60(초) = 6°
• 분침의 속도
  • 분침은 1시간에 한 바퀴를 돌기 때문에, 초당 0.1° 도씩 이동합니다.
  • 360° ÷ 3600(초) = 0.1°
• 시침의 속도:
  • 시침은 12시간에 한 바퀴를 돌기 때문에, 초당 약 0.0083333° 도씩 이동합니다.
  • 360° ÷ 43200(초) = 0.0083333...°

아래와 같이 각 속도를 상수로 설정하여 이후 각도 계산에 활용합니다.

// 초당 이동 각도 설정
private static final double secSpeed = 360.0 / 60;  // 초침: 6도/초
private static final double minSpeed = 360.0 / (60 * 60);  // 분침: 0.1도/초
private static final double hrsSpeed = 360.0 / (12 * 60 * 60); // 시침: 약 0.0083333도/초

4. 시간 범위 및 알람 횟수 초기화

주어진 시작 시각과 종료 시각을 초 단위로 변환하여 전체 시간 범위를 간편하게 설정합니다. 이를 통해 시작 시점부터 종료 시점까지 초 단위로 탐색하면서 겹침 조건을 검사하고, 필요한 경우 알람을 울리게 할 수 있습니다.

// 알람 횟수 초기화 및 시간 범위 설정
int alarmCount = 0;  // 알람 횟수 초기화
int start = h1 * 60 * 60 + m1 * 60 + s1;  // 시작 시각을 초 단위로 변환
int end = h2 * 60 * 60 + m2 * 60 + s2;    // 종료 시각을 초 단위로 변환

5. 시작 시간이 정각인 경우 처리

시작 시간이 정확히 정각(모든 바늘이 원점 위치에 있을 때)인 경우, 초침, 분침, 시침이 모두 12시 방향에 위치하여 겹칩니다. 이때는 초기 상태에서 이미 알람이 울려야 하므로, 이를 반영하여 시작 시간에 겹침이 발생하는 경우를 따로 처리해야 합니다.

이를 위해, 시작 시간이 360도로 나누어떨어지는지 확인합니다. 이 조건이 참이면 세 바늘이 겹친 상태로 알람이 울리므로, 알람 횟수를 증가시킵니다.

이 처리를 통해, 정각에 알람이 울리는 경우를 예외 없이 반영할 수 있습니다.

// 시작 시간이 정각일 경우 초침, 분침, 시침이 모두 원점에 위치해 겹침
if (start % 360 == 0) alarmCount++;

6. 초마다 각도 계산 및 겹침 검사

주어진 시간 구간 동안 매 초마다 초침, 분침, 시침의 각도를 계산하여 초침이 다른 바늘과 겹치는 순간을 탐지합니다. 이 과정은 초침이 분침 또는 시침의 위치를 넘어가는 순간을 두 바늘이 겹치는 지점으로 판단하고 이를 감지하기 위해 현재 초와 다음 초의 각도를 비교하여 알람을 울리도록 설정합니다.

먼저 각도를 계산하는 단계에서는 매 초마다 초침, 분침, 시침의 각도를 구하여 배열에 저장합니다. 현재 초와 다음 초의 각도를 각각 배열로 담아 두 시점의 각도 변화를 비교할 준비를 합니다. 한 바퀴를 돌아 360도가 되면 다시 각도가 0으로 초기화되는 상황을 방지하기 위해, 다음 초의 각도가 정확히 0이 되는 경우 360으로 조정합니다.

// 각도를 계산하는 함수
private double[] angle(
        int time, // 현재 시각(초 단위)
        int adjustment  //  현재 또는 다음 초 구분 인자: `0`= 현재 || `1`= 다음
) {
    double[] angles = new double[3];  // 각도 배열 (초침, 분침, 시침 순서)
    
    // 초침, 분침, 시침의 각도 계산 (0 ~ 360도 범위로 유지)
    angles[0] = (time + adjustment) * secSpeed % 360;  // 초침 각도
    angles[1] = (time + adjustment) * minSpeed % 360;  // 분침 각도
    angles[2] = (time + adjustment) * hrsSpeed % 360;  // 시침 각도
    
    // adjustment가 1인 경우: 1초 후 바늘의 위치가 정각 위치로 돌아온 경우 값을 360° 으로 조정
    if (adjustment != 0) {
        angles[0] = angles[0] == 0 ? 360 : angles[0];
        angles[1] = angles[1] == 0 ? 360 : angles[1];
        angles[2] = angles[2] == 0 ? 360 : angles[2];
    }
    
    return angles;  // 초침, 분침, 시침의 각도를 담은 배열 반환
}

이렇게 계산된 각도를 바탕으로 겹침 조건을 확인합니다. 초침이 분침 또는 시침을 넘어가는 순간을 감지하기 위해 현재 초에서 초침의 각도가 분침이나 시침보다 낮은지 확인하고, 다음 초에 초침의 각도가 같거나 넘어가는지를 비교합니다. 이러한 조건을 통해 실제로 정확히 겹치지 않더라도 초침이 다른 바늘을 넘는 순간을 포착하여 알람 횟수를 증가시킬 수 있습니다.

마지막으로, 분침과 시침이 겹쳐 있는 경우에는 알람이 중복으로 카운트될 수 있습니다. 이를 방지하기 위해, 다음 초에 분침과 시침이 동시에 겹치는 상황에서는 중복 알람이 발생하지 않도록 제외하여 알람 횟수의 정확성을 보장합니다.

// 각 초마다 각도를 계산하고 겹침을 검사
while (start < end) {
    double[] curr = angle(start, 0);  // 현재 시점의 각도
    double[] next = angle(start, 1);  // 다음 시점의 각도
    
    // 초침이 분침을 넘는 순간 감지
    if (curr[0] < curr[1] && next[0] >= next[1]) alarmCount++;
    // 초침이 시침을 넘는 순간 감지
    if (curr[0] < curr[2] && next[0] >= next[2]) alarmCount++;
    // 분침과 시침이 동시에 겹치는 경우 중복 알람 제거
    if (next[1] == next[2]) alarmCount--;
    
    start++;
}

7. 겹침 횟수 반환

모든 초에 대해 초침이 분침 또는 시침과 겹치는 순간을 검사하고 알람 횟수를 누적한 후, 최종적으로 계산된 알람 횟수를 반환합니다.

이 값은 주어진 시간 구간 동안 초침이 다른 바늘과 겹쳐 알람이 울린 총 횟수를 나타냅니다.

// 계산된 알람 횟수를 반환
return alarmCount;

󰄉 Complexity

• ⏳ TC: O(n)
• 💾 SC: O(1)

주어진 구간의 초 단위 길이를 n라 할 때 각 초마다 각도를 계산하므로 시간 복잡도는 O(n)입니다. 추가 메모리는 초마다 계산된 각도만 저장하므로 상수 공간을 사용합니다.