Henry's Algorithm

문제 설명

H-Index는 과학자의 생산성과 영향력을 나타내는 지표입니다. 어느 과학자의 H-Index를 나타내는 값인 h를 구하려고 합니다. 위키백과1에 따르면, H-Index는 다음과 같이 구합니다.

어떤 과학자가 발표한 논문 n편 중, h번 이상 인용된 논문이 h편 이상이고 나머지 논문이 h번 이하 인용되었다면 h의 최댓값이 이 과학자의 H-Index입니다.

어떤 과학자가 발표한 논문의 인용 횟수를 담은 배열 citations가 매개변수로 주어질 때, 이 과학자의 H-Index를 return 하도록 solution 함수를 작성해주세요.

제한사항

• 과학자가 발표한 논문의 수는 1편 이상 1,000편 이하입니다.
• 논문별 인용 횟수는 0회 이상 10,000회 이하입니다.

입출력 예

citationsreturn

입출력 예 설명

이 과학자가 발표한 논문의 수는 5편이고, 그중 3편의 논문은 3회 이상 인용되었습니다. 그리고 나머지 2편의 논문은 3회 이하 인용되었기 때문에 이 과학자의 H-Index는 3입니다.

※ 공지 - 2019년 2월 28일 테스트 케이스가 추가되었습니다.

1. https://en.wikipedia.org/wiki/H-index 위키백과 ↩

문제 푸는 방법:

1. 정렬한다.

2. 하나씩 탐색하면서 H-Index인지 확인한다.

사실 H-Index에 대한 정의를 제대로 이해하지 못해서 문제를 조금 해맸다.

문제를 잘 파악하는 것도 길러야겠다.

정답 코드:

def solution(citations):
    citations = sorted(citations, reverse= True)
    answer = 0
    for i in range(len(citations)):
        if citations[i] >= i+1:
            answer = i+1
    return answer

문제 설명

이중 우선순위 큐는 다음 연산을 할 수 있는 자료구조를 말합니다.

명령어수신 탑(높이)

이중 우선순위 큐가 할 연산 operations가 매개변수로 주어질 때, 모든 연산을 처리한 후 큐가 비어있으면 [0,0] 비어있지 않으면 [최댓값, 최솟값]을 return 하도록 solution 함수를 구현해주세요.

제한사항

• operations는 길이가 1 이상 1,000,000 이하인 문자열 배열입니다.
• operations의 원소는 큐가 수행할 연산을 나타냅니다.
  • 원소는 “명령어 데이터” 형식으로 주어집니다.- 최댓값/최솟값을 삭제하는 연산에서 최댓값/최솟값이 둘 이상인 경우, 하나만 삭제합니다.
• 빈 큐에 데이터를 삭제하라는 연산이 주어질 경우, 해당 연산은 무시합니다.

입출력 예

operations  return

입출력 예 설명

16을 삽입 후 최댓값을 삭제합니다. 비어있으므로 [0,0]을 반환합니다.
7,5,-5를 삽입 후 최솟값을 삭제합니다. 최대값 7, 최소값 5를 반환합니다.

문제푸는 방법:

heap를 2개 만든다.

maxheap과 minheap을 만들어서 빼줄때 같이 빼주고, 더해줄 때 같이 더해주면 된다.

정답 코드

def solution(operations):
    import heapq
    answer = []
    maxheap = []
    minheap = []
    
    for i in operations:
        if i[0] == "I":
            heapq.heappush(minheap,int(i[2:]))
            heapq.heappush(maxheap,-1 * int(i[2:]))
        else:
            if len(minheap) == 0:
                    continue
            if i[2] == "-":
                num = heapq.heappop(minheap)
                maxheap.remove(-1*num)
            else:
                num = heapq.heappop(maxheap)
                minheap.remove(-1*num)
    if len(minheap) == 0:
        return [0,0]
    else:
        return [-1*heapq.heappop(maxheap),heapq.heappop(minheap)]

문제 설명

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

예를들어

- 0ms 시점에 3ms가 소요되는 A작업 요청 - 1ms 시점에 9ms가 소요되는 B작업 요청 - 2ms 시점에 6ms가 소요되는 C작업 요청

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

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

