프로그래머스 Level2 문제 모음[Python]

- https://school.programmers.co.kr/learn/courses/30/lessons/60058

- 키워드 : stack

- 레벨 : 2

from collections import Counter 

def is_correct(u):
    # 올바른 괄호 문자열 판단
    stack = []
    for i in u:
        if i == "(":
            stack.append(i)
        else:
            if not stack:
                return False
            x = stack.pop()
    return True

def solution(p):
    # 빈 문자열인 경우
    if not p:
        return ""
    
    # 이미 올바른 괄호 문자열일 경우
    if is_correct(p):
        return p
    
    u = ""
    v = ""
    # 2. 균형잡힌 괄호 문자열 u, v로 분리
    for i in range(2, len(p)+1):
        u = p[:i]
        v = p[i:]
        temp = Counter(u)
        if temp["("] == temp[")"]:
            break

    # 올바른 괄호 문자열일 경우
    if is_correct(u):
        # 3-1 v에 대해 같은 과정 수행 후, 수행한 결과 u에 이어 붙이고
        u += solution(v)
        return u
    # 4. 아닐 경우
    else:
        # 4-1 ~ 4-3
        temp = "(" + solution(v) + ")"
        # 4-4
        temp_u = u
        temp_u = temp_u[1:(len(temp_u)-1)]
        temp2 = ""
        for i in temp_u:
            if i == "(":
                temp2 += ")"
            else:
                temp2 += "("
        temp += temp2
        return temp

 

 

 

- https://school.programmers.co.kr/learn/courses/30/lessons/161989

- 키워드 : queue, index

- 레벨 : 2

def solution(n, m, section):
    count = 0
    while section:
        # m이 1일때를 위해 -1로 세팅
        idx = -1
        count += 1
        num = section.pop(0)
        if m == 1:
            section = section[idx+1:]
        else:
            for j in range(num + m - 1, num - 1, -1):
                if j in section:
                    idx = section.index(j)
                    break
        section = section[idx+1:]
    
    return count

 

- https://school.programmers.co.kr/learn/courses/30/lessons/72411

- 키워드 : dictionary, combinations, Counter, sort, join

- 레벨 : 2

from itertools import combinations
from collections import Counter 
def solution(orders, course):
    answer = []
    for i in course:
        counters = {}
        # course 개수별 Counter 세기
        for order in orders:
            # XW와 WX를 동일하게 하기 위해 str 사전순 정렬
            order = ''.join(sorted(list(order)))
            # combination 결과 join으로 묶고
            result = list(map(''.join, combinations(order, i)))
            # 딕셔너리화
            result = dict(Counter(result).items())
            # 모든 order에 대하 하나로 합치기
            for key, _ in result.items():
                if key in counters:
                    counters[key] += 1
                else:
                    counters[key] = 1
        
        # course별 max 값가진 keys 찾기, 0이면 스킵
        if len(counters) == 0:
            continue
        max_value = max(counters.values())
        # 최소 value값이 2이상이어야 함
        if max_value < 2:
            continue
        max_keys = [key for key, value in counters.items() if value == max_value]
        answer.extend(max_keys)
    # 사전순 정렬
    answer.sort()
    
    return answer

 

- https://school.programmers.co.kr/learn/courses/30/lessons/68645

- 키워드 : 경우의 수

- 레벨 : 2

def solution(n):
    arr = [[0 for _ in range(n)] for _ in range(n)]
    cur_num = 0
    y, x = (-1, 0)

    for i in range(n, 0, -3):
        # 아래로
        for j in range(0, i):
            y += 1
            cur_num += 1
            arr[y][x] = cur_num
        # 오른쪽으로
        for j in range(0, i-1):
            x += 1
            cur_num += 1    
            arr[y][x] = cur_num
        # 왼쪽위로
        for j in range(0, i-2):
            x -= 1
            y -= 1
            cur_num += 1  
            arr[y][x] = cur_num
    # 2차원 -> 1차원
    arr = sum(arr, [])
    arr2 = []
    for i in arr:
        if i != 0:
            arr2.append(i)
    
    return arr2

 

- https://school.programmers.co.kr/learn/courses/30/lessons/42883

- 키워드 : stack

- 레벨 : 2 (다시보기)

def solution(number, k):
    answer = []
    
    for num in number:
        while k > 0 and answer and answer[-1] < num:
            answer.pop()
            k -= 1
        answer.append(num)

    return ''.join(answer[:len(number)-k])

좋은 풀이와 설명 : https://gurumee92.tistory.com/162

 

 

- https://school.programmers.co.kr/learn/courses/30/lessons/12899

- 키워드 : 진수

- 레벨 : 2 

def solution(n):
    answer = ''
    while n > 0:
        n, mod = divmod(n-1, 3) # 0부터 시작하는 것이 아니라 1부터 시작하도록 n-1 해줌
        answer = '124'[mod] + answer
    return answer

 

- https://school.programmers.co.kr/learn/courses/30/lessons/68936

- 키워드 : 쿼드트리(quad tree), list

- 레벨 : 2 

count_zero = 0
count_one = 0

