IT-garden

문제 설명

하드디스크는 한 번에 하나의 작업만 수행할 수 있습니다. 디스크 컨트롤러를 구현하는 방법은 여러 가지가 있습니다. 가장 일반적인 방법은 요청이 들어온 순서대로 처리하는 것입니다.

예를들어

작업 요청

와 같은 요청이 들어왔습니다. 이를 그림으로 표현하면 아래와 같습니다.

한 번에 하나의 요청만을 수행할 수 있기 때문에 각각의 작업을 요청받은 순서대로 처리하면 다음과 같이 처리 됩니다.

이 때 각 작업의 요청부터 종료까지 걸린 시간의 평균은 10ms(= (3 + 11 + 16) / 3)가 됩니다.

하지만 A → C → B 순서대로 처리하면

이렇게 A → C → B의 순서로 처리하면 각 작업의 요청부터 종료까지 걸린 시간의 평균은 9ms(= (3 + 7 + 17) / 3)가 됩니다.

각 작업에 대해 [작업이 요청되는 시점, 작업의 소요시간]을 담은 2차원 배열 jobs가 매개변수로 주어질 때, 작업의 요청부터 종료까지 걸린 시간의 평균을 가장 줄이는 방법으로 처리하면 평균이 얼마가 되는지 return 하도록 solution 함수를 작성해주세요. (단, 소수점 이하의 수는 버립니다)

제한조건

• jobs의 길이는 1 이상 500 이하입니다.
• jobs의 각 행은 하나의 작업에 대한 [작업이 요청되는 시점, 작업의 소요시간] 입니다.
• 각 작업에 대해 작업이 요청되는 시간은 0 이상 1,000 이하입니다.
• 각 작업에 대해 작업의 소요시간은 1 이상 1,000 이하입니다.
• 하드디스크가 작업을 수행하고 있지 않을 때에는 먼저 요청이 들어온 작업부터 처리합니다.

입출력 예

입출력 예 설명

문제에 주어진 예와 같습니다.

• 0ms 시점에 3ms 걸리는 작업 요청이 들어옵니다.
• 1ms 시점에 9ms 걸리는 작업 요청이 들어옵니다.
• 2ms 시점에 6ms 걸리는 작업 요청이 들어옵니다.

나의 풀이

import heapq

def solution(jobs):
    jobs=sorted(jobs, key = lambda x: (x[0],x[1]))
    heap=[] # 힙
    
    t = jobs[0][1] + jobs[0][0] # 전체 시간
    m = t - jobs[0][0] # 요청에서 종료까지
    i = 1
    
    while True:
        if i == len(jobs):
            break
            
        if jobs[i][0] < t: # 작업 중에 요청이 들어오는 것
            heapq.heappush(heap,[jobs[i][1],jobs[i][0]])
            i += 1
        else: # 작업이 끝나고 요청이 들어오는 것
            try: # 실행할 작업이 있는지 확인
                start,h=heapq.heappop(heap) 
                t += start # 전체 시간에 더하기
                m += t - h # 요청에서 종료까지 구해 더하기
            except: # 작업을 수행하고 있지 않은 경우
                t = jobs[i][0] + jobs[i][1] # 시간 새로 설정
                m += jobs[i][1] # 작업 소요시간 더하기 
                i += 1
                
    while True: # heap에 남아있는 것들을 처리하기 위한 무한 반복
        try:
            start,h=heapq.heappop(heap)
            t += start  # 전체 시간에 더하기
            m += t - h # 요청에서 종료까지 구해 더하기
        except:
            break
            
    return m//len(jobs) # 평균 시간

1. heapq을 이용하여 문제를 풀었습니다.
2. 예시를 통해 해당 시점으로부터 처리할 수 있는 작업들 중 가장 작업 소요시간이 작은 작업부터 해야 평균을 가장 줄일 수 있다는 것을 알 수 있습니다.
3. jobs를 오름차순으로 정렬하고 하나의 작업을 수행해 걸린 전체 시간(t)과 요청에서 종료까지 걸린 시간 m을 구합니다.
4-1. 무한 루프를 통해 작업이 진행 중에 새로운 작업이 들어오면 heapq에 넣습니다.
4-2. 그렇지 않을 경우 heapq에 값이 있다면 최소힙을 제거하고 t와 m을 계산합니다. heapq에 값이 없다면 t를 새로 설정하고 t와 m을 계산합니다.
5. 무한 루프가 끝나고 아직 heapq에 값이 있다면 heapq의 값들을 계산하고 요청부터 종료까지 걸린 시간의 평균을 리턴합니다.

프로그래머스 '디스크 컨트롤러' : https://programmers.co.kr/learn/courses/30/lessons/42627

문제 설명

네트워크란 컴퓨터 상호 간에 정보를 교환할 수 있도록 연결된 형태를 의미합니다. 예를 들어, 컴퓨터 A와 컴퓨터 B가 직접적으로 연결되어있고, 컴퓨터 B와 컴퓨터 C가 직접적으로 연결되어 있을 때 컴퓨터 A와 컴퓨터 C도 간접적으로 연결되어 정보를 교환할 수 있습니다. 따라서 컴퓨터 A, B, C는 모두 같은 네트워크 상에 있다고 할 수 있습니다.

컴퓨터의 개수 n, 연결에 대한 정보가 담긴 2차원 배열 computers가 매개변수로 주어질 때, 네트워크의 개수를 return 하도록 solution 함수를 작성하시오.

제한조건

• 컴퓨터의 개수 n은 1 이상 200 이하인 자연수입니다.
• 각 컴퓨터는 0부터 n-1인 정수로 표현합니다.
• i번 컴퓨터와 j번 컴퓨터가 연결되어 있으면 computers[i][j]를 1로 표현합니다.
• computer[i][i]는 항상 1입니다.

입출력 예

입출력 예 설명

예제 #1
아래와 같이 2개의 네트워크가 있습니다.

나의 풀이

def solution(n, computers):
    def dfs(s):
        ch[s]=1
        for i in a[s]:
            if ch[i] == 0:
                dfs(i)

    a=[[] for i in range(n)]
    for i in range(n):
        for j in range(i,n):
            if computers[i][j] == 1:
                a[i].append(j)
                a[j].append(i)
                
    ch=[0]*n
    c=0
    for i in range(n):
        if ch[i] == 0:
            c += 1
            dfs(i)  
    return c

1. computers의 배열을 토대로 각 컴퓨터가 어디에 연결되어 있는지 저장합니다.
2. dfs를 통해 모든 점을 방문하고 네트워크의 개수를 세서 리턴합니다.

프로그래머스 '네트워크' : https://programmers.co.kr/learn/courses/30/lessons/43162

문제 설명

대구 달성공원에 놀러 온 지수는 최근에 새로 만든 타일 장식물을 보게 되었다. 타일 장식물은 정사각형 타일을 붙여 만든 형태였는데, 한 변이 1인 정사각형 타일부터 시작하여 마치 앵무조개의 나선 모양처럼 점점 큰 타일을 붙인 형태였다. 타일 장식물의 일부를 그리면 다음과 같다.

그림에서 타일에 적힌 수는 각 타일의 한 변의 길이를 나타낸다. 타일 장식물을 구성하는 정사각형 타일 한 변의 길이를 안쪽 타일부터 시작하여 차례로 적으면 다음과 같다.
[1, 1, 2, 3, 5, 8, .]
지수는 문득 이러한 타일들로 구성되는 큰 직사각형의 둘레가 궁금해졌다. 예를 들어, 처음 다섯 개의 타일이 구성하는 직사각형(위에서 빨간색으로 표시한 직사각형)의 둘레는 26이다.

타일의 개수 N이 주어질 때, N개의 타일로 구성된 직사각형의 둘레를 return 하도록 solution 함수를 작성하시오.

제한조건

• N은 1 이상 80 이하인 자연수이다.
  
  

입출력 예

나의 풀이

def solution(N):
    d=[0]*(N+1)
    d[1]=4
    d[2]=6
    for i in range(3,N+1):
        d[i] = d[i-1] + d[i-2]
    return d[N]

[1, 1, 2, 3, 5, 8 ...]일 때 타일의 개수가 주어지면 각 경우의 둘레를 구했습니다.

n = 1 이면 둘레는 1 * 4 = 4
n = 2 이면 둘레는 (1 * 2) + (2 * 2) = 6
n = 3 이면 둘레는 (3 * 2) + (2 * 2) = 10
n = 4 이면 둘레는 (5 * 2) + (3 * 2) = 16

이를 통해 n이 3이상인 경우 점화식 d[i] = d[i-1] + d[i-2]를 만들었습니다.