- A: 3ms 시점에 작업 완료 (요청에서 종료까지 : 3ms) - B: 1ms부터 대기하다가, 3ms 시점에 작업을 시작해서 12ms 시점에 작업 완료(요청에서 종료까지 : 11ms) - C: 2ms부터 대기하다가, 12ms 시점에 작업을 시작해서 18ms 시점에 작업 완료(요청에서 종료까지 : 16ms)

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

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

- A: 3ms 시점에 작업 완료(요청에서 종료까지 : 3ms) - C: 2ms부터 대기하다가, 3ms 시점에 작업을 시작해서 9ms 시점에 작업 완료(요청에서 종료까지 : 7ms) - B: 1ms부터 대기하다가, 9ms 시점에 작업을 시작해서 18ms 시점에 작업 완료(요청에서 종료까지 : 17ms)

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

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

제한 사항

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

입출력 예

jobsreturn

입출력 예 설명

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

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

문제 푸는 방법은

heap 2개를 사용해서 풀었다.

1. 문제에 리스트가 정렬되어 들어온다는 이야기가 없으므로 리스트를 정렬한다.

2. 정렬된 리스트에서 최초 1개를 processed(heap)에 집어넣는다.(가장 먼저 들어온 디스크)

3. 해당 디스크를 실행한다. 실행한다는 것은 실행 완료된 디스크 리스트 넣는것을 의미.

4. 실행이 끝난 리스트의 작업 시간이 따라 1번에서 정렬된 리스트에서 값을 nexts(heap)에 넣는다.
5. nexts 중에서 가장 첫 번째 값을 가져온다.

6. 더 이상 jobs에 값이 없고 nexts가 빈 리스트가 될때가지 반복한다. 

요약:

jobs[0] -> processed

jobs -> nexts

jobs,nexts가 모두 빌 때가지 반복

코드:

def solution(jobs):
    import heapq
    jobs = sorted(jobs)
    processed = []
    arr = []
    nexts = []
    start = jobs.pop(0)
    time = start[0]
    heapq.heappush(processed,[start[1],start[0]])
    while processed:
        current_job = heapq.heappop(processed)
        arr.append(current_job[0]+(time-current_job[1]))
        time +=  current_job[0]
        while jobs:
            if jobs[0][0] <= time:
                ne = jobs.pop(0)
                heapq.heappush(nexts,[ne[1],ne[0]])
            else:
                if len(nexts) == 0:
                    ne = jobs.pop(0)
                    time = ne[0]
                    heapq.heappush(nexts,[ne[1],ne[0]])
                break
        if len(nexts) == 0:
            return sum(arr)//len(arr)
        heapq.heappush(processed,heapq.heappop(nexts))
    
    
    return 0

풀었는데

코드가 너무 복잡해서 같아서 최적화 하고 싶다!!!

최적화 하는 방법을 생각해보자

2020 하반기 SKTelecom 수시채용에 지원하여

코딩테스트를 보았다.

수시채용은 서류와 코딩테스트를 함께 심사한다고 한다.

전체적으로 어렵진 않았으나,

여러가지 고려해야하는 부분들이 많이 있었다.

1. 코드를 얼마나 효율적으로 짤 것인지

2. 코드를 얼마나 정확하게 짤 수 있는지

3. 필요한 내장 라이브러리를 잘 활용할 수 있는지

에 대해서 보는 것 같았다.

그래도 문제를 다 풀어서 제출했다.

SKTelecom 서류를 다시 찾아보려고 했는데,

이상하게 사이트에서 어떻게 찾아야 하는지 모르겠다.

면접왕 이형께서 서류와 면접은 병행하여 준비하는 것이라고 하셨기 때문에

나도 다시한번 내가 제출한 SKTelecom 서류 찾아보고 준비해야겠다.

지금 시간은 10시 9분..

7시부터 시작해서 3시간동안 쿠팡 코딩테스트를 봤다.

코딩테스트 플랫폼이 여러개가 있는데, 프로그래머스에서 본다.

그 동안 Codility만 공부했던 나에게는 생각보다 어렵게 느껴졌다.

지극히 주관적인 플랫폼 난이도를 따진다면,

프로그래머스 > 백준 > Codility 인거 같다.

총 4개의 문제 중에 1,3번 문제는 어떻게 풀어야할 지 확실하게 감이 왔다.

플랫폼 환경에서 바로 풀지는 않고, jupyter 켜놓고 테스트하고 최적화시키면서 풀려고 노력했다.

약 1시간 반 정도 걸렸다.

그리고 1시간 반 동안 2번 문제 풀어서 테스트종료 남겨두고 긴박하게 제출했다.