def quad_tree(arr, l):
    global count_zero
    global count_one
    if l == 1:
        if arr[0][0] == 1:
            count_one += 1
            return
        else :
            count_zero += 1
            return
            
    temp = sum(list(map(sum, arr)))
    if temp == l**2:
        count_one += 1
        return
    elif temp == 0:
        count_zero += 1
        return
    else:
        # 1 2
        # 3 4
        half_l = int(l/2)
        arr1 = [arr[i][:half_l] for i in range(0, half_l)]
        arr2 = [arr[i][half_l:] for i in range(0, half_l)]
        arr3 = [arr[i][:half_l] for i in range(half_l, l)]
        arr4 = [arr[i][half_l:] for i in range(half_l, l)]
        quad_tree(arr1, half_l)
        quad_tree(arr2, half_l)
        quad_tree(arr3, half_l)
        quad_tree(arr4, half_l)
    
def solution(arr):
    global count_zero, count_one
    l = len(arr)
    quad_tree(arr, l)
    return [count_zero, count_one]

 

- https://school.programmers.co.kr/learn/courses/30/lessons/12905

- 키워드 : DP

- 레벨 : 2 (다시보기)

import copy
def solution(board):
    # dp[i][j]가 현재 위치에서 가질 수 있는 가장 긴 변의 길이라고 정의
    dp = copy.deepcopy(board)
    length = 0
    # y가 1일 경우
    if len(dp) == 1:
        for i in range(len(dp[0])):
            if dp[0][i] == 1:
                return 1
        return length
    # x가 1일 경우
    if len(dp[0]) == 1:
        for i in range(len(dp)):
            if dp[i][0] == 1:
                return 1
        return length
    # x, y > 1
    for i in range(1, len(dp)):
        for j in range(1, len(dp[0])):
            if dp[i][j] == 1:
                dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1
            length = max(length, dp[i][j])
               
    return length**2

 

- https://school.programmers.co.kr/learn/courses/30/lessons/42839

- 키워드 : map, 순열(permutations) 소수(prime)

- 레벨 : 2 (다시보기)

import math
from itertools import permutations

def isPrime(n):
    if n < 2:
        return False
    else:
        for i in range(2, int(math.sqrt(n)) + 1):
            if n % i == 0:
                return False
        return True
    
def solution(numbers):
    per_list = []
    count = 0
    # 모든 경우의 수 concate
    for i in range(1, len(numbers)+1):
        per_list.extend(list(map(int ,list(map(''.join,list(permutations(numbers, i)))))))
    # 중복 제거
    per_list = list(set(per_list))
    for i in per_list:
        if isPrime(i):
            count += 1
        
    return count

# 참고 소수 최적화
import math

def is_prime(n):
    if n <= 1:
        return False

    # 2는 유일한 짝수 소수이므로 따로 처리합니다.
    if n == 2:
        return True

    # n이 짝수인 경우는 소수가 아닙니다.
    if n % 2 == 0:
        return False

    # 3부터 n의 제곱근까지의 홀수로 나누어보면서 소수 여부를 확인합니다.
    sqrt_n = math.isqrt(n)
    for i in range(3, sqrt_n + 1, 2):
        if n % i == 0:
            return False

    return True

 

 

 

 

- https://school.programmers.co.kr/learn/courses/30/lessons/42746

- 키워드 : lambda

- 레벨 : 2 (다시보기)

def solution(numbers):
    numbers = list(map(str, numbers))
    # 3자리수로 맞춘뒤 비교
    numbers.sort(key = lambda x : x*3, reverse = True)
    # 모든 값이 0일 때를 위해 int로 변환 후 다시 str 변환
    return str(int(''.join(numbers)))

 

- https://school.programmers.co.kr/learn/courses/30/lessons/77885

- 키워드 : 시간초과, 규칙찾기

- 레벨 : 2 

# XOR로 하나씩 비트 비교하면 시간초과 됨
import math
def solution(numbers):
    result = []
    for i in numbers:
        temp = bin(i)
        # 가장 아래 비트부터 1이 나오지 않을 때까지의 길이
        # 0 => 1, 1 => 1, 11 => 2, 111 => 4
        tail_one_count = 0
        for j in range(len(temp)-1, -1, -1):
            if temp[j] != "1":
                break
            tail_one_count += 1

        if tail_one_count == 0:
            result.append(i+1)
        else:
            result.append(i + math.pow(2, tail_one_count - 1))
              
    return result

 

- https://school.programmers.co.kr/learn/courses/30/lessons/131127

- 키워드 : Counter

- 레벨 : 2 

from collections import Counter

def solution(want, number, discount):
    want_counter = Counter()
    for i in range(len(want)):
        want_counter[want[i]] = number[i]
        
    count = 0
    length = len(discount) - 10 + 1
    for i in range(length):
        discount_counter = Counter(discount[i:i+10])
        if want_counter == discount_counter:
            count += 1
          
    return count

 

- https://school.programmers.co.kr/learn/courses/30/lessons/49993

- 키워드 : dic

- 레벨 : 2 

def solution(skill, skill_trees):
    count = len(skill_trees) 
    skill_level_dic = {}
    level = 1
    for i in skill:
        skill_level_dic[i] = level
        level += 1
    
    temp_list = []
    for i in skill_trees:
        temp = ""
        for j in i:
            if j in skill:
                temp += j
        temp_list.append(temp)
     
    for i in temp_list:
        level = 1
        for j in i:
            if skill_level_dic[j] != level:
                count -= 1
                break
            level += 1
                     
    return count

 

- https://school.programmers.co.kr/learn/courses/30/lessons/12913

- 키워드 : DP

- 레벨 : 2 

def solution(land):
    a,b,c,d = land[0]
    
    for i in range(1, len(land)):
        # (temp1은 이전에 두번째, 다음에 첫번째 선택 / 이전에 세번째, 다음에 첫번째 선택 / 이전에 네번째, 다음에 첫번째 선택 중 max)
        temp1 = max(land[i][0] + b, land[i][0] + c, land[i][0] + d)
        temp2 = max(land[i][1] + a, land[i][1] + c, land[i][1] + d)
        temp3 = max(land[i][2] + a, land[i][2] + b, land[i][2] + d)
        temp4 = max(land[i][3] + a, land[i][3] + b, land[i][3] + c)
        a = temp1
        b = temp2
        c = temp3
        d = temp4

    return max(a,b,c,d)

 

- https://school.programmers.co.kr/learn/courses/30/lessons/17679#

- 키워드 : 탐색

- 레벨 : 2 

import copy

count = 0
end_flag = False

def make_clear_board(m, n, board):
    # !리스트는 객체이므로 반드시 copy()를 통해 다른 변수 할당
    # 이차원이므로 copy.deepcopy() 사용
    clear_board = copy.deepcopy(board)
    for y in range(m):
        for x in range(n):
            if y+1 < m and x+1 < n:
                kind_of_block = board[y][x]
                if ("A" <= kind_of_block <= "Z" and
                    kind_of_block == board[y][x+1] and
                    kind_of_block == board[y+1][x+1] and
                    kind_of_block == board[y+1][x]):
                    clear_board[y][x] = "!"
                    clear_board[y][x+1] = "!"
                    clear_board[y+1][x+1] = "!"
                    clear_board[y+1][x] = "!"
    return clear_board
        
def count_and_pulldown_board(m, n, board):
    global count
    global end_flag
    count_o = 0
    for i in range(m):
        for j in range(n):
            if board[i][j] == "!":
                count_o += 1
                board[i][j] = "@"
    # "!"가 없으면 end_flag 활성화
    if count_o == 0:
        end_flag = True
    else:
        count += count_o
    
    for i in range(m-2, -1, -1):
        for j in range(n-1, -1, -1):
            if board[i][j] == "@":
                continue
            down = 0
            k = m - 1
            while k > i:
                if board[k][j] == "@":
                    down += 1
                k -= 1
            if down != 0:
                board[i+down][j] = board[i][j]
                board[i][j] = "@"
    return board
    
def solution(m, n, board):
    # m: 세로, n: 가로
    # 1. bfs로 point 기준 오른쪽, 오른쪽아래, 아래를 검사하여 같으면 "!"로 치환
    # 2. "!" 갯수를 count한 후 @로 치환
    # 3. 위에 위치한 블럭을 아래로 당기기
    # 4. 1~3 반복, 만약 1~2 과정에서 한 개도 "!"로 치환이 된 블럭이 없다면 종료
    
    # 새 보드 만들기
    new_board = [["a" for _ in range(n)] for _ in range(m)]
    for i in range(m):
        for j in range(n):
            new_board[i][j] = board[i][j]
    global count
    global end_flag
    while not end_flag:
        o_board = make_clear_board(m, n, new_board)
        new_board = count_and_pulldown_board(m, n, o_board)

    return count

 

- https://school.programmers.co.kr/learn/courses/30/lessons/12900#

- 키워드 : dp

- 레벨 : 2 

def solution(n):
    if n == 1:
        return 1
    if n == 2:
        return 2
    a = 1
    b = 2
    for _ in range(3, n+1):
        temp_a = a
        temp_b = b
        a = temp_b
        b = temp_a + temp_b
    return b % 1000000007

 

- https://school.programmers.co.kr/learn/courses/30/lessons/17687

- 키워드 : string, ascii

- 레벨 : 2 

def solution(n, t, m, p):
    result = ""  
    result_len = m * t
    for i in range(result_len):
        if len(result) >= result_len:
            break
        temp = ""
        j = i
        while j >= n:
            if j % n >= 10:
                temp += chr(j % n + 55)
                print(temp)
            else:
                temp += str(j % n)
            j = int(j / n)
            
        if j >= 10:
            temp += chr(j % n + 55)
        else:
            temp += str(j)  
        temp = temp[::-1]
        result += temp
    
    answer = ""
    for i in range(t):
        answer += result[i * m + p - 1]
    
    return answer

 

- https://school.programmers.co.kr/learn/courses/30/lessons/42888

- 키워드 : dictionary(딕셔너리)

- 레벨 : 2 

def solution(record):
    dict = {}
    for i in record:
        if i.split(" ")[0] == "Enter" or i.split(" ")[0] == "Change":
            dict[i.split(" ")[1]] = i.split(" ")[2]
    
    answer = []
    for i in record:
        temp = ""
        if i.split(" ")[0] == "Enter":
            temp = dict[i.split(" ")[1]] + "님이 들어왔습니다."
            answer.append(temp)
        elif i.split(" ")[0] == "Leave":
            temp = dict[i.split(" ")[1]] + "님이 나갔습니다."
            answer.append(temp)
        
    return answer

 

- https://school.programmers.co.kr/learn/courses/30/lessons/92341

- 키워드 : dictionary(딕셔너리), sort

- 레벨 : 2 

import math
def solution(fees, records):
    dict = {}
    # 주차시간 계산
    for i in range(len(records)):
        temp = records[i].split(" ")
        if temp[1] not in dict:
            dict[temp[1]] = 0
        times = int(temp[0].split(":")[0])*60 + int(temp[0].split(":")[1])
        if temp[2] == "IN":
            dict[temp[1]] -= times
        else:
            dict[temp[1]] += times
    for key in dict.keys():     
        # 출차 안 한 경우 23:59 출차로 기록
        if dict[key] <= 0:
            dict[key] += 1439
    
    # key값으로 정렬
    sort_dict = sorted(dict.items())
    answer = []
    # 주차요금 계산
    for (key, val) in sort_dict:
        fee = fees[1]
        temp = math.ceil((val - fees[0])/fees[2]) * fees[3]
        if temp < 0:
            answer.append(fee)
        else:
            answer.append(fee + temp)
    
    return answer

 

- https://school.programmers.co.kr/learn/courses/30/lessons/138476

- 키워드 : counter, sort, lambda

- 레벨 : 2 

from collections import Counter
def solution(k, tangerine):
    temp = list(Counter(tangerine).items())
    # 귤의 개수가 많은 것 순으로 정렬
    temp.sort(key = lambda x : x[1], reverse = True)
    
    _sum = 0
    idx = 0
    while _sum < k:
        _sum += temp[idx][1]
        idx += 1

    return idx

 

- https://school.programmers.co.kr/learn/courses/30/lessons/131701

- 키워드 : set, 원형순열

- 레벨 : 2 

def solution(elements):
    length = len(elements)
    elements *= 2
    temp_list = []
    for i in range(length):
        for j in range(length):
            temp_list.append(sum(elements[j:j+i+1]))
            
    return len(set(temp_list))

 

- https://school.programmers.co.kr/learn/courses/30/lessons/17686

- 키워드 : sort, lambda, join

- 레벨 : 2 (다시보기)

def solution(files):
    result_list = []
    for i in files:
        head, number, tail = "", "", ""
        number_check= False
        for j in range(len(i)):
            # 숫자가 나오면
            if i[j].isdigit():
                number += i[j]
                number_check = True
            # 숫자 나오기 전
            elif not number_check:
                head += i[j]
            # 숫자나온 후 (tail)
            else:
                tail += i[j:]
                break
        result_list.append((head, number, tail))

    result_list.sort(key = lambda x : (x[0].upper(), int(x[1])))
    
    answer = []
    for i in result_list:
        answer.append(''.join(i))

    return answer

 

- https://school.programmers.co.kr/learn/courses/30/lessons/1844#

- 키워드 : bfs

- 레벨 : 2 (다시보기)

※ 배열의 크기가 클 때는 dfs보다 bfs로 풀자

# bfs
from collections import deque
def solution(maps):
    n = len(maps)
    m = len(maps[0])
    visited = [[False for _ in range(m)] for _ in range(n)]
    q = deque()
    dx = [-1, 1, 0, 0]
    dy = [0, 0, -1, 1]
    
    q.append((0, 0))
    visited[0][0] = True
    
    while q:
        y, x = q.popleft()
        for i in range(4):
            next_x = x + dx[i]
            next_y = y + dy[i]
            if 0<= next_x <m and 0 <= next_y < n and maps[next_y][next_x] == 1:
                if not visited[next_y][next_x]:
                    visited[next_y][next_x] = True
                    q.append((next_y, next_x))
                    maps[next_y][next_x] = maps[y][x]+1
                    
    if maps[n-1][m-1] == 1:
        return -1
    else:
        return maps[n-1][m-1]

 

- dfs로는 답은 맞았지만 효율성 테스트 실패

# dfs
result_list = []
_dir = [[0, 1], [0, -1], [-1, 0], [1, 0]]

def dfs(y, x, maps, visited, count):
    global result_list
    if (y, x) == (len(maps)-1, len(maps[0])-1):
        result_list.append(count)
        return
    for i in _dir:
        next_y = y + i[1]
        next_x = x + i[0] 
        # 맵 범위 안에 있어야 함
        if 0 <= next_x < len(maps[0]) and 0 <= next_y < len(maps):
            # 막힌 길이 아니어야 함
            if maps[next_y][next_x] == 1:
                # 방문하지 않아야 함
                if not visited[next_y][next_x]:
                    visited[next_y][next_x] = True
                    dfs(next_y, next_x, maps, visited, count + 1)
                    visited[next_y][next_x] = False
    return -1

def solution(maps):
    global result_list
    n = len(maps[0])
    m = len(maps)
    visited = [[False for _ in range(n)] for _ in range(m)]
    dfs(0, 0, maps, visited, 0)
    
    # 길이 없다면 -1
    if not result_list:
        return -1

    return min(result_list) + 1

 

- https://school.programmers.co.kr/learn/courses/30/lessons/42583

- 키워드 : queue

- 레벨 : 2

from collections import deque

def solution(bridge_length, weight, truck_weights):
    q_wait = deque(truck_weights)
    q_move = deque()
    pass_list = []
    time = 0
    weight_on_bridge = 0
    while len(truck_weights) != len(pass_list):
        if q_wait:
            # 무게 견딜 수 있으면
            if q_wait[0] + weight_on_bridge <= weight:   
                x = q_wait.popleft()
                # 대기 트럭과 다리 건너는 남은시간을 같이 추가
                q_move.append([x, bridge_length])
                # 현재 다리 적재 무게 추가
                weight_on_bridge += x
        # 1초 경과
        time += 1
        for i in range(len(q_move)):
            q_move[i][1] -= 1
            
        # 지나고 있는 트럭중 첫번째 검사
        if q_move:
            y, left_time = q_move[0]
            if left_time == 0:
                q_move.popleft()
                pass_list.append(y)
                weight_on_bridge -= y
        
    return time + 1

 

- https://school.programmers.co.kr/learn/courses/30/lessons/42626

- 키워드 : heap, 힙

- 레벨 : 2 (다시보기)

import heapq

def solution(scoville, K):
    count = 0
    heapq.heapify(scoville)
    while scoville[0] < K:
        # 힙이의 길이가 1이하인 경우
        # => 모든 음식의 스코빌 지수 K이상으로 만들 수 없음
        if len(scoville) <= 1:
            return -1  
        first = heapq.heappop(scoville)
        second = heapq.heappop(scoville)
        heapq.heappush(scoville, (first + second * 2))
        count += 1
    return count

 

- https://school.programmers.co.kr/learn/courses/30/lessons/49994

- 키워드 : 좌표, 경우의 수

- 레벨 : 2

def solution(dirs):
    length = 0
    coordinates = []
    current_x = 0
    current_y = 0
    next_x = 0
    next_y = 0
    for i in dirs:
        if i == "U":
            next_y = current_y + 1
        elif i == "D":
            next_y = current_y - 1
        elif i == "L":
            next_x = current_x - 1     
        elif i == "R":
            next_x = current_x + 1   
        if -5 <= next_x <= 5 and -5 <= next_y <= 5:
            if (current_x, current_y, next_x, next_y) not in coordinates:
                # !A -> B - > A의 경우도 고려
                coordinates.append((current_x, current_y, next_x, next_y))
                coordinates.append((next_x, next_y, current_x, current_y))
                length += 1
            current_x = next_x
            current_y = next_y
        else:
            next_x = current_x
            next_y = current_y              
    return length

 

- https://school.programmers.co.kr/learn/courses/30/lessons/84512

- 키워드 : dfs

- 레벨 : 2

dict_list = []

def dfs(x, words, depth):
    global dict_list
    if depth == len(words):
        return
    
    for i in range(len(words)):
        _x = x + words[i]
        dict_list.append(_x)
        dfs(_x, words, depth + 1)

def solution(word):
    global dict_list
    dfs("", "AEIOU", 0)
    # 사전식 정렬
    dict_list.sort()
    answer = dict_list.index(word)
    return answer+1

 

- https://school.programmers.co.kr/learn/courses/30/lessons/87946

- 키워드 : dfs, bfs

- 레벨 : 2 (다시보기)

 

// bfs

from collections import deque

def bfs(start, k, dungeons):
    queue = deque()
    queue.append([start, k, 0, [False for _ in range(len(dungeons))]])
    counted = []
    
    while queue:
        location, tired, count, visited = queue.popleft()
        visited[location] = True
        tired -= dungeons[location][1]
        count += 1
        counted.append(count)
        
        for i in range(len(dungeons)):
            if not visited[i] and tired >= dungeons[i][0]:
                queue.append([i, tired, count, visited[:]])
                
    return max(counted)

def solution(k, dungeons):
    answer = -1
    for i in range(len(dungeons)):
        if dungeons[i][0] <= k:
            answer = max(answer, bfs(i, k, dungeons))
    return answer

// dfs

answer = 0

def dfs(k, dungeons, depth, visited):
    global answer
    if depth > answer:
        answer = depth
    
    for i in range(len(dungeons)):
        if not visited[i] and k >= dungeons[i][0]:
            visited[i] = True
            dfs(k-dungeons[i][1], dungeons, depth+1, visited)
            # 모든 경우의 수 탐색을 위한 초기화
            visited[i] = False
        
def solution(k, dungeons):
    global answer
    visited = [False for _ in range(len(dungeons))]
    dfs(k, dungeons, 0, visited)
    return answer

ref) https://hoons-dev.tistory.com/48

 

 

 

- https://school.programmers.co.kr/learn/courses/30/lessons/17684

- 키워드 : LZW, list

- 레벨 : 2

# 1. 현재입력 검사 (1글자부터 ~n) 
# 2. 현재 인덱스 출력
# 3. 다음글자와 합쳐서 사전추가
from string import ascii_uppercase
def solution(msg):
    all_list = list(ascii_uppercase)
    answer_list = []
    # msg가 null일 때 까지
    while msg:
        # 현재 입력 정하기
        current_input = ""
        for i in range(len(msg)):
            if (current_input + msg[i]) in all_list:
                current_input += msg[i]
                continue
            else:
                break
        
        # 현재 입력 인덱스 정답리스트에 추가
        answer_list.append(all_list.index(current_input)+1)
        # 마지막 입력이면 break
        if len(msg) == len(current_input):
            break
        else: 
            # 현재 입력 + 다음 입력 사전에 추가
            all_list.append(current_input + msg[len(current_input)])        
            msg = msg[len(current_input):]

    return answer_list

 

- https://school.programmers.co.kr/learn/courses/30/lessons/92335

- 키워드 : 소수(prime), 진수

- 레벨 : 2

import math
def isPrime(num):
    if num == 1:
        return False
    else:
        for i in range(2, int(math.sqrt(num))+1):
            if num % i == 0:
                return False
        return True
    
