Coding Test sorting, greedy

✅ 정렬

🎈 k번째 수

배열 i~j번째로 숫자를 자르고 정렬했을 때 k번쨰 수를 구하는 문제.

def solution(array, commands):
    answer = []
    for i in range(len(commands)):
        result = sorted(array[commands[i][0]-1:commands[i][1]])
        answer.append(result[commands[i][2]-1])
    return answer

< 풀이 과정 >
주어진 array를 commands 길이만큼 반복하여 array배열을 commands내 숫자로 뽑아 sorting한 후, answer에 k번째 수만 append하였다.

🎈 가장 큰 수

양의 정수로 된 배열 numbers가 주어지고 이 문자조합으로 가장 큰 수를 리턴하는 문제

def solution(numbers):
    numbers = list(map(str, numbers))
    numbers.sort(key = lambda x : x*3, reverse = True)
    return str(int(''.join(numbers)))

< 풀이 과정 >
우선 주어진 정수형 리스트를 문자열 리스트로 바꾼 후, numbers 내 원소가 1000이하인 것에 주목했다. 현재 문자형인 numbers를 3배 곱해주어 내림차순 정렬한다. 그렇게 되면, 3과 30을 비교하면 333, 303이되어 3이 더 큰 값을 갖게 된다.

🎈 H-Index

과학자가 발표한 논문 n편 중 h편 이상 인용된 논문이 h편 이상이고 나머지 논문이 h번 이하 인용된 경우, h의 최대값을 구하는 문제.

def solution(citations):
    answer = 0
    citations.sort()
    for i in range(len(citations)):
        if len(citations) - i <= citations[i]:
            return len(citations) - i
    return 0

< 풀이 과정 >
전체 길이 - 인덱스 보다 정렬된 논문 배열의 숫자가 크거나 같은 경우 리턴하면 되는 문제.
return 0을 해준 이유는, 모든 논문의 인용 횟수가 0인 경우도 고려를 해야한다.

✅ 탐욕법 (Greedy)

🎈 체육복

학생마다 번호가 주어지고, 체육복은 앞뒤번호의 학생으로 부터 빌릴 수 있다.
최종적으로 체육복을 가져온 학생의 수를 리턴하는 문제

def solution(n, lost, reserve):
    answer = 0
    reserve_num = set(reserve) - set(lost)
    lost_num = set(lost) - set(reserve)
    for i in reserve_num:
        if i+1 in lost_num:
            lost_num.remove(i+1)
        elif i-1 in lost_num:
            lost_num.remove(i-1)
    answer = n - len(lost_num)
    return answer

< 풀이 과정 >
lost, reserve 배열에서 reserve배열에 속하면서 lost배열에도 속하는 경우가 있다고 문제에서 주어졌다. 이때 해당 학생은 타인에게 체육복을 빌려줄 수 없다.
이 조건을 만족시켜주기 위해 set 자료구조로 중복을 제거한 값들을 reserve_num, lost_num으로 저장하고 for문으로 reserve_num을 탐색해 앞뒤번호가 lost에 있다면 제거하는 방식으로 구현했다.

🎈 조이스틱

조이스틱으로 알파벳 이름을 완성하는 문제, 맨 처음은 A만 주어진다.

• 윗방향 : 다음 알파벳
• 아랫방향 : 이전 알파벳
• 왼쪽방향 : 왼쪽으로 이동 (첫번째 문자 > 마지막 문자로 이동)
• 오른쪽 방향 : 오른쪽으로 이동 (마지막문자 > 첫번째 문자로 이동)

def solution(name):
    answer = 0
    최소 좌우 이동 횟수 저장
    min_move = len(name) - 1
    for i, char in enumerate(name):
    	# 알파벳 상하이동횟수 최솟값 추가
        answer += min(ord(char) - ord('A'), ord('Z') - ord(char) + 1)
        # 연속된 A 인덱스 찾기
        next = i + 1
        while next < len(name) and name[next] == 'A':
            next += 1
        # 최소 좌우 이동횟수, 연속된 A의 왼쪽, 오른쪽 비교해 최솟값 갱신
        min_move = min([min_move, 2*i+len(name)-next, i+2*(len(name)-next)])
    answer += min_move
    return answer

< 풀이 과정 >
주어진 name의 초기 상태는 자리수는 동일하나 A로 채워진 배열임을 알 수 있다. ex) JAZ > AAA로 시작하므로 연속된 A는 찾을 필요가 없다.
따라서 이를 활용하여 상하 방향, 혹은 좌우 방향으로 구분하여 문제를 해결하였다.

• min_move로 주어진 name의 최소 이동 횟수를 미리 계산한다.
• A~Z 사이에 alpha가 존재하므로 차이가 더 작은 값을 선택해 answer에 추가한다.
• next는 결국 연속된 A의 끝 인덱스를 의미하게 되고, 연속된 A의 왼쪽으로 커서를 옮기면 좌우 이동횟수는 2연속된 A 이전 인덱스 + 연속된 A의 오른쪽부분(len(name)-next)가 된다. 반대로 연속된 A의 오른쪽으로 커서를 옮기면 좌우 이동횟수는 2((len(name)-next)) + 연속된 A 이전 인덱스(A의 왼쪽부분)가 된다.

