프로그래머스 level2 문제들(정답률 40%~50%)

- 메뉴 리뉴얼

실패한 처음 코드. 13, 14번이 시간초과가 났다.

def solution(orders, course):
    import itertools
    answer = []
    alphabet = set()
    maxOrderLen = 0
    for order in orders:
        for al in order:
            alphabet.add(al)
        if maxOrderLen < len(order):
            maxOrderLen = len(order)
    alphabet = sorted(list(alphabet))
    # course마다 반복문
    for x in course:
        # x개이상 주문한 손님이 없다면 코스요리를 고려하지 않음
        if x > maxOrderLen:
            break
        courseMax = 0
        courseResult = []
        # course마다 max는 다르다.
        nCr = list(itertools.combinations(list(alphabet), x))
        # x개로 만들 수 있는 메뉴 조합 확인. 메뉴마다 카운트를 가진다.
        for menu in nCr:
            count = 0
            # order마다 메뉴가 order에 포함된다면 카운트.
            for order in orders: 
                for oneMenu in menu:
                    if oneMenu not in order:
                        break
                else:
                    count += 1
            # 카운트 끝나고 최대값인지 비교한다.
            if count > courseMax:
                courseMax = count
                courseResult = [''.join(menu)]
            elif count == courseMax:
                courseResult.append(''.join(menu))
        # 조합 확인이 끝나면 최대 결과들을 정답에 추가
        if courseMax >= 2:
            answer.extend(courseResult)
    return sorted(answer)

통과한 코드.

def solution(orders, course):
    import itertools
    # menuDict를 만들어 모든 combination을 추가한다.
    answer = []
    menuDict = {}
    maxOrderLen = 0
    for order in orders:
        if maxOrderLen < len(order):
            maxOrderLen = len(order)
        for c in course:
            nCr = list(itertools.combinations(sorted(order), c))
            for x in nCr:
                x = ''.join(x)
                if x in menuDict:
                    menuDict[x] += 1
                else:
                    menuDict[x] = 1
    # course마다 길이가 c인 dict key의 최대값을 구하고, 해당것들을 정답에 추가
    getValue = lambda x:menuDict[x]
    for c in course:
        # c개이상 주문한 사람이 없다면 고려하지 않음
        if c > maxOrderLen:
            break
        cLenMenus = list(filter(lambda x:len(x)==c, menuDict))
        cLenMenuMax = max(list(map(getValue, cLenMenus)))
        # 2명 이상의 손님으로부터 주문된 조합이어야함
        if cLenMenuMax >= 2:
            answer += list(filter(lambda x:len(x)==c and menuDict[x] == cLenMenuMax, menuDict))
    return sorted(answer)

- 마법의 엘리베이터

def solution(storey):
    # bfs로 1의자리수부터 큰 자리수까지 하면 된다.
    import queue
    que = queue.Queue()
    que.put([storey, 0])
    minDict = {}
    minDict[storey] = 0
    while not que.empty():
        num, rock = que.get()
        # 0은 더이상 검사할 필요 없음
        if num == 0:
            continue
        c = 1
        while True:
            if num % int(10**c) != 0:
                break
            c+=1
        q, r = divmod(num, int(10**c))
        # 최소값이라면 dict갱신
        nextRock = rock + r//int(10**(c-1))
        if q*int(10**c) in minDict:
            if minDict[q*int(10**c)] > nextRock:
                que.put([q*int(10**c), nextRock])
                minDict[q*int(10**c)] = nextRock
        else:
            que.put([q*int(10**c), nextRock])
            minDict[q*int(10**c)] = nextRock
        # 최상위자리수이고 5이하면 위층으로 갈 필요 없음
        if int(str(num).replace('0', '')) <= 5:
            continue
        # 최소값이라면 dict갱신
        nextRock = rock + 10 - r//int(10**(c-1))
        if (q+1)*int(10**c) in minDict:
            if minDict[(q+1)*int(10**c)] > nextRock:
                que.put([(q+1)*int(10**c), nextRock])
                minDict[(q+1)*int(10**c)] = nextRock
        else:
            que.put([(q+1)*int(10**c), nextRock])
            minDict[(q+1)*int(10**c)] = nextRock
    #print(minDict)
    return minDict[0]

