[Week2 자료구조/알고리즘] TIL 5일차 - 자료구조/알고리즘 적용하기

그동안 배웠던 자료구조들을 이제 문제에 적용해 보자.

 

1) 해시

[programmers-Lv1] 완주하지 못한 선수

프로그래머스

문제 개요

마라톤 경기에 참여한 사람과 완주한 선수의 명단이 주어질 때, 완주하지 못한 선수의 이름을 반환해라.(완주하지 못한 선수는 1명이다)

 

풀이

• 선수의 이름을 key로 선수의 숫자를 value로 하는 dict를 만들어 저장(동명이인이 있을 수 있으므로)
• 완주 명단의 이름이 나오면 해당 dict[key]값을 1 감소
• 값이 0이 아닌 key 값을 반환(=완주하지 못한 선수이다)

def solution(participant, completion):
    print(participant+completion)
    d={}
    for people in participant:
        d[people]=d.get(people, 0)+1
    for peopel in completion:
        d[peopel]-=1
    for key in d.keys():
        if d[key]!=0:
            return key

 

2) 탐욕법

알고리즘의 각 단계에서 그 순간에 최적이라고 생각하는 답을 선택하는 알고리즘

현재의 선택이 마지막 해답의 최적성을 해치지 않을 때 사용한다.

[programmers-Lv1] 체육복

프로그래머스

문제 개요

체육복이 있어야 체육 수업을 들을 수 있다.

여분의 체육복이 있는 학생이 체육복이 없는 학생에게 빌려줄 때, 체육수업을 들을 수 있는 최대 학생수를 구하는 문제

(단, 자신이 여분의 체육복이 있지만, 체육복을 잃어버렸을 경우에는 자신이 사용하고 빌려주지 않는다.) 

 

풀이 1

하나의 배열에 모든 학생의 정보를 저장한다.(편하게 인덱싱 하기 위해 리스트 길이를 앞뒤 한 칸씩 추가)

• 초기 배열의 원소값은 1
• 여분의 체육복이 있는 경우 +1
• 체육복을 잃어버린 학생의 경우 -1
• 해당 배열에 대해 값이 0이면(체육복이 없으면) 앞뒤 학생의 값을 확인해 빌린다.

def solution(n, lost, reserve):
    student=[1 for i in range(n+2)]
    for r in reserve:
        student[r]+=1
    for l in lost:
        student[l]-=1
    
    for idx in range(1, len(student)-1):
        if student[idx]==0: #좌우 확인
            if student[idx-1]>=2:
                student[idx]=1
                student[idx-1]-=1
            elif student[idx+1]>=2:
                student[idx]=1
                student[idx+1]-=1
            else:
                continue
    answer=0
    for s in student:
        if s>=1:
            answer+=1
    return answer-2

 

풀이 2

앞선 풀이 1은 학생의 수가 커지면 시간 복잡도가 많이 걸린다.

확인해야 할 학생만 확인하는 방법(lost나 reserve)

• 집합(set) 이용 : 자기 자신이 여분의 체육복이 있고, 체육복을 잃어버렸으면 두 배열에서 삭제
• lost 학생의 수 <reserve 학생의 수 : lost 배열을 기준으로 확인
  • lost의 학생을 크기 순으로 정렬한 뒤, 해당 원소의 앞뒤 학생이 여분의 체육복이 있는지 (reserve에 원소가 있는지) 확인
• lost 학생의 수> reserve 학생의 수 : reseve 배열을 기준으로 확인
  • reserve의 학생을 크기 순으로 정렬한 뒤, 해당 원소의 앞뒤 학생이 여분의 체육복이 있는지 (reserve에 원소가 있는지) 확인

