통계러버

문제 링크 

• 더 맵게

문제 설명

섞은 음식의 스코빌 지수 = 가장 맵지 않은 음식의 스코빌 지수 + (두 번째로 맵지 않은 음식의 스코빌 지수 * 2)

입출력 예 설명

1. 스코빌 지수가 1인 음식과 2인 음식을 섞으면 음식의 스코빌 지수가 아래와 같이 됩니다.
   새로운 음식의 스코빌 지수 = 1 + (2 * 2) = 5
   가진 음식의 스코빌 지수 = [5, 3, 9, 10, 12]
2. 스코빌 지수가 3인 음식과 5인 음식을 섞으면 음식의 스코빌 지수가 아래와 같이 됩니다.
   새로운 음식의 스코빌 지수 = 3 + (5 * 2) = 13
   가진 음식의 스코빌 지수 = [13, 9, 10, 12]

모든 음식의 스코빌 지수가 7 이상이 되었고 이때 섞은 횟수는 2회입니다.

힙

힙(heaps)

• 성질 : 최대/최소 원소를 빠르게 찾을 수 있음.
• 연산
     *   힙 구성(heapify) : O(NlogN)      # 삽입을 N번 하는 꼴로 이해하자.
     *   삽입(insert) : O(logN) : 삽입후에도 log에 비례하는 시간복잡도를 사용해서 min heap(or max heap)구조를 유지하도록 함.
    *   삭제(remove) : O(logN) : 삭제후에도 log에 비례하는 시간복잡도를 사용해서 min heap(or max heap)구조를 유지하도록 함.

코드

sol1)  min_heap을 이용한 우선순위 큐

def solution(scoville, K):
    import heapq as hq
    min_heap = []
    for i in scoville:
        hq.heappush(min_heap, i)                 #O(NlogN)
        
    cnt = 0    
    while min_heap[0] < K and len(min_heap)>1 :  # 힙구조가 되면 가장 처음값은 최솟값이 됨
        fist_min = hq.heappop(min_heap)
        second_min = hq.heappop(min_heap)
        new_sco = fist_min + second_min*2
        hq.heappush(min_heap, new_sco)
        cnt += 1
    return -1 if min_heap[0] < K else cnt

sol2) 

hq.heapify()를 이용하여 리스트를 min heap 형태(맨 앞이 항상 최솟값이 오게 됨)로 바꿔서 푸는 풀이

• hq.heapify() : 리스트를 min heap형태로 바꿈. 시간복잡도: O(logN)
• 주의! min_heap = hq.heapify(scoville) 이렇게 객체로 받아주면 안됨! 오류남

def solution(scoville, K):
    import heapq as hq
    hq.heapify(scoville)  # 리스트 scoville를 min heap으로 바꿈 
        
    cnt = 0    
    while scoville[0] < K and len(scoville)>1 :  # 힙구조가 되면 가장 처음 나오는 값은 최솟값이 됨
        fist_min = hq.heappop(scoville)
        second_min = hq.heappop(scoville)
        new_sco = fist_min + second_min*2
        hq.heappush(scoville, new_sco)
        cnt += 1
    return -1 if scoville[0] < K else cnt

sol3)

def solution(scoville, K):
    import heapq as hq
    hq.heapify(scoville)  # 리스트 scoville를 min heap으로 바꿈   O(logN)
     
    cnt = 0    
    while True:  # O(nlogn)
        fist_min = hq.heappop(scoville)  #O(logn)
        if fist_min >= K:
            break
        elif len(scoville) == 0:
            cnt = -1
            break      
        second_min = hq.heappop(scoville)  #O(logn)
        new_sco = fist_min + second_min*2
        hq.heappush(scoville, new_sco)
        cnt += 1
    return cnt

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

문제 링크

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

문제 설명

어떤 숫자에서 k개의 수를 제거했을 때 얻을 수 있는 가장 큰 숫자를 구하려 합니다.

탐욕법인 이유

• 앞 단계에서의 선택(앞자리에 큰수)이 이후 단계에서의 동작에 의한 해(solution)의 최적성(optimality)에 영향을 주지 않음

솔루션

주어진 숫자(number)에서 왼쪽부터 하나씩 꺼내어 모으되,

1. 이때, 이미 모아둔 것 중 지금 등장하는 것보다 작은 것들은 빼낸다.
2. 단, 이때 유효한 숫자를 모두 소진할 때 까지만 뺀다.
3. 아직 뺄 개수(k)를 채우지 못한 경우 뒤에서 부터 남은 자리수만큼 뺀다.

코드

sol1) 스택을 이용한 풀이

def solution(number, k):
    stack = [number[0]]
    for num in number[1:]:
        while len(stack) > 0 and stack[-1] < num and k > 0: # 파이썬에서 문자열의 대소관계는 아스키 코드를 따라 간다. 이를 이용하면 문자열로 된 숫자를 대소비교히면 숫자일때의 대소 비교때와 같아진다.
            k -= 1
            stack.pop()
        stack.append(num)
    if k != 0:   # while문을 다 돌았는데 k가 0이 아니면 뒤에서부터 pop한다
        stack = stack[:-k]
    return ''.join(stack)

sol2) 스택을 이용한 풀이2

def solution(number, k):
    stack = []
    for x in number:
        while stack and k >0 and stack[-1] < x:  # 파이썬에서 문자열의 대소관계는 아스키 코드를 따라 간다. 이를 이용하면 문자열로 된 숫자를 대소비교히면 숫자일때의 대소 비교때와 같아진다.
            stack.pop()
            k -= 1
        stack.append(x) # 맨 처음에는 stack이 비어있으므로 while문 돌지 않고 x부터 append함
    if k!=0:
        stack = stack[:-k]
    res = ''.join(map(str, stack))  
    return res

sol3) 스택과 큐를 이용한 풀이

from collections import deque
def solution(number, k):
    cnt = 0
    q= deque(number)
    sol = []
    sol.append(q.popleft()) #number의 첫글자를 stack에 넣고 시작
    while q:
        x = q.popleft()
        while sol and x > sol[-1] and cnt !=k:  # 스택의 맨위 글자와 큐의 왼쪽 첫번째 글자를 비교해서 스택의 맨위 글자가 더 작으면 크거나 같아 질때까지 스택의 맨 위 글자를 pop한다. 이 때 pop을하다 pop의 숫자가 k가 되면 멈춘다
                                                # 또한, 스택이 비어있으면 pop을 못하므로 비게 되면 멈춘다
                                                #  파이썬에서 문자열의 대소관계는 아스키 코드를 따라 간다. 이를 이용하면 문자열로 된 숫자를 대소비교히면 숫자일때의 대소 비교때와 같아진다.
            sol.pop()
            cnt +=1 
        sol.append(x)                           
        while (not q) and (cnt != k) :         #만약 q의 원소를 모두 썼는데 cnt에 도달 못했으면 도달할때까지 뒤에서부터 빼냄
            sol.pop()
            cnt +=1
    return ''.join(sol)

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

문제 링크

• 최솟값 만들기

문제 설명

길이가 같은 배열 A, B 두개가 있습니다. 각 배열은 자연수로 이루어져 있습니다.
배열 A, B에서 각각 한 개의 숫자를 뽑아 두 수를 곱합니다. 이러한 과정을 배열의 길이만큼 반복하며, 두 수를 곱한 값을 누적하여 더합니다. 이때 최종적으로 누적된 값이 최소가 되도록 만드는 것이 목표입니다. (단, 각 배열에서 k번째 숫자를 뽑았다면 다음에 k번째 숫자는 다시 뽑을 수 없습니다.)

예를 들어 A = [1, 4, 2] , B = [5, 4, 4] 라면

• A에서 첫번째 숫자인 1, B에서 첫번째 숫자인 5를 뽑아 곱하여 더합니다. (누적된 값 : 0 + 5(1x5) = 5)
• A에서 두번째 숫자인 4, B에서 세번째 숫자인 4를 뽑아 곱하여 더합니다. (누적된 값 : 5 + 16(4x4) = 21)
• A에서 세번째 숫자인 2, B에서 두번째 숫자인 4를 뽑아 곱하여 더합니다. (누적된 값 : 21 + 8(2x4) = 29)

즉, 이 경우가 최소가 되므로 29를 return 합니다.

배열 A, B가 주어질 때 최종적으로 누적된 최솟값을 return 하는 solution 함수를 완성해 주세요.

제한사항

• 배열 A, B의 크기 : 1,000 이하의 자연수
• 배열 A, B의 원소의 크기 : 1,000 이하의 자연수

입출력 예

입출력 예 설명

입출력 예 #1
문제의 예시와 같습니다.

입출력 예 #2
A에서 첫번째 숫자인 1, B에서 두번째 숫자인 4를 뽑아 곱하여 더합니다. (누적된 값 : 4) 다음, A에서 두번째 숫자인 2, B에서 첫번째 숫자인 3을 뽑아 곱하여 더합니다. (누적된 값 : 4 + 6 = 10)
이 경우가 최소이므로 10을 return 합니다.

솔루션

⇒ A의 가장 작은 값과 B의 가장 큰 값을 순서대로 곱해서 더하는 형태

⇒ A와 B를 하나는 오름차순, 하나는 내림차순으로 정렬한 후 각 원소끼리 곱해서 더하자

코드

sol1

def solution(A,B):
    n = len(A)
    A = sorted(A)
    B = sorted(B, reverse = True)
    answer = 0
    for i in range(n):
        answer += A[i]*B[i]
    return answer

sol2

def solution(A,B):
    return sum(a*b for a, b in zip(sorted(A), sorted(B, reverse = True)))

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

문제 링크

• 기능개발

문제 설명

프로그래머스 팀에서는 기능 개선 작업을 수행 중입니다. 각 기능은 진도가 100%일 때 서비스에 반영할 수 있습니다.

또, 각 기능의 개발속도는 모두 다르기 때문에 뒤에 있는 기능이 앞에 있는 기능보다 먼저 개발될 수 있고, 이때 뒤에 있는 기능은 앞에 있는 기능이 배포될 때 함께 배포됩니다.

먼저 배포되어야 하는 순서대로 작업의 진도가 적힌 정수 배열 progresses와 각 작업의 개발 속도가 적힌 정수 배열 speeds가 주어질 때 각 배포마다 몇 개의 기능이 배포되는지를 return 하도록 solution 함수를 완성하세요.

제한 사항

• 작업의 개수(progresses, speeds배열의 길이)는 100개 이하입니다.
• 작업 진도는 100 미만의 자연수입니다.
• 작업 속도는 100 이하의 자연수입니다.
• 배포는 하루에 한 번만 할 수 있으며, 하루의 끝에 이루어진다고 가정합니다. 예를 들어 진도율이 95%인 작업의 개발 속도가 하루에 4%라면 배포는 2일 뒤에 이루어집니다.

입출력 예

입출력 예 설명

입출력 예 #1
첫 번째 기능은 93% 완료되어 있고 하루에 1%씩 작업이 가능하므로 7일간 작업 후 배포가 가능합니다.
두 번째 기능은 30%가 완료되어 있고 하루에 30%씩 작업이 가능하므로 3일간 작업 후 배포가 가능합니다. 하지만 이전 첫 번째 기능이 아직 완성된 상태가 아니기 때문에 첫 번째 기능이 배포되는 7일째 배포됩니다.
세 번째 기능은 55%가 완료되어 있고 하루에 5%씩 작업이 가능하므로 9일간 작업 후 배포가 가능합니다.

따라서 7일째에 2개의 기능, 9일째에 1개의 기능이 배포됩니다.

입출력 예 #2
모든 기능이 하루에 1%씩 작업이 가능하므로, 작업이 끝나기까지 남은 일수는 각각 5일, 10일, 1일, 1일, 20일, 1일입니다. 어떤 기능이 먼저 완성되었더라도 앞에 있는 모든 기능이 완성되지 않으면 배포가 불가능합니다.

따라서 5일째에 1개의 기능, 10일째에 3개의 기능, 20일째에 2개의 기능이 배포됩니다.

코드

def solution(progress, speeds):
    import math
    from collections import deque
    q = deque()
    answer = []
    for i in range(len(progress)):
        q.append(math.ceil((100 - progress[i])/speeds[i]))

    while q:
        a = q.popleft()
        cnt = 1
        for _ in range(len(q)): 
            if a >= q[0]:
                q.popleft()
                cnt += 1
            else:
                break   
        answer.append(cnt)  
    return answer

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

문제링크

• 게임 맵 최단거리

문제설명

ROR 게임은 두 팀으로 나누어서 진행하며, 상대 팀 진영을 먼저 파괴하면 이기는 게임입니다. 따라서, 각 팀은 상대 팀 진영에 최대한 빨리 도착하는 것이 유리합니다.

지금부터 당신은 한 팀의 팀원이 되어 게임을 진행하려고 합니다. 다음은 5 x 5 크기의 맵에, 당신의 캐릭터가 (행: 1, 열: 1) 위치에 있고, 상대 팀 진영은 (행: 5, 열: 5) 위치에 있는 경우의 예시입니다.

위 그림에서 검은색 부분은 벽으로 막혀있어 갈 수 없는 길이며, 흰색 부분은 갈 수 있는 길입니다. 캐릭터가 움직일 때는 동, 서, 남, 북 방향으로 한 칸씩 이동하며, 게임 맵을 벗어난 길은 갈 수 없습니다. 아래 예시는 캐릭터가 상대 팀 진영으로 가는 두 가지 방법을 나타내고 있습니다.

첫 번째 방법은 11개의 칸을 지나서 상대 팀 진영에 도착했습니다.

두 번째 방법은 15개의 칸을 지나서 상대팀 진영에 도착했습니다.

위 예시에서는 첫 번째 방법보다 더 빠르게 상대팀 진영에 도착하는 방법은 없으므로, 이 방법이 상대 팀 진영으로 가는 가장 빠른 방법입니다.

만약, 상대 팀이 자신의 팀 진영 주위에 벽을 세워두었다면 상대 팀 진영에 도착하지 못할 수도 있습니다. 예를 들어, 다음과 같은 경우에 당신의 캐릭터는 상대 팀 진영에 도착할 수 없습니다.

게임 맵의 상태 maps가 매개변수로 주어질 때, 캐릭터가 상대 팀 진영에 도착하기 위해서 지나가야 하는 칸의 개수의 최솟값을 return 하도록 solution 함수를 완성해주세요. 단, 상대 팀 진영에 도착할 수 없을 때는 -1을 return 해주세요.

제한사항

• maps는 n x m 크기의 게임 맵의 상태가 들어있는 2차원 배열로, n과 m은 각각 1 이상 100 이하의 자연수입니다.
  • n과 m은 서로 같을 수도, 다를 수도 있지만, n과 m이 모두 1인 경우는 입력으로 주어지지 않습니다.
• maps는 0과 1로만 이루어져 있으며, 0은 벽이 있는 자리, 1은 벽이 없는 자리를 나타냅니다.
• 처음에 캐릭터는 게임 맵의 좌측 상단인 (1, 1) 위치에 있으며, 상대방 진영은 게임 맵의 우측 하단인 (n, m) 위치에 있습니다.

입출력 예

입출력 예 설명

예제 #1
주어진 데이터는 다음과 같습니다.

캐릭터가 적 팀의 진영까지 이동하는 가장 빠른 길은 다음 그림과 같습니다.

따라서 총 11칸을 캐릭터가 지나갔으므로 11을 return 하면 됩니다.

예제 #2

문제의 예시와 같으며, 상대 팀 진영에 도달할 방법이 없습니다. 따라서 -1을 return 합니다.

코드

def bfs(maps):
    from collections import deque
    n=len(maps)
    m =len(maps[0])
    visit = [[False]*m for _ in range(n)]
    
    dx = [-1,1,0,0]
    dy = [0,0,-1,1]
    
    
    q = deque()
    q.append((0,0,1))
    visit[0][0] = True
    while q:
        y, x, d =q.popleft()
        if y == n-1 and x == m-1:
            return d
        else:
            for k in range(4):
                nx = x+dx[k]
                ny = y+dy[k]
                if (0 <= nx < m) and (0 <= ny <n) and (visit[ny][nx] == False) and (maps[ny][nx] ==1):
                    q.append((ny,nx,d+1))
                    visit[ny][nx] = True
    return -1