- 전력망을 둘로 나누기

def solution(n, wires):
    answer = n
    # 하나가 끊기면 무조건 두개의 트리가 만들어짐
    for i in range(len(wires)):
        matrix = [[0 for i in range(n+1)] for i in range(n+1)]
        changedWires = wires[:i] + wires[i+1:]
        for x, y in changedWires:
            matrix[x][y] = 1
            matrix[y][x] = 1
        nodes = set([i for i in range(1, n+1)])
        # 1부터 연결된 노드의 개수를 센다. dfs
        stack = [1]
        while len(stack)>0:
            d = stack.pop()
            nodes.remove(d)
            # 다음 인덱스들은 현재 노드와 인접해야 하고, 방문하지 않은 노드여야한다
            nextIdx = list(filter(lambda x:matrix[d][x]==1 and x in nodes, range(n+1)))
            for x in nextIdx:
                stack.append(x)
        difference = abs(n-2*len(nodes))
        if difference < answer:
            answer = difference
    return answer

- 호텔 대실

def after10m(s):
    h = int(s[:2])
    m = int(s[3:])
    m += 10
    if m >= 60:
        m -= 60
        h += 1
    return str(h).rjust(2, '0')+':'+str(m).rjust(2, '0')
    
def solution(book_time):
    # 시작시간기준 정렬
    book_time.sort(key=lambda x:x[0])
    rooms = []
    maxRoom = 0
    # 앞에서부터 하나씩 리스트에 넣는데, 리스트안에 끝나는시간+10분이 넣어야하는 
    # 시작시간보다 작거나 같다면 pop한다.
    for x in book_time:
        rooms = list(filter(lambda y:after10m(y[1]) > x[0], rooms))
        rooms.append(x)
        if maxRoom < len(rooms):
            maxRoom = len(rooms)
    return maxRoom

- 시소 짝꿍

처음에는 2중for문을 돌려서, 시간이 10만*(10만+1)/2만큼 탐색했는데, 질문하기 세션을 본 후 2*10만 만큼 탐색하는 코드로 바뀌었다.

def solution(weights):
    answer = 0
    weights.sort()
    p = [[1, 1], [3, 2], [2, 1], [4, 3]]
    length = len(weights)
    d = {}
    for x in weights:
        if x in d:
            d[x] += 1
        else:
            d[x] = 1
    for i in range(length-1):
        weight = weights[i]
        # d에서 자신을 제외함.
        d[weight] -= 1
        if d[weight] == 0:
            del d[weight]
        # 가능한 숫자만큼 answer에 더함
        for x in p:
            num = weight * x[0] / x[1]
            if num in d:
                answer += d[num]
    return answer

- 무인도 여행

처음에 xx, yy 대신 x, y로 변수를 사용해서 50점만 나왔었다. 변수는 지역변수라 해도 다르게 사용하자!

def solution(maps):
    answer = []
    h = len(maps)
    w = len(maps[0])
    dx = [0, 0, 1, -1]
    dy = [1, -1, 0, 0]
    for i in range(h):
        maps[i] = list(maps[i])
    for y in range(h):
        for x in range(w):
            if maps[y][x] != "X":
                # dfs로 해당 무인도의 총 식량을 구함
                stack = []
                food = 0
                stack.append([y, x])
                while len(stack) > 0:
                    [yy, xx] = stack.pop()
                    # X가 아니라면 food에 추가
                    if maps[yy][xx] != "X":
                        food += int(maps[yy][xx])
                        maps[yy][xx] = "X"
                    else:
                        continue
                    # 상하좌우에 연결되는 땅이 있으면 스택에 넣음
                    for i in range(4):
                        nx = xx + dx[i]
                        ny = yy + dy[i]
                        if nx >= 0 and nx < w and ny >=0 and ny < h:
                            if maps[ny][nx] != "X":
                                stack.append([ny, nx])
                answer.append(food)
    answer.sort()
    if len(answer) == 0:
        answer.append(-1)
    return answer

