그냥 코딩하는 사람의 블로그

풀이 과정

1. 행이 10만개나 가능하므로 탐색문제로 해결하면 시간초과

2. 따라서 dp를 활용하여 문제를 해결함.

3. i행 j열의 경우, 이전 행에서 j열을 제외한 나머지 열중 최댓값 + i행 j열의 값으로 대체

import copy
def solution(land):
    dp = copy.deepcopy(land)

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

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

출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges

풀이 과정

1. 시간을 분단위로 변환 / 정규 표현식 활용하여 악보를 요소 하나하나씩 담긴 리스트로 변환

2. 정렬(분단위로 변환하였으니 종료시간 - 시작시간으로 내림차순, 시작시간으로 오름차순)

3. m도 정규 표현식 활용하여 리스트 변환 / 순차적으로 접근하면서 비교

import re
def solution(m, musicinfos):
    answer = ''

    infos = []

    # 시간 분단위로 변환 
    for musicinfo in musicinfos:
        info = musicinfo.split(',')
        stmin = 60 * int(info[0][0:2]) + int(info[0][3:5])
        fimin = 60 * int(info[1][0:2]) + int(info[1][3:5])
        title = re.findall('A#|C#|D#|F#|G#|[A|B|G|F|E|D|C]', info[3])
        it = (fimin - stmin) // len(title)
        k = (fimin - stmin) % len(title)
        infos.append([stmin, fimin, info[2], title * it + title[:k]])

    # 재생시간, 시작시간 순 정렬
    infos.sort(key=lambda x:(-(x[1]-x[0]), x[0]))
    m = re.findall('A#|C#|D#|F#|G#|[A|B|G|F|E|D|C]', m)
    length = len(m)

    # 문자열 비교 파트
    for i in range(len(infos)):
        for j in range(len(infos[i][3]) - length + 1):
            count = 0
            for k in range(len(m)):
                if m[k] == infos[i][3][j+k]:
                    count += 1

            if count == length:
                answer = infos[i][2]
                break

        if answer != '':
            break


    if answer == '':
        answer = '(None)'

    return answer

출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges

풀이 방법

1. recursion을 사용하게 되면 n이 100000 이하이므로 불가능

2. 따라서 a, b, c를 두어, c는 a+b, a는 b, b는 c 이런식으로 진행하여 계산량 최소화

3. 마지막에 1234567로 나눈 나머지 수를 리턴해주면 된다.

def solution(n):
    answer = 0
    a = 0
    b = 1
    c = 1
    if n == 1:
        return 1

    for i in range(2, n+1):
        c = a + b
        a = b
        b = c

    answer = c % 1234567
    return answer

출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges

풀이 과정

1. 최대 길이가 -55이므로.. 현재 위치를 (5,5)로 두고 010으로 제한한다.

2. 방문 체크를 위해 set을 사용. set에는 리스트를 넣을수 없어서 Tuple로 변환하여 set에 넣어준다.

=> (현재x, 현재y, 이동x, 이동y)

=> (이동x, 이동y, 현재x, 현재y)

* 처음 걸어본 길의 길이이므로 이동한 길을 통해 반대에서 이곳으로 돌아오는 케이스도 있기 때문에 두가지 케이스를 넣어준다.

3. 길이 막혀있는지, 막혀있지 않다면 방문한 길인지를 체크하면서 처음 걸어본 길의 길이를 1씩 증가시킨다.

def solution(dirs):
    answer = 0

    path = set()
    pos = [5, 5]
    for d in dirs:
        if d == 'U' and pos[0] > 0:
            if tuple([pos[0], pos[1], pos[0]-1, pos[1]]) not in path:
                path.add(tuple([pos[0], pos[1], pos[0]-1, pos[1]]))
                path.add(tuple([pos[0]-1, pos[1], pos[0], pos[1]]))
                answer += 1
            pos[0] -= 1
        elif d == 'L' and pos[1] > 0:
            if tuple([pos[0], pos[1], pos[0], pos[1]-1]) not in path:
                path.add(tuple([pos[0], pos[1], pos[0], pos[1]-1]))
                path.add(tuple([pos[0], pos[1]-1, pos[0], pos[1]]))
                answer += 1
            pos[1] -= 1
        elif d == 'R' and pos[1] < 10:
            if tuple([pos[0], pos[1], pos[0], pos[1]+1]) not in path:
                path.add(tuple([pos[0], pos[1], pos[0], pos[1]+1]))
                path.add(tuple([pos[0], pos[1]+1, pos[0], pos[1]]))
                answer += 1
            pos[1] += 1
        elif d == 'D' and pos[0] < 10: 
            if tuple([pos[0], pos[1], pos[0]+1, pos[1]]) not in path:
                path.add(tuple([pos[0], pos[1], pos[0]+1, pos[1]]))
                path.add(tuple([pos[0]+1, pos[1], pos[0], pos[1]]))
                answer += 1
            pos[0] += 1
    return answer

출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges

풀이 과정

1. 현재 검사하려는 영역을 검사한다.

2. 현재 검사하려는 영역이 압축이 되지 않는다면 영역을 왼쪽위, 왼쪽아래, 오른쪽아래, 오른쪽 위로 4개 분할하여 재귀함수를 호출한다.

3. 영역의 크기가 1x1인 경우에는 하나의 영역으로 간주하고 종료

4. 영역이 압축이 된다면 무슨 영역인지 카운팅 해주고 종료

import sys

count = [0, 0]

sys.setrecursionlimit(10**6)