🎈 큰수 만들기

주어진 숫자에서 K개의 수를 제거해 가장 큰 수를 만드는 문제

def solution(number, k):
    answer = []
    for num in number:
        if not answer:
            answer.append(num)
            continue
        if k > 0:
            while answer[-1] < num:
                answer.pop()
                k -= 1
                if not answer or k <= 0:
                    break
        answer.append(num)
    if k > 0:
        answer = answer[:-k]
    else:
        answer
    return ''.join(answer)
    
### 간단 구현
def solution(number, k):
    answer = []
    for num in number:
        while answer and k > 0 and answer[-1] < num:
            answer.pop()
            k -= 1
        answer.append(num)
    return ''.join(answer[:len(answer)-k])

< 풀이 과정 >
주어진 문자 배열 number에서 앞 순서대로 answer에 넣어서 다음 숫자와 비교해 다음 숫자가 더 크면, answer.pop 후 k - 1을 해 작은 수를 제거해준다.
반복문 이후 k가 0보다 큰 경우가 있을 수 있기에, answer[:-k]로 표현해주고, 아닌 경우엔 그냥 answer를 리턴한다. 최종적으로 리스트 내 원소만 리턴해주면 되는 문제.

🎈 구명보트

구명보트는 최대 2인승이고, 사람들 개개인의 몸무게와 탑승 제한 무게가 주어질 때 필요한 구명보트 개수를 리턴하는 문제.

def solution(people, limit):
    answer = 0
    people.sort()
    light = 0
    heavy = len(people) - 1
    while light <= heavy:
        if people[light] + people[heavy] <= limit:
            light += 1
            heavy -= 1
        else:
            heavy -= 1
        answer += 1
    return answer

< 풀이 과정 >
주어진 people 배열을 오름차순으로 정렬해 가벼운 순서부터 나열한 후 가벼운 사람과 무거운 사람을 더해 무게 제한 보다 낮다면 인덱스를 올려가며 반복을 진행한다. 만일 무게 제한보다 무거운 경우, heavy만 태워보낸다. 이러한 반복이 있을 때마다 answer + 1 처리를 해 리턴한다.

🎈 섬 연결하기

n개의 섬 사이에 다리를 건설하는 costs가 주어질때 최소 비용으로 모든 섬이 서로 통행 가능하도록 만드는 최소 비용을 구하는 문제.
costs 배열은 [i, j, c] i>j로 이동하는데 드는 비용c만큼 드는 것을 의미한다.

def find(parent, x):
    if parent[x] != x:
        return find(parent, parent[x])
    else:
        return x
def union(parent, rank, x, y):
    x_root = find(parent, x)
    y_root = find(parent, y)
    if rank[x_root] < rank[y_root]:
        parent[x_root] = y_root
    else:
        parent[y_root] = x_root
        if rank[x_root] == rank[y_root]:
            rank[x_root] += 1
    
def solution(n, costs):
    answer = 0
    costs.sort(key = lambda x: x[2])
    # 노드 번호, 각 노드의 rank값 생성
    parent = [i for i in range(n)]
    rank = [0 for _ in range(n)]
    for cost in costs:
    	# 섬과 섬끼리 연결이 안되어있는 경우
        if find(parent, cost[0]) != find(parent, cost[1]):
            # 합치기
            union(parent, rank, cost[0], cost[1])
            answer += cost[2]
            # 모든 노드 연결 시 종료
            if len(set(parent)) == 1:
                break             
    return answer

< 풀이 과정 >
union-find, union-by rank 기법으로 크루스칼 알고리즘을 풀이하였다.
find 함수로 부모노드를 찾고, union 함수로 두 루트노드의 rank값을 비교해 rank값이 더 높은 쪽이 부모노드를 갖는 식으로 처리하였다.
이후, solution함수로 parent, rank를 만들어 costs를 for문을 돌아 모든 노드가 연결되도록 간선을 연결해준다. 앞서 costs를 비용이 작은 순서대로 정렬 시켜주는 것이 핵심이다.

🎈 단속카메라

차량 별 고속도로 진입 시점, 고속도록 탈출 시점이 주어지고, 모든 차량이 한 번은 단속용 카메라를 만나도록 하기 위해 최대 몇 대의 카메라를 설치해야 하는지를 구하는 문제

def solution(routes):
    answer = 0
    routes.sort(key = lambda x: x[1])
    camera = -30001
    for route in routes:
        if camera < route[0]:
            answer += 1
            camera = route[1]
    return answer

< 풀이 과정 >
주어진 routes에서 route를 고속도로 나가는 지점 기준으로 오름차순 정렬한다.
camera 시작 지점을 범위가 [-30000,30000]이므로 -30001로 시작을 하고 camera가 route[0]보다 작다면 route[1]로 고속도로 나가는 지점으로 카메라를 변경한다.