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

풀이과정

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

- board의 2x2 블록을 검사하여 삭제 가능하면 포지션 저장(바로 삭제하면 중첩되는 경우 문제)

- 포지션에 따라 2x2 블록 삭제('-'로 치환)

- 열 기준으로 '-' 요소들 붙여줌 (6 6 - - 2 2) -> (- - 6 6 2 2)

'-' 요소 붙여줄 때, -가 아닌 요소들만 순차적으로 리스트에 저장해준 다음, 모자란 개수만큼 - 채워주는 방식으로 구현, 현재 방식은 columns에 열 기준으로 - 제거하여 저장 후 다시 board에 저장하였는데.. 처음부터 board를 행-열 회전시킨 후 진행하였으면 훨씬 수월하였을 것 같음. 

from collections import deque

def check(board, m, n):
    dx = [0, 0, 1, 1]
    dy = [0, 1, 0, 1]
    ch = board[m][n]
    count = 0
    for i in range(4):
        x = m + dx[i]
        y = n + dy[i]
        if x >= 0 and x <= len(board)-1 and y >= 0 and y <= len(board[0])-1:
            if board[x][y] == ch:
                count += 1
    
    if count == 4:
        return True
    return False

def remove(board, m, n):
    dx = [0, 0, 1, 1]
    dy = [0, 1, 0, 1]
    for i in range(4):
        board[m+dx[i]][n+dy[i]] = '-'
    
def solution(m, n, board):
    board = [list(b) for b in board]
    answer = 0
    
    while True:
        currect = []
        # 2x2 검사
        for i in range(m):
            for j in range(n):
                if board[i][j] == '-':
                    continue
                if check(board, i, j):
                    currect.append([i, j])

        if len(currect) == 0:
            # -의 개수 구해줌
            for b in board: 
                answer += b.count('-')
            break
            
        # 검사결과 제거
        for cur in currect:
            remove(board, cur[0], cur[1])

        # - 붙여주는 과정
        columns = [[] for _ in range(n)]
        for j in range(n):
            for i in range(m):
                if board[i][j] != '-':
                    columns[j].append(board[i][j])
            if len(columns[j]) < m:
                columns[j] = ['-'] * (m - len(columns[j])) + columns[j] # 길이 '-' 붙여서 맞추어줌
        

        # - 제거한걸 원래 board에 적용
        for i in range(m):
            for j in range(n):
                board[i][j] = columns[j][i]
                
    return answer

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

- set을 활용하여 이전에 누가 말한 단어인지 검사

- 현재 단어의 이전 단어를 저장해 두고 현재 단어의 처음 알파벳과 이전 단어의 마지막 알파벳을 비교

- 순서는 (i % n) + 1번째 사람이 (i // n) + 1번째 순서에서 탈락한 것이다.

- 모두 정상적으로 끝마친 경우는 [0, 0] 리턴

def solution(n, words):
    word_said = set()

    answer = []

    last = ''
    for i, word in enumerate(words):
        if word in word_said or (len(last) != 0 and last[-1] != word[0]):
            answer = [(i%n)+1, (i//n)+1]
            break
        word_said.add(word)
        last = word

    if len(answer) == 0:
        answer = [0, 0]

    return answer

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

- 처음에는 오름차순으로 정렬해서 순차적 비교로 하려 했으나 실패

- 따라서, 현재 리스트를 오름차순으로 정렬하여 deque로 만든 후, 왼쪽, 오른쪽에서 하나씩 빼면서 비교 (최소, 최대)

- 현재 deque에서의 최소 요소 + 현재 deque에서의 최대 요소가 limit보다 작다면 두개를 동시 pop

- 현재 deque에서의 최소 요소 + 현재 deque에서의 최대 요소가 limit보다 크다면 최대 요소만 pop

- 최소 요소밖에 없는 경우에는 최소 요소 pop

- 각각의 pop 과정마다 answer을 1씩 증가시켜 주면 된다.

from collections import deque
def solution(people, limit):
    answer = 0
    people.sort()
    deq = deque(people)
    sumation = 0
    while deq:
        left = deq.popleft() # 남아있는 사람 중 최소 무게 한명 뺌
        right = 0

        while deq: # 최대 무게에서 순차적으로 내려가면서 최소 + 최대가 limit보다 작은 경우까지 반복
            right = deq.pop()
            if left + right <= limit:
                break
            else:
                answer += 1    

        answer += 1


    return answer

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

- 시간을 1초씩 증가시키면서 매순간 큐에서 나가야하는 트럭은 빼주고, 트럭이 들어올 수 있으면 큐에 넣어주는 작업을 반복하면 된다.

- 종료조건은 모든 트럭을 큐에 넣었으며, 큐가 비어있는 경우에만(다리를 모두 건넜을 때만) 종료하도록 함.

from collections import deque

def solution(bridge_length, weight, truck_weights):
    answer = 0
    idx = 0
    cur_weight = 0
    time = 0
    queue = deque()
    while True:
        if queue and queue[0][1] <= time:
            cur_weight = cur_weight - queue[0][0]
            queue.popleft()

        if idx < len(truck_weights) and weight >= cur_weight + truck_weights[idx]: 
            queue.append([truck_weights[idx], time+bridge_length])
            cur_weight = cur_weight + truck_weights[idx]
            idx += 1

        time += 1
        if idx == len(truck_weights) and not queue:
            break

    answer = time
    return answer

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

- 처음엔 그냥 bfs로 하려고 하였으나 시간초과 문제로 인해 실패.

- 다른 방식으로 고안 : 가로축으로 한칸씩 늘려가면 노란색 칸은 한칸, 갈색 칸은 두칸씩 증가한다.

- 세로축으로 이동한다면 노란색 칸은 현재 노란색 한줄만큼 늘고, 갈색 칸은 두칸씩 증가한다.

- 따라서, 현재 가로축 길이에서 세로축으로 늘렸을 때, 문제의 조건에 맞는지 검사해주면 된다.

- yellow % y == 0으로 세로로 늘렸을때 노란색 개수가 나누어 떨어지는지 확인하고, b + 2 * ( yellow // y - 1) == brown으로 노란색 개수가 yellow에 도달할 정도로 세로로 늘렸을 때, brown도 도달하는지 확인한다.

- 여기에 추가적으로 늘렸을때 가로축이 더 긴지 확인하면 된다. (cy >= cx + yellow // y - 1)

from collections import deque

def solution(brown, yellow):
    answer = []
    queue = deque([[3, 3, 8, 1]])
    loopcount = 0
    while queue:
        cx, cy, b, y,= queue.popleft()
        if b == brown and y == yellow:
            answer = [cy, cx]
            break
        if yellow % y == 0 and b + 2 * (yellow // y - 1) == brown:
            if cy >= cx + yellow // y - 1:
                answer = [cy, cx + yellow // y - 1]
                break
        queue.append([cx, cy+1, b+2, y+1]) # 오른쪽 이동


    return answer

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

- itertools의 combinations 썼다가 시간초과가 났는데 간단하게 풀 수 있었음.

- 그냥 옷을 입거나 입지 않는 경우가 있으므로 옷의 종류별로 모든 경우를 곱해준다.

- 마지막에 옷을 입지 않는 경우를 -1 해주면 된다.

def solution(clothes):
    answer = 1
    clo = {}
    for cloth, types in clothes:
        if clo.get(types) == None: 
            clo[types] = 0
        clo[types] += 1

    p = clo.values()
    for i in p:
        answer *= (i+1)

    return answer - 1

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

- 처음에는 그냥 구간 나누어서 구간의 최댓값으로 맨 앞자리부터 채우는 방식으로 구현하였음.

- 10번에서 무한정 시간초과가 나서 잘 안되어서 다른 방식으로 구현.

- 다음은 잘 안됬던 소스

def get_max(number, src, dest):
    num = number[src]
    idx = src
    for i in range(src, dest):
        if num < number[i]:
            num = number[i]
            idx = i
        if number[i] == 9:
            break
    
    return (num, idx+1)

def solution(number, k):
    length = len(number)
    nex = 0
    c = length-k
    answer = ''
    
    while True:
        m, nex = get_max(number,nex,length-c+1)
        answer += m
        if len(answer) == length-k:
            break
        c = c - 1
        
    return answer
    from collections import deque

- 개수가 최대 100만개라 그런거 같았음. 따라서 풀이 방식을 스택으로 그리디하게 구현

- 매 순간 스택에 넣을때 스택 맨 위 요소가 넣으려는 요소보다 작다면 계속 빼주다가 맨 위 요소가 더 커지면 그때 넣어줌, 단 빼줄 때 몇개 빼주었는지 카운팅 해주어야 함. 최대 k개 빼야 하므로.

- 번외로 k개를 빼지 못하였다면 마지막에 맨 뒤에서 k개 빼줌

def solution(number, k):
    stack = deque()
    delcnt = 0
    for i, n in enumerate(number):
        while stack and delcnt != k:
            if stack[-1] < n:
                delcnt += 1
                stack.pop()
            else:
                break
        stack.append(n)
    
    answer = "".join(stack)
    if delcnt < k: # 충분히 지우지 못한 경우 뒤에서부터 지워줌.
        answer = answer[:-(k-delcnt)]
        
    return answer

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