def solution(n, lost, reserve):
    lost, reserve=list(set(lost)-set(reserve)), list(set(reserve)-set(lost))
    answer=n-len(lost)
    lost.sort(reverse=True)
    reserve.sort(reverse=True)
    if len(lost)<len(reserve): #lost 기준으로 확인
        while len(lost)!=0 and len(reserve)!=0:
            minus=lost[-1]-1
            plus=lost[-1]+1
            lost.pop()
            if minus in reserve:
                reserve.remove(minus)
            elif plus in reserve:
                reserve.remove(plus)
            else:
                continue
            answer+=1
    else:#Reserve 기준으로 확인
        while len(reserve)!=0 and len(lost)!=0:
            minus=reserve[-1]-1
            plus=reserve[-1]+1
            reserve.pop()
            if minus in lost:
                lost.remove(minus)
            elif plus in lost:
                lost.remove(plus)
            else:
                continue
            answer+=1
                
            
    return answer

 

[programmers-Lv2] 큰 수 만들기

프로그래머스

문제 개요

어떤 수에서 k개의 수를 제거하여 얻을 수 있는 최대 수를 반환하여라.

 

풀이

앞, 뒤 원소를 비교

• k개의 원소를 꺼내거나, 끝까지 검사했을 때 앞의 원소가 뒤에 원소보다 크거나 같아야 함
• k 개의 원소를 꺼내지 못하고 반복문이 종료되면, 제거된 수의 앞의 원소가 뒤에 원소보다 크다는 뜻이므로 뒤에서 나머지 k자리 제거

def solution(number, k):
    if len(number)-k==1:
        return max(number)
    answer=""
    last=[number[0]]
    idx=1
    while k>0 and idx<len(number):
        if last[-1]<number[idx]:
            while k>0 and len(last)>0 and last[-1]<number[idx]:
                last.pop()
                k-=1
        last.append(number[idx])
        idx+=1
    if idx<len(number):
        last+=(number[idx:])
    if k>0:
        last=last[:-(k)]
    return ''.join(last)

 

3) 정렬

key 옵션을 이용하면 원하는 기준에 따라 정렬 시킬 수 있다.

[programmers-Lv2] 가장 큰 수

프로그래머스

문제 개요

n개의 수가 주어질 때, 해당 숫자를 배치해서 얻을 수 있는 최대 수를 반환하여라(수는 1000 이하이다.)

 

풀이 1

수의 [0], [1], [2], [3] 번째의 크기를 비교해야 한다.

def solution(numbers):
    str_numbers=[str(num) for num in numbers]
    str_numbers.sort(key=lambda x : (x*1000)[:4], reverse=True)
    str_numbers=''.join(str_numbers)    
    return str_numbers if str_numbers[0]!="0" else "0"

 

4) 힙

파이썬의 내장 자료형을 이용해서 힙 자료구조를 사용해 보자.

 

import heapq

자주 사용되는 연산은 다음과 같다.

🦛heapq.heapify(list) → heap : $O(nlogn)$
list를 heap으로 변환
🦛heapq.heappush(heap, item) → None : $O(logn)$
item을 heap에 추가
🦛heapq.heappop(heap) → item :$O(logn)$
heap에서 가장 작은 원소를 pop, 비어 있는 경우 IndexError가 호출

[programmers-Lv1] 더 맵게

문제 개요

모든 원소를 특정값 이상으로 만드려고 한다.

특정값 이하인 원소들에 대해 (최솟값+두 번째 최솟값*2) 연산을 수행해서 특정값 이상으로 만들려고 할 때, 최소 연산 횟수를 구하는 문제이다.

 

최솟값들을 계속 얻어야 하기 때문에 힙 자료구조(최소힙)를 사용하면 시간복잡도를 줄일 수 있다.

 

풀이

• heap.pop의 값이 K보다 크면 나머지 모든 원소가 K보다 크다는 의미 이므로 지금까지의 연산 횟수를 반환
• K보다 작으면, $최솟값1+2*최솟값2$ 연산을 수행한 뒤 삽입

import heapq
def solution(scoville, K):
    heapq.heapify(scoville)
    answer=0
    while len(scoville)!=0:
        num1=heapq.heappop(scoville)
        if num1>=K:
            break
        else:
            if len(scoville)==0:
                return -1
            else:
                num2=heapq.heappop(scoville)
                heapq.heappush(scoville, num1+2*num2)
                answer+=1

    return answer

 