- [3차] 방금그곡

문제에 B#이 없지만, B#조건을 추가해주어야 34번이 맞는다.

def solution(m, musicinfos):
    import math
    answer = '(None)'
    maxD = 0
    repStr = lambda s:s.replace('C#','c').replace('D#','d').replace('F#','f').replace('G#','g').replace('A#','a').replace('B#','b')
    m = repStr(m)
    # 곡마다: 실제재상 구하기, 들어있는지 확인하기, 들어있다면 음악 제목 넣기
    for music in musicinfos:
        startT, endT, title, play = music.split(',')
        duration = (int(endT[:2])-int(startT[:2]))*60 + int(endT[3:])-int(startT[3:])
        play = repStr(play)
        play = play * math.ceil(duration/len(play))
        play = play[:duration]
        if m in play:
            if duration > maxD:
                answer = title
                maxD = duration
    return answer

대문자#이 문제라면, regex를 사용해 모든 경우의 수를 replace하는 방법도 있다.

def solution(m, musicinfos):
    import math
    import re
    answer = '(None)'
    maxD = 0
    repStr = lambda s:re.sub('[A-Z]#', lambda x:x.group()[0].lower(), s)
    m = repStr(m)
    # 곡마다: 실제재상 구하기, 들어있는지 확인하기, 들어있다면 음악 제목 넣기
    for music in musicinfos:
        startT, endT, title, play = music.split(',')
        duration = (int(endT[:2])-int(startT[:2]))*60 + int(endT[3:])-int(startT[3:])
        play = repStr(play)
        play = play * math.ceil(duration/len(play))
        play = play[:duration]
        if m in play:
            if duration > maxD:
                answer = title
                maxD = duration
    return answer

- 숫자 카드 나누기

def primeFactorization(num):
    d = {}
    x = 2
    while x <= num:
        if num % x == 0:
            if x in d:
                d[x] += 1
            else:
                d[x] = 1
            num //= x
        else:
            x += 1
    return d
def solution(arrayA, arrayB):
    import math
    # 나눌 수 있다-나머지가 0이다, 나눌 수 없다-나머지가 0이 아니다
    answer = 0
    # 철수의 경우
    gcd = 0
    if len(arrayA) == 1:
        gcd = arrayA[0]
    else:
        gcd = math.gcd(arrayA[0], arrayA[1])
        for i in range(2, len(arrayA)):
            gcd = math.gcd(gcd, arrayA[i])
    # 소인수분해로 만들 수 있는 숫자들로 나누어본다.
    if gcd != 1:
        d = primeFactorization(gcd)
        stack = [] # [num, depth]
        keys = list(d.keys())
        for i in range(d[keys[0]]+1):
            stack.append([keys[0]**i, 1])
        while len(stack):
            [num, depth] = stack.pop()
            if depth == len(d):
                # 상대 숫자들을 모두 나눌 수 없을 때.
                for y in arrayB:
                    if y % num == 0:
                        break
                else:
                    if answer < num:
                        answer = num
            else:
                for i in range(d[keys[depth]]+1):
                    stack.append([keys[depth]**i*num, depth+1])
    # 영희의 경우
    if len(arrayB) == 1:
        gcd = arrayB[0]
    else:
        gcd = math.gcd(arrayB[0], arrayB[1])
        for i in range(2, len(arrayB)):
            gcd = math.gcd(gcd, arrayB[i])
    # 소인수분해로 만들 수 있는 숫자들로 나누어본다.
    if gcd != 1:
        d = primeFactorization(gcd)
        stack = [] # [num, depth]
        keys = list(d.keys())
        for i in range(d[keys[0]]+1):
            stack.append([keys[0]**i, 1])
        while len(stack):
            [num, depth] = stack.pop()
            if depth == len(d):
                # 상대 숫자들을 모두 나눌 수 없을 때.
                for y in arrayA:
                    if y % num == 0:
                        break
                else:
                    if answer < num:
                        answer = num
            else:
                for i in range(d[keys[depth]]+1):
                    stack.append([keys[depth]**i*num, depth+1])
    return answer

