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

- 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

- 각각의 회전 케이스에 대해서 스택으로 괄호 검사를 하면 된다.

- {, [, (를 만나면 스택에 넣어주고, }, ], )를 만나면 스택에서 빼주면 되는데, 넣을때는 그냥 넣으면 되지만 뺄때는 스택이 비어 있는지, 뺀 괄호가 }, ], )에 매칭이 되는지를 검사해야 한다.

- for문을 빠져 나오고 나서는 괄호가 비어 있는지 확인해야 함. '{{{{{{' 같은 경우는 넣기만 하고 빠져나올 수 있음.

- 조건을 만족하는 모든 개수를 구하면 된다.

from collections import deque

def check(s):
    st = deque()
    for t in s:
        if t in ['[', '(', '{']:
            st.append(t)
        else:
            if len(st) == 0:
                return False
            temp = st.pop()
            if (temp == '[' and t == ']') or (temp == '(' and t == ')') or (temp == '{' and t == '}'):
                continue
            return False
    if st: # 스택에 차있으면 False임! 이거 처리 안해서 13번 통과 못했었음.
        return False

    return True

def solution(s):
    answer = 0
    for i in range(len(s)):
        temp = s[i:] + s[:i] # 회전
        if check(temp):
            answer += 1
    return answer

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

- Floyd 알고리즘을 적용하여 모든 정점에서 다른 정점에 도달하는 최소 거리를 구해준다.(최대 50개의 마을까지이므로, 더 늘어나면 dijkstra 알고리즘 적용)

- 이후 distance[1]을 조사하여 1번 마을에서 K 거리 이내의 마을들의 개수를 출력해주면 된다.

import copy
def solution(N, road, K):
    INT_MAX = 9999999999
    matrix = [[INT_MAX] * (N+1) for _ in range(N+1)]
    for a, b, c in road:
        if matrix[a][b] > c:
            matrix[a][b] = c
            matrix[b][a] = c

    distance = copy.deepcopy(matrix) 

    for i in range(1, N+1):
        distance[i][i] = 0

    # floyd Algorithm
    for i in range(1, N+1):
        for j in range(1, N+1):
            for k in range(1, N+1):
                distance[j][k] = min(distance[j][k], distance[j][i] + distance[i][k])


    # 1에서 도달 가능한 개수 출력
    answer = len(list(filter(lambda x:x<=K, distance[1])))

    return answer

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

- 정렬 문제인데 정렬로 하면 좀 복잡해지는거 같아서 이진 탐색으로 구현함.

- 최대 나올수있는 결과값을 citations의 최댓값으로 잡아두고, 절반씩 나눠가면서 h값의 조건과 맞는지 조사하고, 조건이 맞다면 결과를 저장해 둔 뒤 오른쪽 구간을 검사

- 조건이 맞지 않다면 왼쪽 구간을 검사한다.

def solution(citations):
    answer = 0
    visited = set()
    left = 0
    right = max(citations)

    while left <= right:
        temp = (left + right) // 2
        larger = 0

        for c in citations:
            larger = larger + 1 if c >= temp else larger

        if len(citations) - larger <= temp and temp <= larger:
            answer = temp
            left = temp + 1
        else:
            right = temp - 1

    return answer

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