def check(arr, x1, y1, x2, y2):
    t = arr[x1][y1]
    for i in range(x1, x2+1):
        for j in range(y1, y2+1):
            if arr[i][j] != t:
                return False

    return True

def f(arr, x1, y1, x2, y2):
    if check(arr, x1, y1, x2, y2):
        t1 = arr[x1][y1]
        count[t1] += 1
        return

    if x1 == x2 and y1 == y2:
        count[arr[x1][y1]] += 1
        return

    midX = (x1 + x2) // 2
    midY = (y1 + y2) // 2

    f(arr, x1, y1, midX, midY) # 왼위
    f(arr, midX+1, y1, x2, midY) # 왼아
    f(arr, midX+1, midY+1, x2, y2) # 오아
    f(arr, x1, midY+1, midX, y2) # 오위

def solution(arr):
    answer = []
    t = len(arr)
    f(arr, 0, 0, t-1, t-1)
    return count

출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges

풀이 과정

1. 각각의 케이스마다 선행 스킬 순서(skill)을 queue로 만들어 준다.

2. 각 스킬트리를 문자 순서대로 진행하면서 해당 문자가 선행 스킬 순서 내에 있는지, 있다면 queue의 맨 앞에 있는지를 검사한다.

3. queue의 맨 앞에 없다면, 먼저 나와야 하는 스킬이 아니므로 잘못된 것이므로 break

4. queue의 맨 앞에 있다면, 먼저 나와야 하는 스킬이 맞으므로 queue에서 빼준 다음 다음 문자에 대해 계속 진행한다.

5. 만족하는 스킬 트리의 개수를 리턴하면 된다.

from collections import deque

def solution(skill, skill_trees):
    answer = 0
    for sk in skill_trees:
        queue = deque(skill)
        flag = True
        for s in sk:
            if s in queue:
                if queue[0] == s: # 선행스킬이면 큐에서 빼줌
                    queue.popleft()
                else: # 선행스킬이 아니라면 잘못된 것이므로 false
                    flag = False
                    break

        if flag:
            answer += 1

    return answer

출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges

풀이과정

1. 1의 개수를 카운트해준다. 이 때 0의 개수도 같이 카운팅

2. 1의 개수의 길이를 bin 함수를 사용하여 2진수 형태로 변환

3. 해당 결과값이 1일때까지 반복.

4. 몇번 진행하였는지, 몇개의 0을 제거하였는지 리턴

def convert(s):
    return bin(s)[2:]

def solution(s):
    answer = []
    zero = 0
    step = 0
    while True:
        temp = []
        for n in s:
            if n == '0':
                zero += 1
            else:
                temp.append(n)

        t = convert(len(temp))
        step += 1
        s = t
        if s == '1':
            break

    answer = [step, zero]
    return answer

출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges

풀이과정

1. cache를 deque로 구현

2. 대/소문자 구분을 하지 않는다고 하였으므로 lower() 함수를 사용하여 소문자로 변환

3. 캐시 히트일 경우 해당 요소를 deque에서 지워주고 deque의 맨 뒤에 넣어 줌 (위치 이동)

4. 캐시 미스일 경우 해당 요소를 deque에 넣어줌과 동시에 deque의 크기가 넘친다면 deque의 가장 왼쪽 요소(가장 사용이 되지 않은 요소)를 지워준다.

5. 전체 비용을 계산하면 완료

소스 코드

from collections import deque

def solution(cacheSize, cities):
    answer = 0

    deq = deque()

    for city in cities:
        city = city.lower()
        if city in deq:
            answer += 1
            deq.remove(city)
            deq.append(city)
        else:
            answer += 5
            deq.append(city)
            # 캐시 초과 시 가장 사용이 되지 않은 캐시 빼줌
            if len(deq) > cacheSize: 
                deq.popleft()

    return answer

출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges

- 최대한 2를 많이 곱하는것이 좋으므로 .. 나누어 떨어지지 않을 때만 1 빼준다.

- 나누어 떨어진다면 2로 나누어 준다.

- 1 빼줄때는 이동하는 경우로 따로 카운팅 해준 다음에 리턴

from collections import deque

def solution(n):
    count = 0
    while True:
        if n % 2 == 1:
            n = n - 1
            count += 1
        else:
            n = n // 2

        if n == 0:
            break

    return count

출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges

- 현 시점의 가격과 스택에 저장된 가격들을 하나씩 비교하면서 현 시점의 가격이 작다면 pop 하는 방식으로 구현

- 미리 answer을 prices의 길이만큼 만들어 둔 후, 현 시점의 가격보다 스택의 값이 크다면 pop 해준다, 여기서 가격이 떨어지지 않는 기간은 현 시점의 인덱스 - 스택에 저장된 인덱스이다.

- 전체 가격을 돈 다음에는 stack에 남아있는 값들에 대한 처리를 해준다. 이때는 전체 크기 - 스택에 저장된 인덱스 - 1로 처리해주는데, 그 이유는 인덱스가 0부터 시작하기도 하고, 마지막 값은 0이 되어야 하기 때문이다.

from collections import deque

def solution(prices):
    answer = [0] * len(prices)
    stack = deque()

    for idx in range(len(prices)):
        while stack:
            if prices[stack[-1]] > prices[idx]:
                i = stack.pop()
                answer[i] = idx - i
            else:
                break

        stack.append(idx)

    while stack:
        i = stack.pop()
        answer[i] = len(prices) - i - 1

    return answer

출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges