담학기에이쁠's 코딩 복습

문제 설명

• 어느 학교에 페인트가 칠해진 길이가 n미터인 벽이 있습니다. 벽에 동아리 · 학회 홍보나 회사 채용 공고 포스터 등을 게시하기 위해 테이프로 붙였다가 철거할 때 떼는 일이 많고 그 과정에서 페인트가 벗겨지곤 합니다. 페인트가 벗겨진 벽이 보기 흉해져 학교는 벽에 페인트를 덧칠하기로 했습니다.
• 넓은 벽 전체에 페인트를 새로 칠하는 대신, 구역을 나누어 일부만 페인트를 새로 칠 함으로써 예산을 아끼려 합니다. 이를 위해 벽을 1미터 길이의 구역 n개로 나누고, 각 구역에 왼쪽부터 순서대로 1번부터 n번까지 번호를 붙였습니다. 그리고 페인트를 다시 칠해야 할 구역들을 정했습니다.
• 벽에 페인트를 칠하는 롤러의 길이는 m미터이고, 롤러로 벽에 페인트를 한 번 칠하는 규칙은 다음과 같습니다.
  • 롤러가 벽에서 벗어나면 안 됩니다.
  • 구역의 일부분만 포함되도록 칠하면 안 됩니다.
• 즉, 롤러의 좌우측 끝을 구역의 경계선 혹은 벽의 좌우측 끝부분에 맞춘 후 롤러를 위아래로 움직이면서 벽을 칠합니다. 현재 페인트를 칠하는 구역들을 완전히 칠한 후 벽에서 롤러를 떼며, 이를 벽을 한 번 칠했다고 정의합니다.
• 한 구역에 페인트를 여러 번 칠해도 되고 다시 칠해야 할 구역이 아닌 곳에 페인트를 칠해도 되지만 다시 칠하기로 정한 구역은 적어도 한 번 페인트칠을 해야 합니다. 예산을 아끼기 위해 다시 칠할 구역을 정했듯 마찬가지로 롤러로 페인트칠을 하는 횟수를 최소화하려고 합니다.
• 정수 n, m과 다시 페인트를 칠하기로 정한 구역들의 번호가 담긴 정수 배열 section이 매개변수로 주어질 때 롤러로 페인트칠해야 하는 최소 횟수를 return 하는 solution 함수를 작성해 주세요.

제한사항

• 1 ≤ m ≤ n ≤ 100,000
• 1 ≤ section의 길이 ≤ n
• 1 ≤ section의 원소 ≤ n
  • section의 원소는 페인트를 다시 칠해야 하는 구역의 번호입니다.
  • section에서 같은 원소가 두 번 이상 나타나지 않습니다.
  • section의 원소는 오름차순으로 정렬되어 있습니다.

n = 8
m = 4
section = [2,3,6]
# result = 2

def solution(n, m, section):
    answer = 0
    
    # n개의 벽을 하나하나 보기 보다는
    # section은 칠해야 할 벽을 작은 수 부터 정렬해 놓았으니
    # section의 맨 첫 번째 값에 해당하는 벽 부터 시작하면 된다.
    # sectio의 첫번째 값에 1을 뺀 후 frist_num에 저장
    first_num = section[0] -1
    
    # section의 요소들을 하나하나 살펴보며
    for num in section:
        
        # 만약 first_num의 값이 section의 요소 중 하나인 num 보다 작으면
        if first_num < num:
            
            # num에 롤러의 길의 -1 값을 더한다.
            # 이는 section의 값에 해당하는 위치의 벽만 살펴 보겠다는 의미이다.
            # 앞에 수만은 벽이 있어도 section에 해당하는 즉 다시 칠할 벽 부분 만 본다는 뜻이다.
            # 아래의 식을 수행하면 first_num은 num에서 롤러의 길이 만큼의 벽에 도달한다.
            first_num = num+m-1
            # 그리고 벽을 칠했으니 answer에 1을 더한다.
            answer += 1
            
            # 다시 for 문으로 돌아가면 롤러로 칠한 끝 부분부터 시작한다.
    return answer
    
    # 함수를 실행 해 보자.
    solution(n, m, section)
    # 2 가 출력된다.

문제 설명

• 머쓱이는 태어난 지 11개월 된 조카를 돌보고 있습니다. 조카는 아직 "aya", "ye", "woo", "ma" 네 가지 발음과 네 가지 발음을 조합해서 만들 수 있는 발음밖에 하지 못하고 연속해서 같은 발음을 하는 것을 어려워합니다. 문자열 배열 babbling이 매개변수로 주어질 때, 머쓱이의 조카가 발음할 수 있는 단어의 개수를 return하도록 solution 함수를 완성해주세요.

제한사항

• 1 ≤ babbling의 길이 ≤ 100
• 1 ≤ babbling[i]의 길이 ≤ 30
• 문자열은 알파벳 소문자로만 이루어져 있습니다.

# 입출력 예
babbling = ["ayaye", "uuu", "yeye", "yemawoo", "ayaayaa"]
babbling1 = ["aya", "yee", "u", "maa"]