프로그래머스 '타일 장식물' : https://programmers.co.kr/learn/courses/30/lessons/43104

문제 설명

가로 길이가 2이고 세로의 길이가 1인 직사각형모양의 타일이 있습니다. 이 직사각형 타일을 이용하여 세로의 길이가 2이고 가로의 길이가 n인 바닥을 가득 채우려고 합니다. 타일을 채울 때는 다음과 같이 2가지 방법이 있습니다.

• 타일을 가로로 배치 하는 경우
• 타일을 세로로 배치 하는 경우

예를들어서 n이 7인 직사각형은 다음과 같이 채울 수 있습니다.

직사각형의 가로의 길이 n이 매개변수로 주어질 때, 이 직사각형을 채우는 방법의 수를 return 하는 solution 함수를 완성해주세요.

제한조건

• 가로의 길이 n은 60,000이하의 자연수 입니다.
• 경우의 수가 많아 질 수 있으므로, 경우의 수를 1,000,000,007으로 나눈 나머지를 return해주세요.

입출력 예

입출력 예 설명

입출력 예 #1
다음과 같이 5가지 방법이 있다.

나의 풀이

def solution(n):
    d=[0]*(n+1)
    d[1]=1
    d[2]=2
    for i in range(3,n+1):
        d[i] = (d[i-1] + d[i-2]) % 1000000007
    return d[n]

프로그래머스 '2 x n 타일링' : https://programmers.co.kr/learn/courses/30/lessons/12900

문제 설명

아래와 같이 5와 사칙연산만으로 12를 표현할 수 있습니다.

12 = 5 + 5 + (5 / 5) + (5 / 5)
12 = 55 / 5 + 5 / 5
12 = (55 + 5) / 5

5를 사용한 횟수는 각각 6,5,4 입니다. 그리고 이중 가장 작은 경우는 4입니다.
이처럼 숫자 N과 number가 주어질 때, N과 사칙연산만 사용해서 표현 할 수 있는 방법 중 N 사용횟수의 최솟값을 return 하도록 solution 함수를 작성하세요.

제한조건

• N은 1 이상 9 이하입니다.
• number는 1 이상 32,000 이하입니다.
• 수식에는 괄호와 사칙연산만 가능하며 나누기 연산에서 나머지는 무시합니다.
• 최솟값이 8보다 크면 -1을 return 합니다.

입출력 예

입출력 예 설명

예제 #1
문제에 나온 예와 같습니다.

예제 #2
11 = 22 / 2와 같이 2를 3번만 사용하여 표현할 수 있습니다.

나의 풀이