def solution(n, k):
    temp_list = []
    rest = 0
    while n >= k:
        rest = n % k
        temp_list.append(rest)
        n //= k
    rest = n % k
    temp_list.append(rest)
    temp_list.reverse()
    temp_str = ""
    for i in temp_list:
        temp_str += str(i)
    count = 0
    for i in temp_str.split("0"):
        if not i:
            continue
        if isPrime(int(i)):
            count += 1
    return count

 

 

- https://school.programmers.co.kr/learn/courses/30/lessons/43165#

- 키워드 : dfs, bfs, 재귀(recursive)

- 레벨 : 2

count = 0
def dfs(numbers, target, cnt):
    global count
    if cnt == len(numbers):
        if sum(numbers) == target:
            count += 1
            return
    else: 
        dfs(numbers, target, cnt+1)
        numbers[cnt] *= -1
        dfs(numbers, target, cnt+1)
        return
    

def solution(numbers, target):
    global count
    dfs(numbers, target, 0)
    return count

★ 다른사람의 풀이

from itertools import product
def solution(numbers, target):
    # numbers가 [a1, b1, c1] 이면 [(a1, -a1), (b1, -b1), (c1, -c1)] 형태로 변환
    l = [(x, -x) for x in numbers]
    # product(*l)을 하면 각 요소들의 모든 경우에 수 생성 ex) (a1, b1, c1), (-a1, b1, c1), (a1, -b1, c1) ... 등 총 8개 생성
    s = list(map(sum, product(*l)))
    return s.count(target)

ref) https://school.programmers.co.kr/learn/courses/30/lessons/43165/solution_groups?language=python3

 

 

- https://school.programmers.co.kr/learn/courses/30/lessons/42577

- 키워드 : sort

- 레벨 : 2

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

 

- https://school.programmers.co.kr/learn/courses/30/lessons/17677

- 키워드 : Counter, Jaccard

- 레벨 : 2 (다시보기)

from collections import Counter
def solution(str1, str2):
    # 소문자로 변환
    str1 = str1.lower()
    str2 = str2.lower()
    list1 = []
    list2 = []
    # 2쌍씩 나누기
    for i in range(len(str1) - 1):
        temp = str1[i] + str1[i+1]
        if(temp.isalpha()):
            list1.append(temp)
    for i in range(len(str2) - 1):
        temp = str2[i] + str2[i+1]
        if(temp.isalpha()):
            list2.append(temp)
    # 중복 집합으로 만들기
    counter1 = Counter(list1)
    counter2 = Counter(list2)
    # element로 카운터 숫자만큼 item 리턴 후 list화
    intersection = list((counter1 & counter2).elements())
    union = list((counter1 | counter2).elements())
    if not union:
        return 65536
    else :
        j = len(intersection) / len(union)
        return int(j * 65536)

 

- https://school.programmers.co.kr/learn/courses/30/lessons/42587

- 키워드 : queue

- 레벨 : 2

def solution(priorities, location):
    queue = priorities
    printCount = 0
    while(queue):
        x = queue[0]
        if(x == max(queue)):
            location -= 1
            printCount += 1
        else:
            if(location == 0):
                location = len(queue) - 1
            else:
                location -= 1
            queue.append(x)
        queue.pop(0)
        if(location < 0):
            return printCount
    return -1

 

 

- https://school.programmers.co.kr/learn/courses/30/lessons/87390

- 키워드 : 시간초과, 배열(array)

- 레벨 : 2 (다시보기)

import math
def solution(n, left, right):
    # 1 ≤ n ≤ 10^7 => 시간초과 주의
    # arr[i][j] = max(i, j) + 1
    arr = []
    while(left <= right):
        i = math.floor(left / n)
        j = left % n
        left += 1
        arr.append(max(i, j) + 1)
    return arr

 

- https://school.programmers.co.kr/learn/courses/30/lessons/42586

- 키워드 : list, queue

- 레벨 : 2

def solution(progresses, speeds):
    answer = []
    queue = progresses
    # 큐가 빌 때 까지
    while(queue):
        for i in range(len(queue)):
            queue[i] += speeds[i]
        if(queue[0] >= 100):
            deployCount = 1
            for i in range(1, len(queue)):
                if(queue[i] >= 100):
                    deployCount += 1
                else:
                    break
            queue = queue[deployCount:]
            speeds = speeds[deployCount:]
            answer.append(deployCount)
    return answer

 

- https://school.programmers.co.kr/learn/courses/30/lessons/42578

- 키워드 : dictionary(딕셔너리), 경우의 수

- 레벨 : 2

def solution(clothes):
    kindOfClothDict = {}
    for i in clothes:
        # 현재 보고있는 옷 + 아무것도 고르지 않을 경우에 수 까지 합쳐서 초기값 2로 설정
        if(i[1] not in kindOfClothDict):
            kindOfClothDict[i[1]] = 2
        else:
            kindOfClothDict[i[1]] += 1
    
    answer = 1
    for i in kindOfClothDict:
        answer *= kindOfClothDict[i]
    # 아무것도 고르지 않는 경우 빼기
    return answer - 1

 

- https://school.programmers.co.kr/learn/courses/30/lessons/76502

- 키워드 : stack

- 레벨 : 2 (다시보기)