- 배달

처음 다익스트라를 사용해 풀어본 문제다. 문제를 풀긴 했지만 다익스트라는 아직 익숙하지 않아서 나중에 또 해봐야될듯 하다.

def solution(N, road, K):
    INF = 1234567890
    # 인접 행렬
    g = [[INF for x in range(N)] for y in range(N)]
    for [v1, v2, distance] in road:
        v1 -= 1
        v2 -= 1
        if g[v1][v2] > distance:
            g[v1][v2] = distance
        if g[v2][v1] > distance:
            g[v2][v1] = distance
    for i in range(N):
        g[i][i] = 0
    # d는 최단거리, v는 방문한 노드
    def shortest(d, v):
        m = INF
        index = 0
        for i in range(N):
            if v[i] == False and d[i] < m:
                m = d[i]
                index = i
        return index
    # 다익스트라
    def dijkstra(start):
        # 최단거리 리스트
        d = g[start]
        # 방문한 노드
        v = [False for x in range(N)]
        v[start] = True
        # N-2번동안 방문안한 제일거리짧은 정점을 구해 최단거리 갱신
        for x in range(N-2):
            current = shortest(d, v)
            for y in range(N):
                if d[y] > d[current] + g[current][y]:
                    d[y] = d[current] + g[current][y]
            v[current] = True
        return d
    return len(list(filter(lambda x: x<=K, dijkstra(0))))

- 괄호 변환 

문제가 무슨말인가 했었는데, 재귀를 염두해두고 설명한 문제였다.

def rightBracket(s):
    count = 0
    for c in s:
        if c == "(":
            count += 1
        elif c == ")":
            count -= 1
        if count < 0:
            return False
    return True
def reverseBracket(s):
    temp = ""
    for c in s:
        if c == "(":
            temp += ')'
        else:
            temp += '('
    return temp
def solution(p):
    # 1. 입력이 빈 문자열인 경우, 빈 문자열을 반환합니다. 
    if p == "":
        return ""
    # 2. 문자열 w를 두 "균형잡힌 괄호 문자열" u, v로 분리합니다.
    count = 0
    index = 0
    for i in range(len(p)):
        if p[i] == "(":
            count += 1
        elif p[i] == ")":
            count -= 1
        if count == 0:
            index = i
            break
    u = p[:index+1]
    v = p[index+1:]
    # 3. 문자열 u가 "올바른 괄호 문자열" 이라면 문자열 v에 대해 1단계부터 다시 수행합니다.
    if rightBracket(u):
        return u + solution(v)
    # 4. 문자열 u가 "올바른 괄호 문자열"이 아니라면 아래 과정을 수행합니다. 
    return '(' + solution(v) + ')' + reverseBracket(u[1:-1])

- 수식 최대화

def solution(expression):
    import re
    import copy
    exp = list(re.findall("[0-9]+|[-+*]", expression))
    for i in range(len(exp)):
        if exp[i].isnumeric():
            exp[i] = int(exp[i])
    answer = 0
    charPriority = ["+-*", "+*-", "-+*", "-*+", "*+-", "*-+"]
    # 6가지 해보며 최대값을 구한다
    for char in charPriority:
        exp2 = copy.deepcopy(exp)
        # 012번째 연산문자를 계산한다
        for c in char:
            # exp2에 따라 c 연산문자에 해당하는 값을 계산
            while True:
                if c in exp2:
                    index = exp2.index(c)
                    num1 = exp2.pop(index-1)
                    exp2.pop(index-1)
                    num2 = exp2.pop(index-1)
                    if c == "+":
                        exp2.insert(index-1, num1+num2)
                    elif c == "-":
                        exp2.insert(index-1, num1-num2)
                    elif c == "*":
                        exp2.insert(index-1, num1*num2)
                else:
                    break
        if answer < abs(exp2[0]):
            answer = abs(exp2[0])
    return answer