def solution(N, number):
    possible_set = [0,[N]] 
    if N == number: 
        return 1
    for i in range(2, 9): 
        case_set = [] 
        case_set.append(int(str(N)*i))
        for i_half in range(1, i//2+1):
            for x in possible_set[i_half]:
                for y in possible_set[i-i_half]: 
                    case_set.append(x+y)
                    case_set.append(x-y)
                    case_set.append(y-x)
                    case_set.append(x*y)
                    if y !=0:
                        case_set.append(x/y)
                    if x !=0:
                        case_set.append(y/x)
            if number in case_set:
                return i
            possible_set.append(case_set) 
    return -1

다이나믹 문제에서 문제를 어떤식으로 풀어야 할지 몰라 많이 시간을 사용했던 문제입니다.

프로그래머스 'N으로 표현' : https://programmers.co.kr/learn/courses/30/lessons/42895

문제 설명

추석 트래픽

이번 추석에도 시스템 장애가 없는 명절을 보내고 싶은 어피치는 서버를 증설해야 할지 고민이다. 장애 대비용 서버 증설 여부를 결정하기 위해 작년 추석 기간인 9월 15일 로그 데이터를 분석한 후 초당 최대 처리량을 계산해보기로 했다. 초당 최대 처리량은 요청의 응답 완료 여부에 관계없이 임의 시간부터 1초(=1,000밀리초)간 처리하는 요청의 최대 개수를 의미한다.

입력 형식

solution 함수에 전달되는 lines 배열은 N(1 ≦ N ≦ 2,000)개의 로그 문자열로 되어 있으며, 각 로그 문자열마다 요청에 대한 응답완료시간 S와 처리시간 T가 공백으로 구분되어 있다.

• 응답완료시간 S는 작년 추석인 2016년 9월 15일만 포함하여 고정 길이 2016-09-15 hh:mm:ss.sss 형식으로 되어 있다.
• 처리시간 T는 0.1s, 0.312s, 2s 와 같이 최대 소수점 셋째 자리까지 기록하며 뒤에는 초 단위를 의미하는 s로 끝난다.
• 예를 들어, 로그 문자열 2016-09-15 03:10:33.020 0.011s은 2016년 9월 15일 오전 3시 10분 **33.010초**부터 2016년 9월 15일 오전 3시 10분 **33.020초**까지 **0.011초** 동안 처리된 요청을 의미한다. (처리시간은 시작시간과 끝시간을 포함)
• 서버에는 타임아웃이 3초로 적용되어 있기 때문에 처리시간은 0.001 ≦ T ≦ 3.000이다.
• lines 배열은 응답완료시간 S를 기준으로 오름차순 정렬되어 있다.

출력 형식

• solution 함수에서는 로그 데이터 lines 배열에 대해 초당 최대 처리량을 리턴한다.
  
  

입출력 예

예제1

• 입력: [
  2016-09-15 01:00:04.001 2.0s,
  2016-09-15 01:00:07.000 2s
  ]

• 출력: 1

예제2

• 입력: [
  2016-09-15 01:00:04.002 2.0s,
  2016-09-15 01:00:07.000 2s
  ]

• 출력: 2

• 설명: 처리시간은 시작시간과 끝시간을 포함하므로
  첫 번째 로그는 01:00:02.003 ~ 01:00:04.002에서 2초 동안 처리되었으며,
  두 번째 로그는 01:00:05.001 ~ 01:00:07.000에서 2초 동안 처리된다.
  따라서, 첫 번째 로그가 끝나는 시점과 두 번째 로그가 시작하는 시점의 구간인 01:00:04.002 ~ 01:00:05.001 1초 동안 최대 2개가 된다.

예제3

• 입력: [
  2016-09-15 20:59:57.421 0.351s,
  2016-09-15 20:59:58.233 1.181s,
  2016-09-15 20:59:58.299 0.8s,
  2016-09-15 20:59:58.688 1.041s,
  2016-09-15 20:59:59.591 1.412s,
  2016-09-15 21:00:00.464 1.466s,
  2016-09-15 21:00:00.741 1.581s,
  2016-09-15 21:00:00.748 2.31s,
  2016-09-15 21:00:00.966 0.381s,
  2016-09-15 21:00:02.066 2.62s
  ]

• 출력: 7

• 설명: 아래 타임라인 그림에서 빨간색으로 표시된 1초 각 구간의 처리량을 구해보면 (1)은 4개, (2)는 7개, (3)는 2개임을 알 수 있다. 따라서 초당 최대 처리량은 7이 되며, 동일한 최대 처리량을 갖는 1초 구간은 여러 개 존재할 수 있으므로 이 문제에서는 구간이 아닌 개수만 출력한다.

나의 풀이

def checktr(time,li):
    c=0
    start=time
    end=time+1000
    for i in li:
        if i[1] >= start and i[0] < end:
            c += 1
    return c

def solution(lines):
    li=[]
    r=1
    for line in lines:
        y,a,b=line.split()
        a=a.split(':')
        b=float(b.replace('s',''))*1000
        end=(int(a[0])*3600 + int(a[1])*60 + float(a[2]))*1000
        start=end-b+1
        li.append([start,end])
    for i in li:
        r=max(r,checktr(i[0],li),checktr(i[1],li))
    return r

1. 로그 문자열에서 시간을 모두 초로 바꿨습니다. 다음 밀리초로 바꿉니다.(1초=1000밀리초)
 처리시간은 시작시간과 끝시간을 포함하기 때문에 +1을 합니다. (처리시간 0.001 더해야 하는데 0.001*1000=1)

2. 초당 최대 처리량은 각 배열의 시작과 끝을 기준으로 최대가 나올 것이기 때문에 시작과 끝만 검사하면 됩니다.
이는 checktr 함수를 통해 구현합니다.
3. time을 기준으로 1초 동안 구간의 처리량을 구하기 위해 1000을 더하고 리스트를 검사합니다.
4. 해당 범위에 속하면 처리량을 더해주고 최대 처리량을 구해 리턴합니다.

프로그래머스 '[1차] 추석 트래픽' : https://programmers.co.kr/learn/courses/30/lessons/17676