[코딩테스트 : 프로그래머스] 노란불 신호등 C#

 

문제 내용

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

 

문제 분석

여러 신호등이 노란색이 되어 정전이 일어나는 시간을 찾기

 

1. LCM을 활용해서 신호등 전체의 한 사이클 범위를 분석.

2. 나머지 계산(%)을 통해서 노란색이 사이클 내에 몇 번인지 파악하고, 이를 활용해서 노란색이 겹치는 타이밍을 계산

 

필요한 알고리즘 - LCM, GCD

    // 유클리드 호제법 최대 공약수
    private int GCD(int a, int b)
    {
        while(b != 0)
        {
            int temp = a % b;
            a = b;
            b = temp;
        }
        return a;
    }

    private int LCM(int a, int b)
    {
        return a / GCD(a, b) * b;
    }

 

	public class Solution
	{
    	public int solution(int[,] signals)
        {
        	int row = signals.GetLength(0);
            int lcm = 1;
            
            for(int i = 0; i < row; i++)
            {
            	int cycle = signals[i, 0] + signals[i, 1] + signals[i, 2];
                lcm = LCM(cycle, lcm); // 신호등 전체의 한 사이클을 최소 공배수로 계산
            }
            
            for(int t = 1; t <= lcm; t++)
            {
            	bool isAllYellow = true;
            	for(int i = 0; i < row; i++)
                {
                	int green = signals[i, 0];
                    int yellow = signals[i, 1];
                    int red = signals[i, 2];
                    
                    int yellowStart = green + 1;
                    int yellowEnd = green + yellow;
                    
                    int cycle = green + yellow + red;
                    int pos = t % cycle; // 각 신호등의 사이클 내에서 몇 번째인지 추출
                    if(pos == 0) // 한 사이클을 다 돌음
                    	pos = cycle;
                    
                    if(pos < yellowStart || pos > yellowEnd) // 노란색 범위 밖일 경우
                    {
                    	isAllYellow = false;
                        break;
                    }
                }
                
                if(isAllYellow) return t; // 정전 시간 반환
            }
            return -1; // 해당하지 않는 경우
        }
    }