- 줄 서는 방법

def fac(n):
    if n <= 1:
        return 1
    return n * fac(n-1)
def solution(n, k):
    k -= 1
    arr = [x for x in range(1, n+1)]
    answer = []
    while True:
        # 몇번째로 큰 숫자인지 구하는것
        index = k//fac(n-1)
        answer.append(arr.pop(index))
        k %= fac(n-1)
        n -= 1
        if len(arr) == 0:
            break
    return answer

- 행렬 테두리 회전하기

행과 렬을 바꿔서 설명한다. 헷갈리게 하는 문제다. 

def solution(rows, columns, queries):
    arr = [[i*columns + j + 1 for j in range(columns)] for i in range(rows)]
    answer = []
    for [y1, x1, y2, x2] in queries:
        y1-=1
        x1-=1
        y2-=1
        x2-=1
        clock = []
        for x in range(x1, x2+1): #위
            clock.append(arr[y1][x])
        for y in range(y1+1, y2+1): #오른쪽
            clock.append(arr[y][x2])
        for x in range(x2-1, x1-1, -1): #아래
            clock.append(arr[y2][x])
        for y in range(y2-1, y1, -1): #왼쪽
            clock.append(arr[y][x1])
        answer.append(min(clock))
        arr[y1][x1] = clock[-1]
        idx = 0
        for x in range(x1+1, x2+1): #위
            arr[y1][x] = clock[idx]
            idx+=1
        for y in range(y1+1, y2+1): #오른쪽
            arr[y][x2] = clock[idx]
            idx+=1
        for x in range(x2-1, x1-1, -1): #아래
            arr[y2][x] = clock[idx]
            idx+=1
        for y in range(y2-1, y1, -1): #왼쪽
            arr[y][x1] = clock[idx]
            idx+=1
    return answer

- 거리두기 확인하기

def solution(places):
    answer = []
    for place in places:
        flag = False
        for y in range(5):
            if flag:
                break
            for x in range(5):
                if place[y][x] == "P":
                    # 오른쪽이나 아래가 P라면 거리두기x
                    if x < 4 and place[y][x+1] == "P":
                        flag = True
                        break
                    if y < 4 and place[y+1][x] == "P":
                        flag = True
                        break
                    # 오른쪽2칸이 P이고 오른쪽이 X가 아니라면 거리두기x
                    if x < 3 and place[y][x+2] == "P":
                        if place[y][x+1] != "X":
                            flag = True
                            break
                    # 아래2칸이 P이고 아래가 X가 아니라면 거리두기x
                    if y < 3 and place[y+2][x] == "P":
                        if place[y+1][x] != "X":
                            flag = True
                            break
                    # 오른쪽아래가 P이고 오른쪽과 아래가 X가 아니라면 거리두기x
                    if x < 4 and y < 4 and place[y+1][x+1] == "P":
                        if not (place[y][x+1] == "X" and place[y+1][x] == "X"):
                            flag = True
                            break
                    # 왼쪽아래가 P이고 왼쪽과 아래가 X가 아니라면 거리두기x
                    if x > 0 and y < 4 and place[y+1][x-1] == "P":
                        if not (place[y][x-1] == "X" and place[y+1][x] == "X"):
                            flag = True
                            break
        if flag:
            answer.append(0)
        else:
            answer.append(1)
    return answer

- 테이블 해시 함수

def solution(data, col, row_begin, row_end):
    data.sort(key=lambda x:(x[col-1], -x[0]))
    answer = 0
    for i in range(row_begin-1, row_end):
        total = 0
        for d in data[i]:
            total += d % (i+1)
        answer ^= total
    return answer

- 미로 탈출

그냥 bfs문제이다.