def solution(babbling):


    # 머쓱이가 낼 수 있는 옹알이를 words에 리스트로 넣어놓는다.
    words= ["aya", "ye", "woo", "ma"]

    answer = 0
    # for문으로 babbling안에 있는 문자열 하나하나를 babbl에 저장한다.
    for babbl in babbling:
        # words에 있는 요소 하나하나를 word에 저장한다.
        for word in words:
            # 문제에서 연속해서 같은 발음을 하는 것은 불가능하기에
            # word가 두번 babbl에 들어가지 않으면
            if word*2 not in babbl:
                # babbl에 word부분을 " "으로 replace한다.
                babbl = babbl.replace(word," ")
        # 그 후 babbl에 있는 모든 공백을 strip으로 날리고 "" 와 같아지면
        if babbl.strip() == "":
            # answer에 1을 더한다.
            answer +=1
    return answer

print(solution(babbling))
print(solution(babbling1))

# 2
# 1

다른 사람의 풀이

def solution(babbling):
    count = 0
    
    # babbling에 있는 문자열 하나한를 b에 저장해 살펴본다.
    for b in babbling:
        # 만약 "aya", "ye", "woo", "ma" 들이 두번 연속 해서 나오지 않는다면 계속
        if "ayaaya" in b or "yeye" in b or "woowoo" in b or "mama" in b:
            continue
        # 만약 "aya", "ye", "woo", "ma" 문자열 모두 공백으로 replace한 후 공백을 없애 버리면 False가 됨
        # not을 붙여 반대로 True로 만들어 진다면
        if not b.replace("aya", " ").replace("ye", " ").replace("woo", " ").replace("ma", " ").replace(" ", ""):
            # count에 1 추가
            count += 1

    return count

문제 설명

• 코딩테스트를 준비하는 머쓱이는 프로그래머스에서 문제를 풀고 나중에 다시 코드를 보면서 공부하려고 작성한 코드를 컴퓨터 바탕화면에 아무 위치에나 저장해 둡니다. 저장한 코드가 많아지면서 머쓱이는 본인의 컴퓨터 바탕화면이 너무 지저분하다고 생각했습니다. 프로그래머스에서 작성했던 코드는 그 문제에 가서 다시 볼 수 있기 때문에 저장해 둔 파일들을 전부 삭제하기로 했습니다.
• 컴퓨터 바탕화면은 각 칸이 정사각형인 격자판입니다. 이때 컴퓨터 바탕화면의 상태를 나타낸 문자열 배열 wallpaper가 주어집니다. 파일들은 바탕화면의 격자칸에 위치하고 바탕화면의 격자점들은 바탕화면의 가장 왼쪽 위를 (0, 0)으로 시작해 (세로 좌표, 가로 좌표)로 표현합니다. 빈칸은 ".", 파일이 있는 칸은 "#"의 값을 가집니다. 드래그를 하면 파일들을 선택할 수 있고, 선택된 파일들을 삭제할 수 있습니다. 머쓱이는 최소한의 이동거리를 갖는 한 번의 드래그로 모든 파일을 선택해서 한 번에 지우려고 하며 드래그로 파일들을 선택하는 방법은 다음과 같습니다.
  • 드래그는 바탕화면의 격자점 S(lux, luy)를 마우스 왼쪽 버튼으로 클릭한 상태로 격자점 E(rdx, rdy)로 이동한 뒤 마우스 왼쪽 버튼을 떼는 행동입니다. 이때, "점 S에서 점 E로 드래그한다"고 표현하고 점 S와 점 E를 각각 드래그의 시작점, 끝점이라고 표현합니다.
  • 점 S(lux, luy)에서 점 E(rdx, rdy)로 드래그를 할 때, "드래그 한 거리"는 |rdx - lux| + |rdy - luy|로 정의합니다.
  • 점 S에서 점 E로 드래그를 하면 바탕화면에서 두 격자점을 각각 왼쪽 위, 오른쪽 아래로 하는 직사각형 내부에 있는 모든 파일이 선택됩니다.
• 예를 들어 wallpaper = [".#...", "..#..", "...#."]인 바탕화면을 그림으로 나타내면 다음과 같습니다.

• 이러한 바탕화면에서 다음 그림과 같이 S(0, 1)에서 E(3, 4)로 드래그하면 세 개의 파일이 모두 선택되므로 드래그 한 거리 (3 - 0) + (4 - 1) = 6을 최솟값으로 모든 파일을 선택 가능합니다.

• (0, 0)에서 (3, 5)로 드래그해도 모든 파일을 선택할 수 있지만 이때 드래그 한 거리는 (3 - 0) + (5 - 0) = 8이고 이전의 방법보다 거리가 늘어납니다.
• 머쓱이의 컴퓨터 바탕화면의 상태를 나타내는 문자열 배열 wallpaper가 매개변수로 주어질 때 바탕화면의 파일들을 한 번에 삭제하기 위해 최소한의 이동거리를 갖는 드래그의 시작점과 끝점을 담은 정수 배열을 return하는 solution 함수를 작성해 주세요. 드래그의 시작점이 (lux, luy), 끝점이 (rdx, rdy)라면 정수 배열 [lux, luy, rdx, rdy]를 return하면 됩니다.

제한사항

• 1 ≤ wallpaper의 길이 ≤ 50
• 1 ≤ wallpaper[i]의 길이 ≤ 50
  • wallpaper의 모든 원소의 길이는 동일합니다.
• wallpaper[i][j]는 바탕화면에서 i + 1행 j + 1열에 해당하는 칸의 상태를 나타냅니다.
• wallpaper[i][j]는 "#" 또는 "."의 값만 가집니다.
• 바탕화면에는 적어도 하나의 파일이 있습니다.
• 드래그 시작점 (lux, luy)와 끝점 (rdx, rdy)는 lux < rdx, luy < rdy를 만족해야 합니다.