5) 동적계획법(Dynamic programming)

알고리즘 진행에 따라 탐색해야 할 범위를 동적으로 결정함으로써 탐색 범위를 한정할 수 있는 알고리즘을 말한다.

ex) 피보나치수열, 배낭에 물건 담기(knapsack)

 

[programmers-Lv3] N으로 표현

프로그래머스

문제 개요

어떤 수가 주어질 때, 어떤 수와 사칙연산만을 이용해서 특정값을 만들 때, 어떤 수를 최소로 사용을 구하여라.

ex) 5(어떤 수), 특정값(12) 이면 (55+5)/5 4번이다.

 

풀이

그전에 어떤 수를 1, 2, 3,... k번 이용해서 만들 수 있는 수들을 이용해  k+1번 이용해서 만들 수 있는 집합을 구하는 방법을 이용한다.

ex) 5번 사용 = (1, 4), (2, 3) 이용

• dict를 이용해 어떤 수를 k번 이용해서 만들 수 있는 집합을 저장
• set을 이용해 중복된 수를 제거

def solution(N, number):
    first=[N]
    second=list(set([10*N+N, N+N, N-N, N*N, N//N]))
    num_dict={1:first, 2:second}
    
    if N==number:
        return 1

    answer=2
    while (number not in num_dict[answer]):
        if answer>8:
            return -1
        now=[]
        sum=N
        for i in range(1, answer+1):
            sum+=N*(10**i)
        now.append(sum)
        
        for idx in range(1, (answer+1)//2+1, 1):
            prev1=num_dict[idx]
            prev2=num_dict[(answer+1)-idx]
            for num1 in prev1:
                for num2 in prev2:
                    now.append(num1+num2)
                    now.append(num1-num2)
                    now.append(num2-num1)
                    now.append(num1*num2)
                    if num2!=0:
                        now.append(num1//num2)
                    if num1!=0:
                        now.append(num2//num1)
        answer+=1
        num_dict[answer]=list(set(now))
    return answer

 

6) DFS/BFS

DFS : 깊이 우선 탐색 with Stack

한정점에서 인접한 방문하지 않은 정점을 방문하되, 끝의 자식노드까지 탐색을 끝낸 뒤 다음 정점으로 진행

BFS : 너비 우선 탐색 with Queue

한 정점에서 인접한 방문하지 않은 정점을 방문하되, 모든 같은 레벨의 노드 탐색을 끝낸 뒤 다음 레벨로 탐색을 진행

 

[programmers-Lv3] 여행경로

프로그래머스

문제 개요

출발지와 비행기의 항공권 정보가 주어질 때, 모든 항공권을 사용한 비행기의 경로를 구하는 문제

단, 가능한 경로가 여러 개인 경우 알파벳 순서가 앞서는 경로를 반환

 

풀이

깊이 우선 방식을 이용하여 최적해를 찾으면 반환하게 한다.

• 항공권을 출발지를 key로 하는 dictionary에 저장한 뒤, 알파벳 역순으로 정렬(시간복잡도가 $O(n)$인 list.pop()을 이용하기 위해
• 스택에 최상위 장소를 출발지로 하는 항공권이 있는지 탐색
  • 있으면 스택에 도착지를 추가
  • 없으면 해당 도착지를 경로에 추가

from collections import defaultdict

def solution(tickets):
    routes = {}
    
    for t in tickets:
        routes[t[0]]=routes.get(t[0], [])+[t[1] ]   
    # 목적지 기준 내림차순 정렬(시간복잡도 O(1)인 pop 연산 사용)
    for key in routes.keys():
        routes[key].sort(reverse = True)
    
    print(routes)
    stack = ["ICN"]
    path = []
    path_idx=[]
    
    while len(stack)>0:
        top=stack[-1]
        if top not in routes or len(routes[top])==0:
            path.append(stack.pop())
        else:
            stack.append(routes[top].pop())

        
    
    return path[::-1]