def solution(maps):
    from collections import deque
    import copy
    deq = deque()
    answer = 0
    dx = [0,0,1,-1]
    dy = [1,-1,0,0]
    start = None
    end = None
    lever = None
    maps2 = []
    maps3 = []
    for y in range(len(maps)):
        maps2y = []
        maps3y = []
        for x in range(len(maps[0])):
            if maps[y][x] == "X":
                maps2y.append(1)
                maps3y.append(1)
            else:
                maps2y.append(0)
                maps3y.append(0)
            if maps[y][x] == "S":
                start = [y, x]
            elif maps[y][x] == "E":
                end = [y, x]
            elif maps[y][x] == "L":
                lever = [y, x]
        maps2.append(maps2y)
        maps3.append(maps3y)
    # S부터 L까지의 거리 구함
    deq.append([0, start])
    while(len(deq)):
        [dis, [y, x]] = deq.popleft()
        # 현재 자리가 0이라면 적용
        if maps2[y][x] == 0:
            maps2[y][x] = dis
            # 상하좌우로 0이 아니라면 append
            for i in range(4):
                nx = x + dx[i]
                ny = y + dy[i]
                if 0 <= nx and nx < len(maps[0]) and 0 <= ny and ny < len(maps):
                    if maps2[ny][nx] ==0:
                        deq.append([dis+1, [ny, nx]])
            if [y, x] == lever:
                break
    if maps2[lever[0]][lever[1]] == 0:
        return -1
    answer += maps2[lever[0]][lever[1]]
    # L부터 E까지의 거리 구함
    deq.clear()
    deq.append([0, lever])
    while(len(deq)):
        [dis, [y, x]] = deq.popleft()
        # 현재 자리가 0이라면 적용
        if maps3[y][x] == 0:
            maps3[y][x] = dis
            # 상하좌우로 0이 아니라면 append
            for i in range(4):
                nx = x + dx[i]
                ny = y + dy[i]
                if 0 <= nx and nx < len(maps[0]) and 0 <= ny and ny < len(maps):
                    if maps3[ny][nx] ==0:
                        deq.append([dis+1, [ny, nx]])
            if [y, x] == end:
                break
    if maps3[end[0]][end[1]] == 0:
        return -1
    answer += maps3[end[0]][end[1]]
    return answer

- 가장 큰 정사각형 찾기

꽤 어려운 dp문제이다.

def solution(board):
    answer = 0
    height = len(board)
    width = len(board[0])
    for y in range(height):
        for x in range(width):
            if board[y][x] == 0:
                continue
            # 왼위, 왼, 위 중에 최소값+1이 자신이 됨
            if x > 0 and y > 0:
                board[y][x] = min([board[y-1][x-1], board[y-1][x], board[y][x-1]])+1
        if max(board[y])**2 > answer:
            answer = max(board[y])**2
    return answer

- 리코쳇 로봇

예전에 포켓몬 ds로 체육관 관장을 깰 때 봤던 문제이다.

bfs로 풀린다.

def solution(board):
    from collections import deque
    deq = deque()
    answer = -1
    robot = None
    goal = None
    for y in range(len(board)):
        board[y] = list(board[y])
        for x in range(len(board[0])):
            if board[y][x] == "R":
                robot = [y, x]
            elif board[y][x] == "G":
                goal = [y, x]
    # bfs다. 첫 위치서부터 해당 칸에 최소 움직임을 저장한다.
    deq.append([0, robot])
    while len(deq) > 0:
        [d, [y, x]] = deq.popleft()
        if [y, x] == goal:
            answer = d
            break
        if not(board[y][x] == '.' or board[y][x] == 'R'):
            continue
        board[y][x] = d
        # 상하좌우로 움직임
        dx = x - 1
        while dx >= 0 and board[y][dx] != 'D':
            dx -= 1
        deq.append([d+1, [y, dx+1]])
        dx = x + 1
        while dx < len(board[0]) and board[y][dx] != 'D':
            dx += 1
        deq.append([d+1, [y, dx-1]])
        dx = x
        dy = y - 1
        while dy >= 0 and board[dy][x] != 'D':
            dy -= 1
        deq.append([d+1, [dy+1, x]])
        dy = y + 1
        while dy < len(board) and board[dy][x] != 'D':
            dy += 1
        deq.append([d+1, [dy-1, dx]])
    return answer

