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

풀이 과정

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

- 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