wallpaper = ["..........", ".....#....", "......##..", "...##.....", "....#....."]
wallpaper1 = [".#...", "..#..", "...#."]
wallpaper2 = [".##...##.", "#..#.#..#", "#...#...#", ".#.....#.", "..#...#..", "...#.#...", "....#...."]

def solution(wallpaper):

    # 시작지점의 x,y point와
    # 끝지점의 x,y point를 각각 변수를 만들어 할당한다.
    s_y_point = len(wallpaper) # 시작지점의 x와 y에는 가장 끝 지점의 좌표를 입력
    s_x_point = len(wallpaper[0])
    e_y_point = 0 # 끝지점의 x와 y에는 0을 입력
    e_x_point = 0

    # 이중 포문으로 각 요소를 하나하나 살펴본다.
    for i in range(len(wallpaper)):
        for j in range(len(wallpaper[i])):

            # 만약 wallpaper[i][j]가 '#'이고 i가 s_y_point보다 작으면 
            if (wallpaper[i][j] == '#') and (i < s_y_point):
                # s_y_point에 i를 저장
                s_y_point = i
            # 만약 wallpaper[i][j]가 '#'이고 j가 s_x_point보다 작으면
            if (wallpaper[i][j] == '#') and (j < s_x_point):
                # s_x_point에 j를 저장
                s_x_point = j
            # 만약 wallpaper[i][j]가 '#'이고 i가 e_y_point보다 크면
            if (wallpaper[i][j] == '#') and (i > e_y_point):
                # e_y_point에 i를 저장
                e_y_point = i
            # 만약 wallpaper[i][j]가 '#'이고 j가 e_y_point보다 크면
            if (wallpaper[i][j] == '#') and (j > e_x_point):
                # e_x_point에 j를 저장
                e_x_point = j
    return [s_y_point, s_x_point, e_y_point+1,e_x_point+1]

print(solution(wallpaper))
print(solution(wallpaper1))
print(solution(wallpaper2))

# [1, 3, 5, 8]
# [0, 1, 3, 4]
# [0, 0, 7, 9]

다른 사람의 풀이

def solution(wall):
    
    # a와 b라는 빈 리스트를 만든다.
    a, b = [], []
    
    # wall안에있는 모든 문자열요소를 하나하나 살펴본다.
    for i in range(len(wall)):
        for j in range(len(wall[i])):
            
            # 만약 wall[i][j]가 '#'이면
            if wall[i][j] == "#":
                # 그 때의 i값을 a에 마지막 요소로 넣고
                a.append(i)
                # 그 때의 j값을 b에 마지막 요소로 넣는다.
                b.append(j)
    # 그리고 a의 최소값, b의 최소값, a의 최대값+1, b의 최대값 +1을 반환한다.
    return [min(a), min(b), max(a) + 1, max(b) + 1]

print(solution(wallpaper))
print(solution(wallpaper1))
print(solution(wallpaper2))

# [1, 3, 5, 8]
# [0, 1, 3, 4]
# [0, 0, 7, 9]

문제 설명

• 수웅이는 매달 주어진 음식을 빨리 먹는 푸드 파이트 대회를 개최합니다. 이 대회에서 선수들은 1대 1로 대결하며, 매 대결마다 음식의 종류와 양이 바뀝니다. 대결은 준비된 음식들을 일렬로 배치한 뒤, 한 선수는 제일 왼쪽에 있는 음식부터 오른쪽으로, 다른 선수는 제일 오른쪽에 있는 음식부터 왼쪽으로 순서대로 먹는 방식으로 진행됩니다. 중앙에는 물을 배치하고, 물을 먼저 먹는 선수가 승리하게 됩니다.
• 이때, 대회의 공정성을 위해 두 선수가 먹는 음식의 종류와 양이 같아야 하며, 음식을 먹는 순서도 같아야 합니다. 또한, 이번 대회부터는 칼로리가 낮은 음식을 먼저 먹을 수 있게 배치하여 선수들이 음식을 더 잘 먹을 수 있게 하려고 합니다. 이번 대회를 위해 수웅이는 음식을 주문했는데, 대회의 조건을 고려하지 않고 음식을 주문하여 몇 개의 음식은 대회에 사용하지 못하게 되었습니다.
• 예를 들어, 3가지의 음식이 준비되어 있으며, 칼로리가 적은 순서대로 1번 음식을 3개, 2번 음식을 4개, 3번 음식을 6개 준비했으며, 물을 편의상 0번 음식이라고 칭한다면, 두 선수는 1번 음식 1개, 2번 음식 2개, 3번 음식 3개씩을 먹게 되므로 음식의 배치는 "1223330333221"이 됩니다. 따라서 1번 음식 1개는 대회에 사용하지 못합니다.
• 수웅이가 준비한 음식의 양을 칼로리가 적은 순서대로 나타내는 정수 배열 food가 주어졌을 때, 대회를 위한 음식의 배치를 나타내는 문자열을 return 하는 solution 함수를 완성해주세요.

제한사항