처음에 어떻게 접근해야할지 방황했다.

Class를 만들어서 풀어야 하는지, list를 사용해서 풀어야 하는지 고민하다가

두 가지 방법을 모두 사용해봤고, 마지막에 list만 만들어서 테스트케이스 맞추고 제출했다.

문제에 대한 유출은 할 수 없기에 여기서 적을 순 없지만,

마지막 문제는 내가 취약한 유형의 문제였다.

이 유형은 어쩌면 코딩테스트 단골 문제라고 생각이 된다.

그런데 아직도 제대로 접근을 못한다.

이 유형에 대한 문제를 꼭 마스터 하고 싶다. 오히려 만났을 때 반가울 수 있도록..!!

앞으로도 부족한 부분을 채워가면서 꼭 취뽀하자!

문제 설명

0 또는 양의 정수가 주어졌을 때, 정수를 이어 붙여 만들 수 있는 가장 큰 수를 알아내 주세요.

예를 들어, 주어진 정수가 [6, 10, 2]라면 [6102, 6210, 1062, 1026, 2610, 2106]를 만들 수 있고, 이중 가장 큰 수는 6210입니다.

0 또는 양의 정수가 담긴 배열 numbers가 매개변수로 주어질 때, 순서를 재배치하여 만들 수 있는 가장 큰 수를 문자열로 바꾸어 return 하도록 solution 함수를 작성해주세요.

제한 사항

• numbers의 길이는 1 이상 100,000 이하입니다.
• numbers의 원소는 0 이상 1,000 이하입니다.
• 정답이 너무 클 수 있으니 문자열로 바꾸어 return 합니다.

입출력 예

numbersreturn

푸는 방법:

정렬을 숫자가 아닌 문자로 하는 것이 키 포인트이다.

[3,30,2,6,41] => 각 원소에 *2~3 해준다. 이유는 1~1000이하의 수라고 하였기 때문에.

각 원소에 *2 해주면 => [33,3030,22,66,4141] 이것을 정렬한다.

정렬하면 [66,4141,33,3030,22] 이다. 이 원리를 활용하여 리스트를 정렬하고 문제를 풀면 된다.

사실 이전에는 그냥 숫자로 정렬하려고 했는데, 조건이 정말 어려가지가 걸려야해서, 이 방식은 아니었다.

정답

def solution(numbers):
    answer = ''
    a = [str(i) for i in numbers]
    a = sorted(a, key=lambda x:x*3, reverse=True)
    
    return str(int(''.join(a)))

문제 설명

매운 것을 좋아하는 Leo는 모든 음식의 스코빌 지수를 K 이상으로 만들고 싶습니다. 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 Leo는 스코빌 지수가 가장 낮은 두 개의 음식을 아래와 같이 특별한 방법으로 섞어 새로운 음식을 만듭니다.

섞은 음식의 스코빌 지수 = 가장 맵지 않은 음식의 스코빌 지수 + (두 번째로 맵지 않은 음식의 스코빌 지수 * 2)

Leo는 모든 음식의 스코빌 지수가 K 이상이 될 때까지 반복하여 섞습니다.
Leo가 가진 음식의 스코빌 지수를 담은 배열 scoville과 원하는 스코빌 지수 K가 주어질 때, 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 섞어야 하는 최소 횟수를 return 하도록 solution 함수를 작성해주세요.

제한 사항

• scoville의 길이는 2 이상 1,000,000 이하입니다.
• K는 0 이상 1,000,000,000 이하입니다.
• scoville의 원소는 각각 0 이상 1,000,000 이하입니다.
• 모든 음식의 스코빌 지수를 K 이상으로 만들 수 없는 경우에는 -1을 return 합니다.

입출력 예

scovilleKreturn

입출력 예 설명

1. 스코빌 지수가 1인 음식과 2인 음식을 섞으면 음식의 스코빌 지수가 아래와 같이 됩니다.
   새로운 음식의 스코빌 지수 = 1 + (2 * 2) = 5
   가진 음식의 스코빌 지수 = [5, 3, 9, 10, 12]

2. 스코빌 지수가 3인 음식과 5인 음식을 섞으면 음식의 스코빌 지수가 아래와 같이 됩니다.
   새로운 음식의 스코빌 지수 = 3 + (5 * 2) = 13
   가진 음식의 스코빌 지수 = [13, 9, 10, 12]