def solution(maps):
    sol = bfs(maps)
    return sol

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

문제링크

• 타겟 넘버

문제 설명

n개의 음이 아닌 정수들이 있습니다. 이 정수들을 순서를 바꾸지 않고 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다. 예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들려면 다음 다섯 방법을 쓸 수 있습니다.

-1+1+1+1+1 = 3
+1-1+1+1+1 = 3
+1+1-1+1+1 = 3
+1+1+1-1+1 = 3
+1+1+1+1-1 = 3

사용할 수 있는 숫자가 담긴 배열 numbers, 타겟 넘버 target이 매개변수로 주어질 때 숫자를 적절히 더하고 빼서 타겟 넘버를 만드는 방법의 수를 return 하도록 solution 함수를 작성해주세요.

제한 사항

• 주어지는 숫자의 개수는 2개 이상 20개 이하입니다.
• 각 숫자는 1 이상 50 이하인 자연수입니다.
• 타겟 넘버는 1 이상 1000 이하인 자연수입니다.

입출력 예

입출력 예 설명

입출력 예 #1

문제 예시와 같습니다.

입출력 예 #2

+4+1-2+1 = 4
+4-1+2-1 = 4

• 총 2가지 방법이 있으므로, 2를 return 합니다.

코드

DFS 풀이

def dfs(i, numbers, target, tot):
    global cnt
    n = len(numbers)
    if i== n:
        if tot == target:
            cnt += 1
            
    else:
        dfs(i+1, numbers, target, tot + numbers[i])
        dfs(i+1, numbers, target, tot + numbers[i]*(-1))
            
def solution(numbers, target):
    global cnt
    cnt = 0
    dfs(0,numbers, target, 0)
    return cnt

중복순열

• 중복조합은 from itertools import combinations_with_replacement를 쓰는 반면 중복순열은 from itertools import product를 쓴다
• combinations_with_replacement(뽑을 곳, 반복횟수)을 써주기만 하면 되는 반면 product(뽑을 곳, repeat = 반복횟수)임 만약 product에서 repeat을 안쓰면 오류가 뜸 

ex)

from itertools import combinations_with_replacement

li = [1,2]
for com in combinations_with_replacement(li, 2):
    print(com)

>>>(1, 1)
   (1, 2)
   (2, 2)

from itertools import product

li = [1,2]
for pro in product(li,2):
    print(pro)

>>> TypeError

from itertools import product

li = [1,2]
for pro in product(li,repeat = 2):
    print(pro)

>>> (1, 1)
    (1, 2)
    (2, 1)
    (2, 2)

중복순열을 이용한 풀이

def solution(numbers, target):
    from itertools import product
    w = [-1,1]
    n = len(numbers)
    cnt = 0
    for per in  product(w, repeat = n):
        sol = 0
        for i in range(n):
            sol += per[i]*numbers[i]
        if sol == target:
            cnt +=1
    return cnt

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

문제링크

• JadenCase 문자열 만들기

문제 설명

JadenCase란 모든 단어의 첫 문자가 대문자이고, 그 외의 알파벳은 소문자인 문자열입니다. 단, 첫 문자가 알파벳이 아닐 때에는 이어지는 알파벳은 소문자로 쓰면 됩니다. (첫 번째 입출력 예 참고)
문자열 s가 주어졌을 때, s를 JadenCase로 바꾼 문자열을 리턴하는 함수, solution을 완성해주세요.

제한조건

• s는 길이 1 이상 200 이하인 문자열입니다.
• s는 알파벳과 숫자, 공백문자(" ")로 이루어져 있습니다.
  • 숫자는 단어의 첫 문자로만 나옵니다.
  • 숫자로만 이루어진 단어는 없습니다.
  • 공백문자가 연속해서 나올 수 있습니다.

입출력 예

참고

https://kmsstat01.tistory.com/entry/stringsplit

