프로그래머스 알고리즘 문제 해설 파이썬

0. 프로그래머스 알고리즘 문제 해설 강의 

알고리즘 문제 해설

알고리즘 강의가 있어서 수강했다 

해결코드를 파이썬으로 제공하지 않아서 아쉽지만 문제를 이해하고 해결하는 것에 집중을 하면서 수강했다 

 

1. 자릿수 더하기 

풀이 방법 

1의 자리를 구하기 

1의 자리를 제거하고 나머지 숫자들을 오른쪼으로 한칸씩 이동

이동시킬 숫자가 없을때까지 반복 

 

해결코드 

def solution(n):
    answer = 0 
    while n:
        answer = answer+ n%10 
        n = n//10 
    return answer

숏코드 

def solution(n):
    return sum([int(i) for i in str(n)])

 

2. 순열 검사 문제 

풀이방법 

방법 1)

1. 범위를 벗어나는 값이 있는지 확인 

2. 범위를 벗어나지 않는 값이 몇 번 등장하는지 체크 

방법 2)

배열을 정렬하고 순회하면서 1부터 n까지의 숫자가 모두 있는지 확인

 

해결코드 

def solution(arr):
    answer = True 
    arr.sort()
    
    for i in range(len(arr)):
        if (i+1 != arr[i]):
            return False
    return answer

다른 사람의 코드 

def solution(arr):
    if len(arr) == max(arr):
        return True
    else:
        return False

 

3. 나머지 한 점 문제 

풀이방법

xor연산이 제일 간단하다 

 

해결코드 

'''
비트연산자 xor을 사용하여 풀이한 방법 
같은 값 2개와 다른 값 1개를 연산시키면 다른 값 1개가 반환됨
'''

def solution(pos):
    x = pos[0][0] ^ pos[1][0] ^ pos[2][0]
    y = pos[0][1] ^ pos[1][1] ^ pos[2][1]
    return [x, y]

 

4. 가장 큰 정사각형 찾기 문제

풀이방법

dp(다이나믹프로그래밍)으로 해결

#수식으로 정리
dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])+ 1

해결코드 

def solution(board):
    answer = board[0][0]
    
    for i in range(1, len(board)):
        for j in range(1, len(board[i])):
            if board[i][j] == 1:
                board[i][j] = 1 + min(board[i-1][j-1], board[i-1][j], board[i][j-1])
                answer = max(answer, board[i][j])

    return answer**2

 

 

5. 땅따먹기 문제 

풀이방법

해결코드 

def solution(land):

    for i in range(1,len(land)):
        for j in range(len(land[0])):
            land[i][j] += max(land[i-1][:j] + land[i-1][j+1:])

    return max(land[len(land)-1])

 

6. 스티커 모으기 문제

풀이방법

1. 첫 번째 스티커를 뜯은 경우 

2. 첫 번째 스티커를 뜯지 않은 경우

- 각각에 대해 dp[0], dp[1]을 적절하게 초기화 

- 아래의 식으로 각 i에 대해 최댓값 구하기 

dp[i] = max(dp[i-1], dp[i-2]+sticker[i])

- 둘 중 더 큰 값을 정답으로 리턴 

 

해결코드 

def solution(sticker):
    # table[i] = i번째 스티커를 떼는 경우 최댓값
    # 맨 앞 스티커를 떼는지 아닌지 -> 맨 뒤 스티커에 영향을 준다
    if len(sticker) == 1:
        return sticker[0]
    # 1. 맨 앞 스티커를 떼는 경우
    table1 = [0 for _ in range(len(sticker))]
    table1[0] = sticker[0]
    table1[1] = table1[0]
    for i in range(2, len(sticker)-1):
        table1[i] = max(table1[i-1], table1[i-2] + sticker[i])
    value = max(table1)
    
    # 2. 맨 앞 스티커를 떼지 않는 경우
    table1 = [0 for _ in range(len(sticker))]
    table1[0] = 0
    table1[1] = sticker[1]
    for i in range(2, len(sticker)):
        table1[i] = max(table1[i-1], table1[i-2] + sticker[i])
    return max(value, max(table1))

 

 

7. 단어 퍼즐 문제 

풀이방법

해결코드 

def solution(strs, t):
    n = len(t)
    memo=[float("inf")] * (n+1)
    memo[0]=0
    sizes=set(len(s) for s in strs)
    strs=set(strs)
    for i in range(n+1) :	# t의 시작 인덱스
        for size in sizes :
            if i + size < n + 1 and t[i : i + size] in strs :
                memo[i + size]=min(memo[i + size], memo[i] + 1)
    return memo[n] if memo[n] < float("inf") else -1