def check(str_list):
    stack = []

    for _str in str_list:
        if _str in ('[', '(', '{'):
            stack.append(_str)
        else:
            if not stack: return False
            x = stack.pop()
            if _str == ']' and x != '[':
                return False
            elif _str == ')' and x != '(':
                return False
            elif _str == '}' and x != '{':
                return False
    if stack: return False
    return True


def solution(s):
    cnt = 0
    for i in range(len(s)):
        u = s[:i]
        v = s[i:]

        if check(v+u):
            cnt +=1
    return cnt

 

- https://school.programmers.co.kr/learn/courses/30/lessons/64065

- 키워드 : sort, parsing, split

- 레벨 : 2

def solution(s):
    # 큰 괄호제거 및 길이를 맞추기 위한 "," 추가
    s = s[1:]
    s = s[:len(s)-1] + ","
    # 괄호 갯수 = 튜플 길이
    tupleLen = s.count("{")
    # 임의 배열 선언하여 각 부분 집합 넣기
    arr = ["0"] * tupleLen
    for i in range(tupleLen):
        # ex) arr = ['2', '2,1', '2,1,3', '2,1,3,4']
        arr[i] = (s.split("{")[i+1])[:-2]    
    # 길이 순으로 정렬
    arr.sort(key=len)

    answer = [int(arr[0])]
   
    # 해당 원소가 이미 있는지 확인 후 순서대로 넣음
    for i in range(1, tupleLen):
        for j in range(i+1):
            temp2 = int(arr[i].split(",")[j])
            if(temp2 not in answer):
                answer.append(temp2)
                break
                    
    return answer

 

 

- https://school.programmers.co.kr/learn/courses/30/lessons/42747

- 키워드 : h-index, sort

- 레벨 : 2

def solution(citations):
    h_index = 0
    citations.sort(reverse=True)
    for i in range(0, len(citations)):
        # i+1번이상 인용된 논문이 i+1개가 넘는다
        if citations[i] >= i+1:
            h_index = i+1
    return h_index

 

 

- https://school.programmers.co.kr/learn/courses/30/lessons/12939

- 키워드 : split

- 레벨 : 2

def solution(s):
    # split으로 공백 기준으로 나눠 리스트 생성
    # map으로 str -> int로 형변환
    arr = list(map(int, s.split(' ')))
    arr.sort() 

    # 0번(min) n-1번(max)리턴
    return str(arr[0]) + " " + str(arr[-1])

 

 

- https://school.programmers.co.kr/learn/courses/30/lessons/12951

- 키워드 : capitalize

- 레벨 : 2

def solution(s):
    arr = list(s.split(' '))
    str = ""
    for i in range(len(arr)):
        str += arr[i].capitalize()
        if i < len(arr) - 1:
            str += " "    
    return str

 

 

- https://school.programmers.co.kr/learn/courses/30/lessons/70129

- 키워드 : 이진변환(format), binary

- 레벨 : 2

def solution(s):
    binaryCount = 0
    countOfRemovedZero = 0
    while s != "1":
        binaryCount += 1
        count = 0
        for i in range(len(s)):
            if(s[i] == "1"):
                count += 1
        countOfRemovedZero += len(s) - count
        # format 기본 반환형 string
        s = format(count, 'b')
    arr = [binaryCount, countOfRemovedZero]
    return arr

 

 

- https://school.programmers.co.kr/learn/courses/30/lessons/12909

- 키워드 : stack

- 레벨 : 2

def solution(s):
    l = 0
    r = 0
    # "("의 개수가 ")" 의 개수보다 항상 같거나 많아야함
    for i in range(len(s)):
        if(l >= r):       
            if(s[i] == "("):
                l += 1
            else:
                r += 1
        else:
            return False
    # 괄호의 개수가 같지 않을 경우
    if(l != r):
        return False 
    return True

 

 

- https://school.programmers.co.kr/learn/courses/30/lessons/12924#

- 키워드 : number

- 레벨 : 2

def solution(n):
    count = 0
    for i in range(1, n+1):
        sum = 0
        for j in range(i, n+1):
            sum += j
            if(sum == n):
                count += 1
                break
            elif(sum > n):
                break 
    return count

 

 

- https://school.programmers.co.kr/learn/courses/30/lessons/42842

- 키워드 : 완전탐색, 약수

- 레벨 : 2

def solution(brown, yellow):
    # yellow + brown의 약수 구하기
    area = brown + yellow
    arr = []
    for i in range(1, area + 1):
        if(area % i == 0):
            arr.append(i)
 
    arr2 = []
    n = len(arr)
    for i in range(0, int(n/2)+1):
        # 가로의 길이가 세로보다 크거나 같음 주의
        w = arr[n-i-1]
        h = arr[i]
        # 3미만은 길이 될 수 없음
        if(w < 3 or h < 3):
            continue
        
        if((w - 2) * (h - 2) == yellow):
            arr2.append(w)
            arr2.append(h)
            break
                     
    return arr2

 

- https://school.programmers.co.kr/learn/courses/30/lessons/12911?language=python3

- 키워드 : number

- 레벨 : 2

def solution(n):
    # 2진수로 변환했을대 1의 갯수 구하기
    countN = 0
    binN = format(n,'b')
    for i in range(len(binN)):
        if(binN[i] == "1"):
            countN += 1
    
    while True:
        n += 1
        countT = 0
        binT = format(n,'b')
        for i in range(len(binT)):
            if(binT[i] == "1"):
                countT += 1
        if (countT == countN):
            return n

    return -1

 

 