- 하노이의 탑

어릴적해 해본 하노이탑. 그때는 막연히 규칙이 있다고 생각했지만, 지금 다시 코드로 구현해보니 재귀함수로 구현할 수 있는 것이었다. 충격...

def hanoi(myPosition, destPosition, num, arr):
    if num == 1:
        arr.append([myPosition, destPosition])
        return
    # 자신과 위를 나누어 재귀 호출
    # 위를 자신위치, 목표위치도 아닌곳에 보냄
    rest = [1,2,3]
    rest.remove(myPosition)
    rest.remove(destPosition)
    rest = rest[0]
    hanoi(myPosition, rest, num-1, arr)
    # 자신을 목표위치로 보냄
    arr.append([myPosition, destPosition])
    # 위를 목표위치로 보냄
    hanoi(rest, destPosition, num-1, arr)
def solution(n):
    answer = []
    hanoi(1, 3, n, answer)
    return answer

- 디펜스 게임

힙을 사용하면 시간을 상당히 단축할 수 있다.

def solution(n, k, enemy):
    import heapq
    total = 0       # 전체 숫자 합
    maxSum = 0      # 최대값들의 합
    maxCount = 0    # 최대값 개수
    heap = []       # 우선순위 힙
    answer = len(enemy)
    for i in range(len(enemy)):
        num = enemy[i]
        total += num
        heapq.heappush(heap, num)
        maxSum += num
        maxCount += 1
        # k개보다 많다면 힙에서 최소값을 빼준다.
        if maxCount > k:
            minNum = heapq.heappop(heap)
            maxSum -= minNum
            maxCount -= 1
        # 전체 - 최대값들의 합 > n이면 break
        if total - maxSum > n:
            answer = i
            break
    return answer

- 문자열 압축

def compressLen(s, n):
    alpha = s[0:n]
    count = 1
    Len = 0
    for i in range(n, len(s), n):
        if alpha == s[i:i+n]:
            count += 1
        else:
            alpha = s[i:i+n]
            if count == 1:
                Len += n
            else:
                Len += len(str(count))+n
            count = 1
    if count == 1:
        Len += len(alpha)
    else:
        Len += len(str(count))+n
    return Len
def solution(s):
    answer = 0
    Min = len(s)
    for i in range(1, len(s)):
        result = compressLen(s, i)
        if Min > result:
            Min = result
    return Min

- 멀쩡한 사각형

def solution(w,h):
    import math
    mul = math.gcd(w, h)
    answer = w*h
    w //= mul
    h //= mul
    # 기울기가 1이라면 
    # if h == w:
    #     answer - mul
    # 큰 숫자 + 작은숫자 - 1개가 못쓰는 개수임
    return answer - mul*(w+h-1)

- 광물 캐기

dp문제이다.