‘문자열’.upper() 혹은 ‘문자열’.lower()는 ‘숫자’에 적용될 경우 그대로 나옴. 따라서 위 문제의 조건을 따로 고려하지 않아도 됨. 주의! upper 혹은 lower 뒤에 ()를 안하면 값이 생성되지 않으므로 꼭 ()를 뒤에 붙이자
ex) '1b'.upper() >>> ‘1B’ , '1B'.upper() >>> ‘1b’

코드

def solution(s):
    sol = []
    li = s.split(' ')  # 문자열을 split(' ')하면 공백을 기준으로 잘라서 리스트로 만든다. 이때 공백이 연속으로 있으면 공백의 수 -1 개의 ''이 리스트의 원소가 됨
    for k in li:
        
        if  k == '':    # 공백이 두개 이상 연속으로 있을 경우 리스트의 원소중에 ''이 있을 것. 이를 고려해야함
            sol.append(k)
        else:
            sol.append(k[0].upper() +k[1:].lower())   # '문자열'.upper()는 '숫자'.upper()을 할 경우에도 에러 없이 그대로 출력함 
    return(' '.join(sol))

아래의 코드는 하드코드이므로 비추천함....

def solution(s):
    sol = []
    li = s.split(' ')  # 문자열을 split(' ')하면 공백을 기준으로 잘라서 리스트로 만든다. 이때 공백이 연속으로 있으면 공백의 수 -1 개의 ''이 리스트의 원소가 됨
    for i in li:
        if i == '':     # 공백이 두개 이상 연속으로 있을 경우 리스트의 원소중에 ''이 있을 것. 이를 고려해야함
            w = ''
        else:
            w = ''    
            for j in range(len(i)):
                if i[0]  in 'abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ' :
                    if j ==0:
                        w = w + i[0].upper()
                    else:    
                        w = w + i[j].lower()
                else:
                    if j == 0:
                        w = w + i[0]
                    else:    
                        w = w + i[j].lower()
        sol.append(w)

    return(' '.join(sol))

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

문제 링크

• N개의 최소공배수

문제 설명

두 수의 최소공배수(Least Common Multiple)란 입력된 두 수의 배수 중 공통이 되는 가장 작은 숫자를 의미합니다. 예를 들어 2와 7의 최소공배수는 14가 됩니다. 정의를 확장해서, n개의 수의 최소공배수는 n 개의 수들의 배수 중 공통이 되는 가장 작은 숫자가 됩니다. n개의 숫자를 담은 배열 arr이 입력되었을 때 이 수들의 최소공배수를 반환하는 함수, solution을 완성해 주세요.

제한사항

• arr은 길이 1이상, 15이하인 배열입니다.
• arr의 원소는 100 이하인 자연수입니다.

입출력 예

풀이

• 최대공약수는 math 라이브러리에서 gcd함수를 사용하면 됨
• 최소공배수는 두값을 곱하고 최대 공약수로 나누었을 때의 값임. 주의! math 라이브러이에서 gcd는 정수값만 읽음 하지만 나눗셈을 하면 float이 되므로 int값으로 바꿔줘야함
• 3개의 수에 대한 최대공약수는 두개에 대한 최대공약수와 나머지 수 사이에 다시 최대공약수를 구하면 됨
• 3개의 수에 대한 최소공배수는 두개에 대한 최소공배수와 나머지 수 사이에 다시 최소공배수를 구하면 됨

코드

sol1)  최대 공약수를 함수로 만들어서 푸는 풀이

# N개의 최소공배수

def gcd(x,y):
    while x!= 0:
        y , x = x , y%x   # 주의!     y = x
                          #           x = y%x  이렇게 두줄로 쓰면 오답이 나옴. 그 이유는 위에서 할당된 y가 밑에서 적용되기 때문에
    return y    

def lcm(x,y):
    return int(x*y/gcd(x,y))

def solution(arr):
    m = arr.pop()
    n = arr.pop()
    
    l_c_m = lcm(m,n)
    while arr:
        l_c_m = lcm(l_c_m, arr.pop())
    return l_c_m

sol2)  math함수를 이용한 풀이

from math import gcd


def solution(num):      
    answer = num[0]
    for n in num:
        answer = int(n * answer / gcd(n, answer))

    return answer

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