모든 음식의 스코빌 지수가 7 이상이 되었고 이때 섞은 횟수는 2회입니다.

정렬해서 최소 부분을 반복해서 체크해주면 되는 문제이다.

그러나 단순히 sorted(arr) 이 코드를 반복하여 진행하게 되면 Timeout 이 발생하여 문제를 풀 수 가 없다.

그래서 이 부분은 Python import heapq를 불러와서 풀어주었다.

~보다 작은/ ~ 보다 큰 에 대한 문제는 heap을 사용하여 문제를 풀면 성능적으로 우수한 프로그램을 만들 수 있다.

def solution(scoville, K):
    import heapq
    answer = 0
    h = []
    for i in scoville:
        heapq.heappush(h,i)
    while len(h) >= 1:
        first = heapq.heappop(h)
        if first < K:
            answer += 1
            if len(h) == 0:
                return -1
            heapq.heappush(h, first + (heapq.heappop(h))*2)
        else:
            return answer
    

기본적으로 Python에서 제공해주는 heap은 minheap을 의미한다.

최대 힙(Maxheap)을 구현하는 방법은 아래와 같다.

import heapq

nums = [4, 1, 7, 3, 8, 5]
heap = []

for num in nums:
	heapq.heappush(heap, (-num, num))  # (우선 순위, 값)

while heap:
	print(heapq.heappop(heap)[1])  # index 1

문제 설명

일반적인 프린터는 인쇄 요청이 들어온 순서대로 인쇄합니다. 그렇기 때문에 중요한 문서가 나중에 인쇄될 수 있습니다. 이런 문제를 보완하기 위해 중요도가 높은 문서를 먼저 인쇄하는 프린터를 개발했습니다. 이 새롭게 개발한 프린터는 아래와 같은 방식으로 인쇄 작업을 수행합니다.

1. 인쇄 대기목록의 가장 앞에 있는 문서(J)를 대기목록에서 꺼냅니다. 2. 나머지 인쇄 대기목록에서 J보다 중요도가 높은 문서가 한 개라도 존재하면 J를 대기목록의 가장 마지막에 넣습니다. 3. 그렇지 않으면 J를 인쇄합니다.

예를 들어, 4개의 문서(A, B, C, D)가 순서대로 인쇄 대기목록에 있고 중요도가 2 1 3 2 라면 C D A B 순으로 인쇄하게 됩니다.

내가 인쇄를 요청한 문서가 몇 번째로 인쇄되는지 알고 싶습니다. 위의 예에서 C는 1번째로, A는 3번째로 인쇄됩니다.

현재 대기목록에 있는 문서의 중요도가 순서대로 담긴 배열 priorities와 내가 인쇄를 요청한 문서가 현재 대기목록의 어떤 위치에 있는지를 알려주는 location이 매개변수로 주어질 때, 내가 인쇄를 요청한 문서가 몇 번째로 인쇄되는지 return 하도록 solution 함수를 작성해주세요.

제한사항

• 현재 대기목록에는 1개 이상 100개 이하의 문서가 있습니다.
• 인쇄 작업의 중요도는 1~9로 표현하며 숫자가 클수록 중요하다는 뜻입니다.
• location은 0 이상 (현재 대기목록에 있는 작업 수 - 1) 이하의 값을 가지며 대기목록의 가장 앞에 있으면 0, 두 번째에 있으면 1로 표현합니다.

입출력 예

prioritieslocationreturn

입출력 예 설명

예제 #1

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

예제 #2

6개의 문서(A, B, C, D, E, F)가 인쇄 대기목록에 있고 중요도가 1 1 9 1 1 1 이므로 C D E F A B 순으로 인쇄합니다.

zip을 사용해서 풀었다.

문제에서 말하는 요구사항 그대로 풀었다.

"맨 앞에 확인해서 가장 큰 값이면 answer +1, 아니면 맨 뒤로 append"

생각보다 문제가 어렵지 않았다.

정답 코드

def solution(priorities, location):
    answer = 0
    arr = []
    for x,y in zip(priorities,range(len(priorities))):
        arr.append([x,y])
    while arr:
        front = arr.pop(0)
        if len(arr) == 0:
            return answer + 1
        if max(front[0], max([i[0] for i in arr])) == front[0]:
            answer += 1
            if front[1] == location:
                return answer
        else:
            arr.append(front)
    
    
    return answer