Henry's Algorithm

문제 설명

한자리 숫자가 적힌 종이 조각이 흩어져있습니다. 흩어진 종이 조각을 붙여 소수를 몇 개 만들 수 있는지 알아내려 합니다.

각 종이 조각에 적힌 숫자가 적힌 문자열 numbers가 주어졌을 때, 종이 조각으로 만들 수 있는 소수가 몇 개인지 return 하도록 solution 함수를 완성해주세요.

제한사항

• numbers는 길이 1 이상 7 이하인 문자열입니다.
• numbers는 0~9까지 숫자만으로 이루어져 있습니다.
• 013은 0, 1, 3 숫자가 적힌 종이 조각이 흩어져있다는 의미입니다.

입출력 예

numbers   return

입출력 예 설명

예제 #1
[1, 7]으로는 소수 [7, 17, 71]를 만들 수 있습니다.

예제 #2
[0, 1, 1]으로는 소수 [11, 101]를 만들 수 있습니다.

• 11과 011은 같은 숫자로 취급합니다.

문제푸는 방법:

완전 탐색으로 풀 수 있다.

for문을 통해 모든 원소에 접근하여 소수인지 아닌지 판별한다.

정답 코드:

def solution(numbers):
    from itertools import permutations
    c = {}
    answer = 0
    arr = [i for i in numbers]
    for i in range(1,len(arr)+1):
        a = list(set(permutations(arr,i)))
        for j in range(len(a)):
            b = ""
            for k in a[j]:
                b += str(k)
            if is_sosu(int(b)) and int(b) not in c:
                c[int(b)] = 1
                answer += 1
    return answer

def is_sosu(num):
    if num <= 1:
        return False
    for i in range(2,num//2+1):
        if num%i == 0:
            return False
    return True

문제 설명

n개의 노드가 있는 그래프가 있습니다. 각 노드는 1부터 n까지 번호가 적혀있습니다. 1번 노드에서 가장 멀리 떨어진 노드의 갯수를 구하려고 합니다. 가장 멀리 떨어진 노드란 최단경로로 이동했을 때 간선의 개수가 가장 많은 노드들을 의미합니다.

노드의 개수 n, 간선에 대한 정보가 담긴 2차원 배열 vertex가 매개변수로 주어질 때, 1번 노드로부터 가장 멀리 떨어진 노드가 몇 개인지를 return 하도록 solution 함수를 작성해주세요.

제한사항

• 노드의 개수 n은 2 이상 20,000 이하입니다.
• 간선은 양방향이며 총 1개 이상 50,000개 이하의 간선이 있습니다.
• vertex 배열 각 행 [a, b]는 a번 노드와 b번 노드 사이에 간선이 있다는 의미입니다.

입출력 예

nvertexreturn

입출력 예 설명

예제의 그래프를 표현하면 아래 그림과 같고, 1번 노드에서 가장 멀리 떨어진 노드는 4,5,6번 노드입니다.

문제 푸는 방법:

BFS 알고리즘으로 한 칸씩 가면서 Count를 +1 씩 해주면된다.

마지막 Visited 리스트에서 Counter 함수를 통해 중복값끼리 모으고 Sorting 하여 최대값을 알아낸다.

정답 코드:

from collections import deque, Counter

def solution(n, edge):
    answer = 0
    graph = {}
    for i in edge:
        if i[0] in graph:
            graph[i[0]].append(i[1])
        else:
            graph[i[0]] = [i[1]]
        if i[1] in graph:
            graph[i[1]].append(i[0])
        else:
            graph[i[1]] = [i[0]]
    
    result = bfs(graph,1)
    result = sorted(result.values(), reverse=True)
    return list(Counter(result).values())[0]

def bfs(edge,root):
    visited = {}
    queue=deque([[root,0]])
    arr = [[root,0]]
    while queue:
        current = queue.popleft()
        if current[0] not in visited:
            visited[current[0]] = current[1]
            add = set(edge[current[0]]) - set(visited)
            queue += ([[i,current[1]+1] for i in add])
    return visited

나의 생각:

드디어 경로 문제의 첫 발을 띄었다.

항상 알고리즘 문제에서 경로 문제를 제일 어려워했는데,

프로그래머스의 Level 2의 조금 쉬운 문제로 시작했다.

생각보다 어려운 공식이 아니었다. 앞으로 경로 문제 풀 때 괜히 겁먹지 말자!

화이팅!!

NHN 코딩테스트를 대비하며 Java 로도 풀어보았다.

푸는 방식은 위의 파이썬 코드 설명과 같다. 화이팅!

import java.util.*;

class Solution {
    public int solution(int n, int[][] edge) {
        int answer = 0;
        ArrayList<ArrayList<Integer>> list = new ArrayList<ArrayList<Integer>>();
        for(int i=0; i<edge.length; i++){
            list.add(new ArrayList<Integer>());
        }
        for(int[] i:edge){
            int a = i[0];
            int b = i[1];
            list.get(a).add(b);
            list.get(b).add(a);
        }
        int[] cnt = new int[n+1];
        cnt[0]=cnt[1] = 0;
        boolean[] visited = new boolean[n+1];
        visited[0]=visited[1] = true;
        Queue<Integer> q = new LinkedList<Integer>();
        q.add(1);// 시작점
        while(!q.isEmpty()){
            int cur = q.poll();
            for(int v:list.get(cur)){
                if(!visited[v]){
                    visited[v] = true;
                    cnt[v] = cnt[cur]+1;
                    q.add(v);
                }
            }
        }
        int max = 0;
        int ans = 0;
        for(int i: cnt){
            if(max<i){
                max = i;
                ans = 1;
            }else if(max == i){
                ans += 1;
            } 
        }
        
        return ans;
    }
}

문제 설명

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

풀었는데

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

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

문제 설명

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