• 2 ≤ food의 길이 ≤ 9
• 1 ≤ food의 각 원소 ≤ 1,000
• food에는 칼로리가 적은 순서대로 음식의 양이 담겨 있습니다.
• food[i]는 i번 음식의 수입니다.
• food[0]은 수웅이가 준비한 물의 양이며, 항상 1입니다.
• 정답의 길이가 3 이상인 경우만 입력으로 주어집니다.

food1 = [1, 3, 4, 6] # "1223330333221"
food2 = [1, 7, 1, 2] # "111303111"
food3 = [1, 3, 2, 3] # "1230123"

def solution(food):
    # 답을 넣을 asnwer을 만든다.
    answer = ''

    # enumerate를 사용하면 food의 각 요소와 해당요소의 인덱스 값을 반환한다.
    # 이때 맨 앞의 1은 물을 뜻하므로 0으로 무조건 반환해야 하기에 food[1:]로 빼고
    # for문을 돌린다. food1 = [1, 3, 4, 6] 을 예로 들면,
    # idx, num 값은 차례대로 (0,3),(1,4),(2,6)이 들어간다.
    for idx, num in enumerate(food[1:]):

        # num//2 range만큼 다시 for문을 돌린다.
        # 3, 4, 6 을 2로 나눈 몫 -> 1, 2, 3 range만큼 반복될 것이다.
        for i in range(num//2):

            # asnwer에 idx 즉 인덱스 값에 1을 더한 값을 집어 넣는다.
            # 1이 한번 2가 두번 3이 세번 들어갈 것이다.
            answer += str(idx+1)

    # anwer값에 0을 더한 후 answer를 반전시킨 문자열을 더한다.    
    return answer + '0'+answer[::-1]

print(solution(food1))
print(solution(food2))
print(solution(food3))

# 1223330333221
# 111303111
# 1230321

다른 사람의 풀이

def solution(food):
    # '0'을 가지고있는 문자열 answer을 만든다.
    answer ="0"
    
    # food의 길이-1부터 0까지 거꾸로 살펴보며 for문을 돌린다.
    # food1 = [1, 3, 4, 6] 을 예시로 들면 i에는 3, 2, 1이 차례대로 들어간다.
    for i in range(len(food)-1, 0,-1):
        
        # food의 i번째의 요소를 2로 나눈 후 int를 씌워주면 소수점이 날라간다.
        # 이 때 c에는 3, 2, 1 이 차례대로 할당된다.
        c = int(food[i]/2)
        
        # 각 c가 0이되면 멈추는 while문이다.
        while c>0:
            # 기존의 answer에 '0'이 있다.
            # 여기 앞과 뒤에 문자열 i를 넣은 값을 다시 answer에 할당한다.
            answer = str(i) + answer + str(i)
            # c에 1을 뺀 후 다시 while문을 돌린다.
            c -= 1
    return answer

print(solution(food1))
print(solution(food2))
print(solution(food3))

# 1223330333221
# 111303111
# 1230321

문제 설명

• 햄버거 가게에서 일을 하는 상수는 햄버거를 포장하는 일을 합니다. 함께 일을 하는 다른 직원들이 햄버거에 들어갈 재료를 조리해 주면 조리된 순서대로 상수의 앞에 아래서부터 위로 쌓이게 되고, 상수는 순서에 맞게 쌓여서 완성된 햄버거를 따로 옮겨 포장을 하게 됩니다. 상수가 일하는 가게는 정해진 순서(아래서부터, 빵 – 야채 – 고기 - 빵)로 쌓인 햄버거만 포장을 합니다. 상수는 손이 굉장히 빠르기 때문에 상수가 포장하는 동안 속 재료가 추가적으로 들어오는 일은 없으며, 재료의 높이는 무시하여 재료가 높이 쌓여서 일이 힘들어지는 경우는 없습니다.
• 예를 들어, 상수의 앞에 쌓이는 재료의 순서가 [야채, 빵, 빵, 야채, 고기, 빵, 야채, 고기, 빵]일 때, 상수는 여섯 번째 재료가 쌓였을 때, 세 번째 재료부터 여섯 번째 재료를 이용하여 햄버거를 포장하고, 아홉 번째 재료가 쌓였을 때, 두 번째 재료와 일곱 번째 재료부터 아홉 번째 재료를 이용하여 햄버거를 포장합니다. 즉, 2개의 햄버거를 포장하게 됩니다.
• 상수에게 전해지는 재료의 정보를 나타내는 정수 배열 ingredient가 주어졌을 때, 상수가 포장하는 햄버거의 개수를 return 하도록 solution 함수를 완성하시오.

제한사항

• 1 ≤ ingredient의 길이 ≤ 1,000,000
• ingredient의 원소는 1, 2, 3 중 하나의 값이며, 순서대로 빵, 야채, 고기를 의미합니다.

ingredient = [2, 1, 1, 2, 3, 1, 2, 3, 1]

def solution(ingredient):
    pack = True
    answer = 0
    result = 0

    # pack가 True일 때만 실행한다.
    while pack:

        # ingredient의 길이만큼 for문을 돌린다.
        for i in range(len(ingredient)):
            # 만약 ingredient[i:i+4] 값이 [1,2,3,1] 이면
            if ingredient[i:i+4] == [1,2,3,1]:
                # 해당 ingredient[i:i+4] 을 리스트에서 지워버리고
                del ingredient[i:i+4]
                # result에 1을 더한 후
                result += 1
                # 해당 i 인덱스에 0을 집어넣는다.
                ingredient.insert(i,0)

        # 그리고 answer와 result의 값이 같으면
        # 즉 더 [1,2,3,1]을 찾지 못하면
        if answer == result:   
            # pack를 False로 바꾸고 while문을 끝낸다.
            pack = False
        # 아니라면
        # 즉 [1,2,3,1]을 더 찾았다면
        elif answer != result:
            # ingredient에 넣은 0을 빼주고
            ingredient = [i for i in ingredient if i != 0]
            # result 값을 answer에 할당한다.
            answer = result

    return answer

    solution(ingredient)
    # 2

3~6, 9, 12문제에 계속 실패가 뜬다....결국 반례를 찾아보고 다른 사람의 풀이를 살펴보았다.

반례를 찾아보니

• 만약 ingredient가 [...1,2,1,2,3,1,3,1,....] 이라면
• 중간에 [...1,2,[1,2,3,1],3,1,....] 을 빼면 [...1,2,3,1,]이 또 만들어진다.
• 이때 또 만들어진 [1,2,3,1]을 찾아내야 되는데
• 위에 짠 코드에는 그냥 다음으로 넘어가 버린다.

# 위의 반례를 예시로 들어 아래의 ingredient 변수를 만든다.
ingredient = [1,1,2,2,3,1, 1,2, 1, 2, 3, 1, 3, 1, 2, 3, 1]
# 3이 나와야한다.

def solution(ingredient):
    answer = 0
    i = 0

    # i 가 ingredient의 길이보다 같거나 작은한 계속 while을 돌린다.
    while i <= len(ingredient):
        # 만약 ingredient[i:i+4]에 해당하는 리스트 값이 [1,2,3,1] 이면
        if ingredient[i:i+4] == [1,2,3,1]:
            # 해당 ingredient[i:i+4]을 ingredient에서 삭제한다.
            del ingredient[i:i+4]
            # answer에 1을 더한다.
            answer += 1
            # 그리고 i에 3을 뺀 값을 i에 저장한다.
            # 이때 i는 인덱스값으로 쓰이기에 3칸 만큼 뒤로 간다는 뜻이다
            i = i - 3
        # 그 후에 마치 for문을 돌리듯이 다음 i 인덱스를 살펴본다.
        i += 1

    return answer

    solution(ingredient)

    # 3

다른 사람의 풀이

ingredient = [1,1,2,2,3,1, 1,2, 1, 2, 3, 1, 3, 1, 2, 3, 1]

def solution(ingredient):
    
    # 리스트 s와 값이 0인 cnt를 만든다.
    s = []
    cnt = 0
    
    # ingredient의 요소 하나하나를 살펴보자.
    for i in ingredient:
        # 해당 i를 리스트 s에 마지막 요소로 집어넣는다.
        s.append(i)
        # 이때 만약 리스트 s의 맨 뒤에서 네번째 부터 맨 뒤의 요소가
        # [1, 2, 3, 1] 리스트의 값을 가지면
        if s[-4:] == [1, 2, 3, 1]:
            # cnt를 1 더해준고
            cnt += 1
            # pop()으로 s의 맨 마지막 요소를
            # 4번 반복하여 빼 낸다.
            for i in range(4):
                s.pop()
    return cnt
    
    solution(ingredient)
    
    # 3

문제 설명

• 과일 장수가 사과 상자를 포장하고 있습니다. 사과는 상태에 따라 1점부터 k점까지의 점수로 분류하며, k점이 최상품의 사과이고 1점이 최하품의 사과입니다. 사과 한 상자의 가격은 다음과 같이 결정됩니다.
  • 한 상자에 사과를 m개씩 담아 포장합니다.
  • 상자에 담긴 사과 중 가장 낮은 점수가 p (1 ≤ p ≤ k)점인 경우, 사과 한 상자의 가격은 p * m 입니다.
• 과일 장수가 가능한 많은 사과를 팔았을 때, 얻을 수 있는 최대 이익을 계산하고자 합니다.(사과는 상자 단위로만 판매하며, 남는 사과는 버립니다)
• 예를 들어, k = 3, m = 4, 사과 7개의 점수가 [1, 2, 3, 1, 2, 3, 1]이라면, 다음과 같이 [2, 3, 2, 3]으로 구성된 사과 상자 1개를 만들어 판매하여 최대 이익을 얻을 수 있습니다.
  • (최저 사과 점수) x (한 상자에 담긴 사과 개수) x (상자의 개수) = 2 x 4 x 1 = 8
• 사과의 최대 점수 k, 한 상자에 들어가는 사과의 수 m, 사과들의 점수 score가 주어졌을 때, 과일 장수가 얻을 수 있는 최대 이익을 return하는 solution 함수를 완성해주세요.

제한사항

• 3 ≤ k ≤ 9
• 3 ≤ m ≤ 10
• 7 ≤ score의 길이 ≤ 1,000,000
  • 1 ≤ score[i] ≤ k
• 이익이 발생하지 않는 경우에는 0을 return 해주세요.

# 에시 1
k = 4
m = 3
score = [4, 1, 2, 2, 4, 4, 4, 4, 1, 2, 4, 2]

# 예시 2
k1 = 3
m1 = 4
score1 = [1, 2, 3, 1, 2, 3, 1]

def solution(k, m, score):
    answer = 0

    # sorted함수를 사용해 score의 요소들을 내림차순 정렬한다.
    # 예시) [4, 4, 4, 4, 4, 4, 2, 2, 2, 2, 1, 1]
    sort_score = sorted(score,reverse=True)

    # for문을 돌려 sort_score를 m으로 나눈 몫 만큼의 범위만 반복한다.
    for i in range(len(sort_score)//m):
        # 만약 sort_score[i:i+m] 즉 i인덱스부터 m번째 뒤의 인덱스까지의 길이가
        # m 이라면
        if len(sort_score[i:i+m]) == m:
            # sort_score를 m개 씩 나눈 후 제일 작은 값을 찾아야 하므로
            # 각 i * m 번 째의 m-1뒤의 인덱스 부분만 사용한다.
            # 예시) [4, 4, 4, 4, 4, 4, 2, 2, 2, 2, 1, 1] ->
            # [4, 4, 2, 1] 을 사용한여 각 요소에 m을 곱한 후 answer에 더해준다.
            answer += sort_score[i*m+(m-1)] *m     
    return answer

print(solution(k, m, score))
print(solution(k1, m1, score1))

# 33
# 8

다른 사람의 풀이

def solution(k, m, score):
    return sum(sorted(score)[len(score)%m::m])*m
    
# 상당히 짧고 간결하다...

# 예시 1을 사용하자.
# sorted(score) -> [1, 1, 2, 2, 2, 2, 4, 4, 4, 4, 4, 4]
# len(score) = 12
# len(score)%m::m -> 12 % m::m -> 0부터 끝까지 step 4 -> [1, 2, 4, 4]
# 각 요소의 m을 곱해서 더하는 것 결국 모든 요소를 더한 후 m을 곱한것과 같다.
# sum(sorted(score)[len(score)%m::m])*m을 return

print(solution(k, m, score))
print(solution(k1, m1, score1))

# 33
# 8

문제 설명

• 휴대폰의 자판은 컴퓨터 키보드 자판과는 다르게 하나의 키에 여러 개의 문자가 할당될 수 있습니다. 키 하나에 여러 문자가 할당된 경우, 동일한 키를 연속해서 빠르게 누르면 할당된 순서대로 문자가 바뀝니다.
• 예를 들어, 1번 키에 "A", "B", "C" 순서대로 문자가 할당되어 있다면 1번 키를 한 번 누르면 "A", 두 번 누르면 "B", 세 번 누르면 "C"가 되는 식입니다.
• 같은 규칙을 적용해 아무렇게나 만든 휴대폰 자판이 있습니다. 이 휴대폰 자판은 키의 개수가 1개부터 최대 100개까지 있을 수 있으며, 특정 키를 눌렀을 때 입력되는 문자들도 무작위로 배열되어 있습니다. 또, 같은 문자가 자판 전체에 여러 번 할당된 경우도 있고, 키 하나에 같은 문자가 여러 번 할당된 경우도 있습니다. 심지어 아예 할당되지 않은 경우도 있습니다. 따라서 몇몇 문자열은 작성할 수 없을 수도 있습니다.
• 이 휴대폰 자판을 이용해 특정 문자열을 작성할 때, 키를 최소 몇 번 눌러야 그 문자열을 작성할 수 있는지 알아보고자 합니다.
• 1번 키부터 차례대로 할당된 문자들이 순서대로 담긴 문자열배열 keymap과 입력하려는 문자열들이 담긴 문자열 배열 targets가 주어질 때, 각 문자열을 작성하기 위해 키를 최소 몇 번씩 눌러야 하는지 순서대로 배열에 담아 return 하는 solution 함수를 완성해 주세요.
• 단, 목표 문자열을 작성할 수 없을 때는 -1을 저장합니다.

제한사항

• 1 ≤ keymap의 길이 ≤ 100
  • 1 ≤ keymap의 원소의 길이 ≤ 100
  • keymap[i]는 i + 1번 키를 눌렀을 때 순서대로 바뀌는 문자를 의미합니다.
    • 예를 들어 keymap[0] = "ABACD" 인 경우 1번 키를 한 번 누르면 A, 두 번 누르면 B, 세 번 누르면 A 가 됩니다.
  • keymap의 원소의 길이는 서로 다를 수 있습니다.
  • keymap의 원소는 알파벳 대문자로만 이루어져 있습니다.
• 1 ≤ targets의 길이 ≤ 100
  • 1 ≤ targets의 원소의 길이 ≤ 100
  • targets의 원소는 알파벳 대문자로만 이루어져 있습니다.

예시 모음

• 아래의 예시에서 하나를 정해 실행합니다.

keymap = ["ABACD", "BCEFD"]
targets = ["ABCD","AABB"]
# keymap = ["AA"]
# targets = ["B"]
# keymap = ["AGB", "BSSS"]
# targets = ["AGZ", "BSSS"]

def solution(keymap, targets):
    answer = []

    # key값은 알파벳을 value값은 0을 갖는 dict를 하나 만듭니다.
    alp_dict = {'A': 0,'B': 0,'C': 0,'D': 0,'E': 0,'F': 0,'G': 0,'H': 0,'I': 0,
 'J': 0,'K': 0,'L': 0,'M': 0,'N': 0,'O': 0,'P': 0,'Q': 0,'R': 0,'S': 0,'T': 0,'U': 0,'V': 0,'W': 0,'X': 0,'Y': 0,'Z': 0}

    # keymap의 요소를 살펴보며 가장 적은 탭으로
    # alp_dict의 key값에 해당하는 알파벳을 입력할 수 있는 탭 수를 alp_dict에 value 값으로 넣습니다.
    for k in alp_dict.keys():
        for test in keymap:
            if alp_dict[k] == 0:
                alp_dict[k] = test.find(k)+1 if test.find(k) != -1 else 0
            elif (test.find(k) != -1) and (alp_dict[k] >= test.find(k)+1):
                alp_dict[k] = test.find(k)+1 if test.find(k) != -1 else 0

    # targets의 요소 하나하나를 text로 할당해 살펴봅시다.
    for text in targets:

        # 리스트 내 for문으로 text의 요소 하나하나에 해당하는 alp_dict의 value 값을
        # result에 할당합니다.
        result = [alp_dict[k] for k in text]

        # 이때 result안의 요소 값이 하나라도 0이 들어가면
        if 0 in result:
            # 해당 글자를 만들 수 없으므로 answer에 -1 넣습니다.
            answer.append(-1)
        else:
            # 0이 없다면 result의 모든 요소를 합한 값을 answer에 넣습니다.
            answer.append(sum(result))


    return answer

print(solution(keymap, targets))
print(solution(keymap1, targets1))
print(solution(keymap2, targets2))

# [9, 4]
# [-1]
# [-1, 7]

다른 사람의 풀이

def solution(keymap, targets):
    answer = []
    
    
    # range(26) 즉 알파벳 갯수 만큼의 101을 리스로 만들어 alpha에 할당
    alpha = [101 for i in range(26)]
    
    # keymap의 요소 하나하나를 i에 할당하여 반복문을 돌린다.
    for i in keymap:
        # keymap의 요소 i를 enumerate로
        # 인덱스와 각 인덱스의 해당하는 값을 살펴본다.
        for idx, j in enumerate(i):
            # 'ABACD'를 i값으로 사용해 예시를들어보자.
            # enumerate('ABACD')에서
            # idx = 0, j = 'A'로 살펴보면
            # ord(j)-ord('A') = 0이 된다
            k = ord(j)-ord('A')
            # k는 0이므로 alpha[0]은 원래있던 alpha[0]과 idx+1의 값 중 최소값이
            # 들어가게 된다.
            alpha[k] = min(alpha[k],idx+1)
    
    # targets의 요소 하나하나를 i에 할당한다.
    # ex) i = 'ABCD'
    for i in targets:
        total = 0
        # i의 요소 하나하나를 j에 할당한다.
        # ex) j = 'A'
        for j in i:
            # ord(j) - ord('A') = 0 이므로 alpha[0] 값이 cnt로 할당.
            cnt = alpha[ord(j) - ord('A')]
            
            # cnt가 101이면
            if cnt ==101:
                # answer에 -1을 넣고 멈춘다.
                answer.append(-1)
                break
            # cnt가 101이 아니면
            else:
                # cnt의 값을 total에 더한다.
                total+= cnt
        else:
            # 그 후 total값을 answer에 할당한다.
            answer.append(total)



    return answer

print(solution(keymap, targets))
print(solution(keymap1, targets1))
print(solution(keymap2, targets2))

# [9, 4]
# [-1]
# [-1, 7]

문제 설명

• 숫자나라 기사단의 각 기사에게는 1번부터 number까지 번호가 지정되어 있습니다. 기사들은 무기점에서 무기를 구매하려고 합니다.
• 각 기사는 자신의 기사 번호의 약수 개수에 해당하는 공격력을 가진 무기를 구매하려 합니다. 단, 이웃나라와의 협약에 의해 공격력의 제한수치를 정하고, 제한수치보다 큰 공격력을 가진 무기를 구매해야 하는 기사는 협약기관에서 정한 공격력을 가지는 무기를 구매해야 합니다.
• 예를 들어, 15번으로 지정된 기사단원은 15의 약수가 1, 3, 5, 15로 4개 이므로, 공격력이 4인 무기를 구매합니다. 만약, 이웃나라와의 협약으로 정해진 공격력의 제한수치가 3이고 제한수치를 초과한 기사가 사용할 무기의 공격력이 2라면, 15번으로 지정된 기사단원은 무기점에서 공격력이 2인 무기를 구매합니다. 무기를 만들 때, 무기의 공격력 1당 1kg의 철이 필요합니다. 그래서 무기점에서 무기를 모두 만들기 위해 필요한 철의 무게를 미리 계산하려 합니다.
• 기사단원의 수를 나타내는 정수 number와 이웃나라와 협약으로 정해진 공격력의 제한수치를 나타내는 정수 limit와 제한수치를 초과한 기사가 사용할 무기의 공격력을 나타내는 정수 power가 주어졌을 때, 무기점의 주인이 무기를 모두 만들기 위해 필요한 철의 무게를 return 하는 solution 함수를 완성하시오.

제한사항

• 1 ≤ number ≤ 100,000
• 2 ≤ limit ≤ 100
• 1 ≤ power ≤ limit

number = 5
limit = 3
power = 2
# 결과는 10이 나와야 한다.
number1 = 10
limit1 = 3
power1 = 2
# 결과는 21이 나와야 한다.

def solution(number, limit, power):
    # 결과를 출력할 answer을 만든다
    answer = 0

    # number의 범위 안에 있는 모든 수의 약수를 구해야 한다.
    # range를 사용해 for문을 돌린다.
    for num in range(1,number+1):
        # 두 임의의 리스트를 만든다.
        divisors = []
        divisors_back = []

        # number까지의 범위 중 한 수인 num의 약수를 구한다.
        # 이때 num이 아주 큰 수 이면 약수를 구할때 시간복잡도가 커진다.
        # 그래서 해당 수의 제곱근의 약수를 구한다.
        for i in range(1, int(num**(1/2)) +1):
            # 만약 num범위의 수들 중 나눠서 나머지가 0이되는 수 i를
            if num % i == 0:
                # divisors에 마지막 요소로 집어 넣는다.
                divisors.append(i)
                # 이때 num을 i로 나눈 후 몫이 i랑 같지 않으면
                if i != (num//i):
                    # divisors_back에 그 몫 값을 마지막 요소로 집어 넣는다.
                    divisors_back.append(num//i)

        # 그 후 divisors와 divisors_back[::-1]을 더하면 해당 수의 약수가 된다.
        # 위 제곱근을 사용하는 방법을 아래에서 자세히 다루도록 하자.

        # 만약 divisors + divisors_back[::-1]의 길이가 limit보다 길다면
        # 즉 기사단원의 공격력이 limit보다 크다면
        if len(divisors + divisors_back[::-1]) > limit:
            # answer에 power값을 더해 주고
            answer += power
        # 그렇지 않다면
        # 즉, 기사단원의 공격력이 limit보다 같거나 작다면
        else:
            # answer에 divisors + divisors_back[::-1]의 길이 값을 더해 준다.
            answer += len(divisors + divisors_back[::-1])
    return answer

print(solution(number, limit, power))
print(solution(number1, limit1, power1))

# 10
# 21

약수 구하는 법

# 100의 약수를 구해보자.

# 약수를 구할 100을 n에 할당한다.
n = 100

# 약수를 집어넣을 divisors와 divisors_back 리스트를 만든다.
divisors = []
divisors_back = [] 

# for문을 돌려 n의 제곱근의 범위 만큼 i를 할당한다.
# 여기서 아래의 for문은 `for i in range(1, 11):` 과 같다.
for i in range(1, int(n**(1/2)) + 1):

    # i는 1,2,3,4,5,6,7,8,9,10 의 값들이 하나하나 들어간다.
    # 위 값들 중 n 즉, 100을 나눴을 때 나머지가 0이 되는 값들은
    if (n % i == 0):
        # divisors에 마지막 요소로 들어간다.
        # 여기서는 1, 2, 4, 5, 10 이 100을 나눴을 때 나머지가 0이 되므로
        # divisors에 들어갈 값은 1, 2, 4, 5, 10이다.
        divisors.append(i)

        # divisors에 들어갈 i값들 중
        # 만약 n 즉 100을 i로 나눈 후 몫의 값이 i와 같지 않다면
        if (i != (n // i)): 
            # 100을 i로 나눈 후 몫의 값을 divisors_back에 마지막 요소로 집어 넣는다.
            divisors_back.append(n//i)
        # 위 if 문을 하는 이유는
        # 만약 i값이 1, 2, 4, 5, 10중에 하나인 10이라고 가정해 보자
        # n값인 100을 10으로 나눈 후 몫의 값은 10이다.
        # 즉 i값과 n//i 값이 같은 경우이다.
        # divisors_back에 10이 들어가게 되면
        # divisors와 divisors_back 두 리스트 모두 10 값을 갖게 된다.
        # 그 후 divisors와 divisors_back[::-1]을 합하면
        # [1, 2, 4, 5, 10, 10, 20, 25, 50, 100] 처럼 10이 중복으로 들어가게 된다.
        # 이때 set으로 중복을 제거해주는 방법도 있지만
        # 이 경우에서 아예 중복되는 값을 집어넣지 않은 경우이다.

# divisors와 divisors_back[::-1]을 더하면 100의 약수들이 출력된다.
divisors + divisors_back[::-1]

# [1, 2, 4, 5, 10, 20, 25, 50, 100]

다른 사람의 풀이

# 함수 cf는 n의 약수의 개수를 출력해주는 함수이다.
def cf(n):
    
    # 리스트 a변수를 만든다.
    a = []
    
    # n의 제곱근의 범위 만큼만 for문을 돌린다.
    for i in range(1,int(n**0.5)+1):
        # n을 i로 나눈 나머지 값이 0이면
        if n%i == 0:
            # i값과 n을 i로 나눈 몫값을 a에 마지막 요소로 집어 넣는다.
            a.append(n//i)
            a.append(i)
    # 그 후 set을 사용해 a에 중복 요소를 제거한 후 그 길이를 return한다.
    return len(set(a))
 
def solution(number, limit, power):
    # if를 같이 사용한 리스트 내 for문으로 바로 return한다.
    # 1부터 number안의 정수들을 함수 cf(i)로 출력된 값만 리스트로 집어 넣는다
    # 단 limit 이하인 cf(i) 값만 그대로 집어 넣고
    # limit 초과인 cf(i)값은 cf(i)값 대신 power값을 집어넣는다.
    # 그 후 리스트 내의 모든 요소를 다 더한 값을 출력한다.
    return sum([cf(i) if cf(i)<=limit else power for i in range(1,number+1)])

print(solution(number, limit, power))
print(solution(number1, limit1, power1))

# 10
# 21