def solution(picks, minerals):
    answer = 25*50
    # 순열로 해봤는데 시간초과. dp문제인듯 하다.
    from collections import deque
    deq = deque()
    minDict = {} # 곡괭이 개수: 피로도를 짝으로 가지는 dictionary
    deq.append([tuple(picks), 0, 0]) #[곡괭이 개수, 인덱스, 피로도]
    while len(deq) > 0:
        [picks, index, tireness] = deq.popleft()
        # dictionary에 같은 곡괭이 개수가 있고, 그 값보다 크다면 고려하지 않음
        if picks in minDict:
            if tireness > minDict[picks]:
                continue
            # dictionary에 같은 곡괭이 개수가 있고, 내가 더 작다면 값 갱신
            else:
                minDict[picks] = tireness
        # dictionary에 곡괭이 개수가 없다면 피로도를 등록함
        else:
            minDict[picks] = tireness
        # 곡괭이를 다 썼거나 index가 끝이나면 answer와 비교한다.
        if (picks[0] == 0 and picks[1] == 0 and picks[2] == 0) or index >= len(minerals):
            if tireness < answer:
                answer = tireness
                continue
        # 다이아곡괭이가 남았을 경우
        if picks[0] > 0:
            idx = index
            tireness2 = tireness
            # 5번동안 광질한다
            for k in range(5):
                if idx >= len(minerals):
                    break
                tireness2 += 1
                idx += 1
            deq.append([(picks[0]-1, picks[1], picks[2]), idx, tireness2])
        # 철곡괭이가 남았을 경우
        if picks[1] > 0:
            idx = index
            tireness2 = tireness
            # 5번동안 광질한다
            for k in range(5):
                if idx >= len(minerals):
                    break
                if minerals[idx] == 'diamond':
                    tireness2 += 5
                else:
                    tireness2 += 1
                idx += 1
            deq.append([(picks[0], picks[1]-1, picks[2]), idx, tireness2])
        # 돌곡괭이가 남아있을 경우
        if picks[2] > 0:
            idx = index
            tireness2 = tireness
            # 5번동안 광질한다
            for k in range(5):
                if idx >= len(minerals):
                    break
                if minerals[idx] == 'diamond':
                    tireness2 += 25
                elif minerals[idx] == 'iron':
                    tireness2 += 5
                else:
                    tireness2 += 1
                idx += 1
            deq.append([(picks[0], picks[1], picks[2]-1), idx, tireness2])
    return answer

- 우박수열 정적분

def solution(k, ranges):
    result = []
    coordinate = [k]
    area = [] #넓이. x가 idx~idx+1일때의 넓이를 저장한다.
    index = 1
    while k != 1:
        if k % 2 == 0:
            k = k//2
        else:
            k = k * 3 + 1
        coordinate.append(k)
        # index-1~index의 넓이를 area[index-1]에 저장함
        area.append(min(coordinate[-2], coordinate[-1]) + abs(coordinate[-2] - coordinate[-1])/2)
    # 범위마다 넓이를 구해줌
    for [a, b] in ranges:
        # [0, 0]이라면 전체 구간 넓이
        if a == 0 and b == 0:
            result.append(sum(area))
        # b가 음수라면 a <= x <= n-b 의 넓이
        else:
            b = len(coordinate) + b - 1
            # 유효하지 않은 구간이라면 -1
            if a > b:
                result.append(-1)
            else:
                result.append(sum(area[a: b]))
    return result

- 점 찍기

def solution(k, d):
    import math
    answer = 0
    # x좌표가 0 ~ d까지일 때 반복
    for x in range(0, d+1, k):
        # x좌표가 x일 때 y의 값을 구하여 y개수를 구함. 이것을 정답에 더한다.
        answer += math.floor(math.sqrt(d*d-x*x))//k + 1
    return answer

- 후보키

def solution(relation):
    # 0, 1, 2, 3등 columns의 인덱스들을 초기값으로 넣고, 01, 02, 03등으로 열 개수를 늘려나간다.
    # 만약 후보키라면 후보키리스트에 추가한다.
    cKeyList = []
    from collections import deque
    deq = deque()
    xLen = len(relation[0])
    for i in range(xLen):
        deq.append([i])
    while len(deq)>0:
        # 인덱스에 해당되는 값들을 비교해 후보키인지 판단한다.
        indexes = deq.popleft()
        # 후보키의 최소성에 만족하지 않으면 검사 종료
        flag = False
        for cKey in cKeyList:
            if set(cKey).issubset(indexes):
                flag = True
        if flag:
            continue
        # 중복되는게 있는지는 집합으로 확인한다.
        s = set()
        flag = True
        for r in relation:
            val = []
            for i in range(xLen):
                if i in indexes:
                    val.append(r[i])
            val = tuple(val)
            if val in s:
                flag = False
            else:
                s.add(val)
        # 후보키라면 후보키 리스트에 추가
        if flag:
            cKeyList.append(indexes)
        # 후보키가 아니라면 열 개수를 늘려서 큐에 enqueue한다
        else:
            for x in range(xLen):
                if x not in indexes:
                    deq.append(indexes+[x])
    return len(cKeyList)