[인공지능 데브코스] 1주차 day3 - 알고리즘 문제풀이(1)

12월 02일 수

오늘은 파이썬으로 프로그래머스 알고리즘 문제들을 풀어봤다. 예전에 C로 풀어봤던 문제들도 있었지만 파이썬으로 풀어보는 것은 처음이라 새로웠다. 문제를 혼자 풀어보고 풀이를 보는 방식으로 진행했는데 파이썬은 여러가지 테크닉들이 코드를 간결하게 만드는데 중요하다는 사실을 알 수 있었다. 유용한 테크닉들에 익숙해지고 기억해놔야 겠다는 생각이 들었다. 모든 문제들은 프로그래머스 사이트에 있는 문제들이기 때문에 문제의 설명은 생략하였다.

완주하지 못한 선수(Hash)

해시를 사용해서 푸는 문제로 파이썬에서는 dictionary라는 해시를 기본자료형으로 제공하기 때문에 dictionary를 사용해서 풀었다.
이 문제에서 중요한 점은 이름이 중복되는 선수들을 처리해야 한다는 것인데 다음과 같은 방법으로 해결했다.

def solution(participant, completion):
    key = list(set(participant))
    val = [0 for i in range(len(key))]
    dic = dict(zip(key,val))
    
    for p in participant:
        dic[p] += 1
    for c in completion:
        dic[c] -= 1
        
    one = [k for k,v in dic.items() if v == 1]
    return one[0]

 

체육복(Greedy)

Greedy 문제로 학생들이 가지고 있는 체육복의 개수를 구하고 모든 학생들 을 순회하면서 앞에있는 학생에게 빌리도록 하면 해결된다.

def solution(n, lost, reserve):
    answer = 0
    num = [1 for i in range(n)]
    for l in lost:
        num[l-1] -= 1
    for r in reserve:
        num[r-1] += 1
    answer = num.count(1) + num.count(2)
    for i in range(len(num)):
        if num[i] == 0:
            if i-1 > 0 and num[i-1] > 1:
                answer += 1
            elif i+1 < len(num) and num[i+1] > 1:
                num[i+1] = 1
                answer += 1
    return answer

 

가장 큰 수(Sort)

Sort를 이용하여 푸는 문제이다.
파이썬이기 때문에 코드가 간결해 질 수 있는 부분이 많은 문제인 것 같다.
numbers를 먼저 문자열로 바꾸고 3번 반복하여 만든 문자의 사전적 배열기준으로 sort를 진행하였다.
모든 숫자가 0인 경우는 앞에서 미리 처리해 주었다.

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

 

큰 수 만들기(Greedy)

Greedy 문제로 앞에서부터 순회하다가 자신보다 큰 숫자가 뒤에 나오면 앞의 숫자를 제거해 준다는 방법으로 해결하였다.
삭제하는 시행을 항상 숫자열의 처음부터 시행하게 코드를 작성했다가 시간 초과가 나왔었다.
빈 리스트를 선언하고 하나씩 원소를 넣어주면서 맨 뒤에 있는 숫자보다 새로운 숫자가 더 크다면 작아질때까지 리스트의 맨 끝 원소를 pop해주는 방법으로 구현하면 $O(n)$ 으로 구현이 가능하다.

def solution(number, k):
    ans = []

    for i, num in enumerate(number):
        while len(ans) > 0 and ans[-1] < num and k>0:
            ans.pop()
            k -= 1
        if k==0:
            ans += list(number[i:])
            break
        ans.append(num)
            
    return ''.join(ans) if k==0 else ''.join(ans[:-k])