프로그래머스 1차 추석트래픽

https://programmers.co.kr/learn/courses/30/lessons/17676

코딩테스트 연습 - [1차] 추석 트래픽

start 기준일때

end 기준일때

N=2000 이라서 O(N^2)으로 될 것 같아서 완전탐색으로 풀었습니다.

이중 for문을 돌면서 start와 end가 정해지고 

1. start를 기준으로 1초 

2. end를 기준으로 1초 동안의 트래픽을 체크합니다.

 

if문을 나눈 기준은 

start 일때:

1. target_start 가 start<= target_start < start+1000일때

2. target_end 가  start<= target_end < start+1000일때

3. target_start< start and target_end > start+ 1000

(위 그림순으로 1,2,3입니다)

 

end 일때:

1. target_start 가 end<= target_start < end+1000일때

2. target_end 가  end<= target_end < end+1000일때

3. target_start< end and target_end > end+ 1000

(위 그림순으로 1,2,3입니다)

 

lines = ["2016-09-15 01:00:04.001 2.0s", "2016-09-15 01:00:07.000 2s"]

def solution(lines):
    answer = 0
    traffic = []
    # 시간을 ms 단위로 고쳐서 list에 start와 end를 넣는다.
    for line in lines :
        data = line.split(" ")
        hour , minute , second , ms = int(data[1][0:2]) , int(data[1][3:5]) , int(data[1][6:8]), int(data[1][9:])
        total = hour*3600*1000 + minute * 60 *1000 + second * 1000 + ms
        minus = ''
        for w in data[2] :
            if w == 's':
                break
            else:
                minus += w
        minus = float(minus)*1000
        # print(minus)
        # print(total)
        # print(total-(minus-1))
        start = total-(minus-1)
        end = float(total)
        traffic.append((start,end))
    
    for i in range(len(traffic)) :
        count_start = 0
        count_end = 0
        start = traffic[i][0]
        end = traffic[i][1]
        for j in range(len(traffic)):
            target_start = traffic[j][0]
            target_end = traffic[j][1]
            
            if start <= target_start < start+1000 :
                count_start +=1
            elif start <= target_end < start+1000 :
                count_start +=1
            elif target_start < start and target_end > start+1000 :
                count_start +=1
            
            if end <= target_start < end+1000 :
                count_end +=1
            elif end <= target_end < end+1000 :
                count_end +=1
            elif target_start < end and target_end > end+1000 :
                count_end +=1
            
            answer = max(answer,max(count_start,count_end))
    # print(traffic)
    # print(answer)
    return answer

solution(lines)

 

https://hyeo-noo.tistory.com/359

[프로그래머스 level3] 추석 트래픽 (Python)