- https://school.programmers.co.kr/learn/courses/30/lessons/17680

- 키워드 : LRU, 딕셔너리(Dictionary)

- 레벨 : 2

def solution(cacheSize, cities):

    # !캐시 사이즈가 0일때 예외처리
    if(cacheSize == 0):
        return len(cities) * 5
    # {city : notUsedTime} 형태의 딕셔너리
    dic = {}
    currentUseCacheSize = 0
    totalRunTime = 0

    for i in range(len(cities)):
        flagDone = False
        # !입력 값이 대소문자가 다른것 유의 => 모두 소문자로 치환
        currentCityName = cities[i].lower()

        ### hit ###
        if currentCityName in dic:
            dic[currentCityName] = 0
            totalRunTime += 1

        ### miss ###
        # 캐시에 없는 도시이고 캐시에 아직 빈자리가 있는 경우
        elif(currentUseCacheSize < cacheSize):
            currentUseCacheSize += 1
            dic[currentCityName] = 0
            totalRunTime += 5
        # 캐시가 비어있지 않는 경우
        else:
            # 가장 value가 큰 값이 LRU 값을 찾아 딕셔너리에서 제거
            max_key = max(dic, key = dic.get)
            del dic[max_key]
            dic[currentCityName] = 0
            totalRunTime += 5
        
        # 모든 value 값 +1
        for key in dic:
            dic[key] += 1
                
    return totalRunTime

 

다른사람의 코드 : 

def solution(cacheSize, cities):
    execTime = 0
    cache = []
    # 캐시가 없을 경우
    if cacheSize == 0: return len(cities) * 5
    for city in cities:
      # cache hit
      if city.lower() in cache:
        cache.remove(city.lower())
        cache.append(city.lower())  # 해당 도시를 리스트의 맨 뒤로 보내기
        execTime += 1
      # cache miss
      else:
        if len(cache) == cacheSize: cache.pop(0)  # LRU 알고리즘으로 캐시 교체
        cache.append(city.lower())
        execTime += 5

    return execTime

출처: https://mjmjmj98.tistory.com/120 [👾:티스토리]

 

 

- https://school.programmers.co.kr/learn/courses/30/lessons/12981

- 키워드 : string

- 레벨 : 2

def solution(n, words):
    usedWords = []
    count = 1
    usedWords.append(words[0])
    for i in range(1, len(words)):
        # 전단어 끝과 현단어 앞이 다른 경우
        if words[i-1][-1] != words[i][0]:
            return(count % n + 1, int(count / n) + 1 )
        # 전에 사용했던 단어인 경우
        elif words[i] in usedWords:
            return(count % n + 1, int(count / n) + 1 )
        else:
            usedWords.append(words[i])
            count += 1
        # 단어 전부 사용했는데 안 끝났을 경우
        if(count == len(words)):
            return [0, 0]

    return -1

 

 

- https://school.programmers.co.kr/learn/courses/30/lessons/12973

- 키워드 : stack, O(n), 시간초과

- 레벨 : 2 (다시보기)

def solution(s):
    stack = []
    for i in range(len(s)):
        if not stack:
            stack.append(s[i])          # stack이 비어있다면 push()
        else:
            if s[i] == stack[-1]:       # stack 마지막 값과 s[i]가 같다면pop()
                stack.pop()
            else:
                stack.append(s[i])      # stack 마지막 값과 s[i]가 다르면 push()

    if stack : return 0                 # stack이 비어있지 않다면 return 0
    else : return 1                     # stack이 비어있다면 return 1

 

 

- https://school.programmers.co.kr/learn/courses/30/lessons/42885

- 키워드 : greedy ,deque, O(n), 시간초과

- 레벨 : 2 (다시보기)

from collections import deque

def solution(people, limit):
    boat = 0
    people.sort(reverse=True) # 내림차순 정렬
    deq = deque(people)

    # 데크가 빌 때까지
    while deq:
        # 큐에 둘 이상이 남아 있을 경우
        if len(deq) > 1:
            # 가장 무거운 사람과 가장 가벼운 사람의 합이 limit 보다 작을 때
            if deq[0] + deq[-1] <= limit:
                # 가장 무거운 사람의 무게에 가벼운 사람의 무게를 합치고
                deq[0] = deq[0] + deq[-1]
                # 가장 가벼운 사람 pop
                deq.pop()
            # 가장 무거운 사람이 가장 가벼운 사람과 못타면 혼자 타야함
            else:
                deq.popleft()
                boat+=1
        else:
            deq.pop()
            boat+=1

    return boat
     

from math import gcd

 

 

- https://school.programmers.co.kr/learn/courses/30/lessons/12953

- 키워드 : gcd, lcm

- 레벨 : 2

 

def solution(arr):
    # 최소공배수 = a * b / gcd(a, b)
    l = arr[0]
    for num in arr:
        l = int((num * l) / gcd(num, l))
        
    return l

 

- https://school.programmers.co.kr/learn/courses/30/lessons/12914

- 키워드 : dp

- 레벨 : 2 

def solution(n):
    dp = [1, 2]
    for i in range(2, n):
        dp.append(dp[i - 1] + dp[i - 2])
    return dp[n-1] % 1234567

 

- https://school.programmers.co.kr/learn/courses/30/lessons/12980

- 키워드 : binary(이진 변환)

- 레벨 : 2

def solution(n):
    return bin(n).count('1')