문제1) 등수매기기 - index, sorted 내림차순 사용
영어 점수와 수학 점수의 평균 점수를 기준으로 학생들의 등수를 매기려고 합니다. 영어 점수와 수학 점수를 담은 2차원 정수 배열 score가 주어질 때, 영어 점수와 수학 점수의 평균을 기준으로 매긴 등수를 담은 배열을 return하도록 solution 함수를 완성해주세요.
제한사항
0 ≤ score[0], score[1] ≤ 100
1 ≤ score의 길이 ≤ 10
score의 원소 길이는 2입니다.
score는 중복된 원소를 갖지 않습니다.
입출력 예
| score | result |
| [[80, 70], [90, 50], [40, 70], [50, 80]] | [1, 2, 4, 3] |
| [[80, 70], [70, 80], [30, 50], [90, 100], [100, 90], [100, 100], [10, 30]] | [4, 4, 6, 2, 2, 1, 7] |
입출력 예 설명
입출력 예 #1
평균은 각각 75, 70, 55, 65 이므로 등수를 매겨 [1, 2, 4, 3]을 return합니다.
입출력 예 #2
평균은 각각 75, 75, 40, 95, 95, 100, 20 이므로 [4, 4, 6, 2, 2, 1, 7] 을 return합니다.
공동 2등이 두 명, 공동 4등이 2명 이므로 3등과 5등은 없습니다.
풀이)
def solution(score):
## 리스트 컨프리헨션으로 평균리스트 구함
avg_list = [(x[0]+x[1])/2 for x in score]
## 내림차순으로 정렬하여 순위 구한 후 평균리스트에서 해당 값의 인덱스를 넣어 새로운 리스트를 만든다.
## sorted는 원본이 변하지 않고 정렬한값을 새로운 변수에 저장한다.
answer = [sorted(avg_list,reverse=True).index(x)+1 for x in avg_list]
return answer
시간복잡도:
avg_list를 만드는데 발생하는 시간은 O(n)입니다. 정렬과 요소값을 찾아서 새로운 리스트를 반환한 후 인덱스값을 찾는 작업도 O(n) 시간이 발생합니다. 그런데 avg_list를 반복하면서 매번 인덱스값을 찾는 작업을 반복하므로 O(n^2)이 됩니다.
공간복잡도:
avg_list를 생성하는데 O(n)공간이 필요하며, answer리스트도 1차원 리스트이므로 O(n)공간이 필요합니다. 따라서 총 공간복잡도는 O(n)이 됩니다.
문제2) 치킨 쿠폰 -> 특정한 비율을 무한으로 더하기(근사치 사용)
프로그래머스 치킨은 치킨을 시켜먹으면 한 마리당 쿠폰을 한 장 발급합니다. 쿠폰을 열 장 모으면 치킨을 한 마리 서비스로 받을 수 있고, 서비스 치킨에도 쿠폰이 발급됩니다. 시켜먹은 치킨의 수 chicken이 매개변수로 주어질 때 받을 수 있는 최대 서비스 치킨의 수를 return하도록 solution 함수를 완성해주세요.
제한사항
chicken은 정수입니다.
0 ≤ chicken ≤ 1,000,000
입출력 예
| chicken | result |
| 100 | 11 |
| 1,081 | 120 |
입출력 예 설명
입출력 예 #1
100마리를 주문하면 쿠폰이 100장 발급되므로 서비스 치킨 10마리를 주문할 수 있습니다.
10마리를 주문하면 쿠폰이 10장 발급되므로 서비스 치킨 1마리를 주문할 수 있습니다.
따라서 10 + 1 = 11 을 return합니다.
입출력 예 #2
1081마리를 주문하면 쿠폰이 1081장 발급되므로 서비스 치킨 108마리를 주문할 수 있습니다. 그리고 쿠폰이 1장 남습니다.
108마리를 주문하면 쿠폰이 108장 발급되므로 서비스 치킨 10마리를 주문할 수 있습니다. 그리고 쿠폰이 8장 남습니다.
10마리를 주문하면 쿠폰이 10장 발급되므로 서비스 치킨 1마리를 주문할 수 있습니다.
1마리를 주문하면 쿠폰이 1장 발급됩니다.
가지고 있는 쿠폰이 총 10장이므로 서비스 치킨 1마리를 추가로 주문할 수 있습니다.
따라서 108 + 10 + 1 + 1 = 120 을 return합니다.
풀이)
def solution(chicken):
return int(chicken*0.11111111111)
## 무한으로 이전값의 10%를 더하는 것과 같음
## 즉 chicken *0.1 + (chicken*0.1)*0.1+....
시간복잡도:
단 한번의 산술연산만 하므로 시간복잡도는 O(1)입니다.
공간복잡도:
리턴할 변수 하나의 공간만 필요하므로 공간복잡도도 O(1)입니다.
문제3) 연속된 숫자의 합 -> 연속된 정수의 합 공식 사용
연속된 세 개의 정수를 더해 12가 되는 경우는 3, 4, 5입니다. 두 정수 num과 total이 주어집니다. 연속된 수 num개를 더한 값이 total이 될 때, 정수 배열을 오름차순으로 담아 return하도록 solution함수를 완성해보세요.
제한사항
1 ≤ num ≤ 100
0 ≤ total ≤ 1000
num개의 연속된 수를 더하여 total이 될 수 없는 테스트 케이스는 없습니다.
입출력 예
| num | total | result |
| 3 | 12 | [3, 4, 5] |
| 5 | 15 | [1, 2, 3, 4, 5] |
| 4 | 14 | [2, 3, 4, 5] |
| 5 | 5 | [-1, 0, 1, 2, 3] |
입출력 예 설명
입출력 예 #1
num = 3, total = 12인 경우 [3, 4, 5]를 return합니다.
입출력 예 #2
num = 5, total = 15인 경우 [1, 2, 3, 4, 5]를 return합니다.
입출력 예 #3
4개의 연속된 수를 더해 14가 되는 경우는 2, 3, 4, 5입니다.
풀이)
def solution(num, total):
start = total//num - (num-1)//2
return [start+i for i in range(num)]
시간복잡도:
start 연산에 필요한 시간은 O(1)이지만 리스트를 만드는데 발생하는 시간은 O(n)이므로 총 시간복잡도는 O(n)입니다.
공간복잡도:
상수 변수 하나의 공간은 O(1)이지만 리스트가 하나 생성되므로 공간복잡도도 O(n)입니다.
문제4) 경우의 수 계산
머쓱이는 구슬을 친구들에게 나누어주려고 합니다. 구슬은 모두 다르게 생겼습니다. 머쓱이가 갖고 있는 구슬의 개수 balls와 친구들에게 나누어 줄 구슬 개수 share이 매개변수로 주어질 때, balls개의 구슬 중 share개의 구슬을 고르는 가능한 모든 경우의 수를 return 하는 solution 함수를 완성해주세요.
제한사항
1 ≤ balls ≤ 30
1 ≤ share ≤ 30
구슬을 고르는 순서는 고려하지 않습니다.
share ≤ balls
입출력 예
| balls | share | result |
| 3 | 2 | 3 |
| 5 | 3 | 10 |
내가 푼 풀이)
def solution(balls, share):
return factorial(balls) / (factorial(balls-share) * factorial(share))
def factorial(num):
answer = 1
while num > 1:
answer = answer * num
num -=1
return answer
시간복잡도:
팩토리얼 함수에서 시간복잡도는 O(n)이 발생합니다. 이때 3개의 팩토리얼을 사용했으므로 O(3*n) = O(n)이 됩니다. 솔루션 함수에서 발생한 산술연산의 시간복잡도는 O(1)입니다 따라서 총 시간 복잡도는 O(n)이 됩니다.
공간복잡도:
answer 변수하나의 메모리 공간만 추가로 발생하므로 공간복잡도는 O(1)입니다.
더 효율적인 풀이)
def solution(balls, share):
if share > balls - share:
share = balls - share # 대칭성 활용
result = 1
for i in range(1, share + 1):
result = result * (balls - i + 1) // i
return result
시간복잡도:
내가 푼 풀이에서는 balls의 값이 매우 클 경우 overflow가 발생할 수 있습니다. 위 풀이의 시간복잡도인 O(n)에서 n은 balls를 의미합니다. 이 풀이에서도 시간복잡도는 O(min(share ,balls-share))입니다. 이 풀이에서의 시간복잡도도 O(n)은 맞지만, share가 balls보다 클 수 없으므로 더 효율적입니다.
공간복잡도:
result 변수하나의 메모리 공간만 추가로 발생하므로 공간복잡도는 O(1)입니다.
참고: math.comb사용한 풀이)
import math
def solution(balls, share):
return math.comb(balls, share)
시간복잡도:
파이썬 3.8버전 이상에서는 조합계산 함수가 내장되어 있습니다. 이는 내부적으로 최소값 k = min(share, balls-share)만큼 반복해서 계산합니다. 이 반복문을 사용하여 (balls−i+1)//i 형태로 곱셈과 나눗셈 수행합니다. 따라서 시간복잡도는 위의 효율적인 풀이와 동일합니다.
공간복잡도:
리턴할 변수하나의 메모리 공간만 추가로 발생하므로 공간복잡도는 O(1)입니다.
문제5) 진료순서 정하기 - 내림차순 정렬
외과의사 머쓱이는 응급실에 온 환자의 응급도를 기준으로 진료 순서를 정하려고 합니다. 정수 배열 emergency가 매개변수로 주어질 때 응급도가 높은 순서대로 진료 순서를 정한 배열을 return하도록 solution 함수를 완성해주세요.
제한사항
중복된 원소는 없습니다.
1 ≤ emergency의 길이 ≤ 10
1 ≤ emergency의 원소 ≤ 100
입출력 예
| emergency | result |
| [3, 76, 24] | [3, 1, 2] |
| [1, 2, 3, 4, 5, 6, 7] | [7, 6, 5, 4, 3, 2, 1] |
| [30, 10, 23, 6, 100] | [2, 4, 3, 5, 1] |
입출력 예 설명
입출력 예 #1
emergency가 [3, 76, 24]이므로 응급도의 크기 순서대로 번호를 매긴 [3, 1, 2]를 return합니다.
입출력 예 #2
emergency가 [1, 2, 3, 4, 5, 6, 7]이므로 응급도의 크기 순서대로 번호를 매긴 [7, 6, 5, 4, 3, 2, 1]를 return합니다.
입출력 예 #3
emergency가 [30, 10, 23, 6, 100]이므로 응급도의 크기 순서대로 번호를 매긴 [2, 4, 3, 5, 1]를 return합니다.
내가 푼 풀이)
def solution(emergency):
answer = []
temp = []
for i, e in enumerate(emergency):
temp.append((i+1,e))
temp.sort(key=lambda x:x[1], reverse=True)
temp2 = [(i+1,t) for i,t in enumerate(temp)]
temp2.sort(key=lambda x:x[1][0])
for t in temp2:
answer.append(t[0])
return answer
시간복잡도:
temp 리스트를 생성하는 시간은 O(n), temp 리스트를 정렬하는데 걸리는 시간은 O(nlog n)입니다. 마찬가지로 tem2 리스트를 생성하고 정렬하는데 걸리는시간은 O(n)과 O(nlog n)입니다. 따라서 총 시간복잡도는 O(nlog n)이 됩니다.
공간복잡도:
리스트 생성시마다 추가적인 O(n)의 공간을 필요로 하므로 총 공간복잡도는 O(n)입니다.
더 효율적인 풀이)
def solution(emergency):
# 큰 수일수록 순위가 높다
sorted_emergency = sorted(emergency, reverse=True) # O(n log n)
# 값 → 순위 매핑
rank = {v: i+1 for i, v in enumerate(sorted_emergency)} # O(n)
# 원래 순서대로 순위를 매핑
return [rank[e] for e in emergency] # O(n)
시간복잡도:
위 풀이는 정렬을 한번만 실행했습니다. 물론 정렬하는데 걸리는 시간은 O(nlog n)이지만 내가 푼 풀이와는 다르게 정렬을 한번만 실행했으므로 실제 걸리는 시간은 내가 푼 풀이의 절반정도입니다. 따라서 더 효율적입니다.
공간복잡도:
내가 푼 풀이와 리스트를 생성할때마다 공간을 O(n)만큼 차지하므로 공간복잡도는 O(n)입니다.
문제6) 순서쌍의 개수 구하기
순서쌍이란 두 개의 숫자를 순서를 정하여 짝지어 나타낸 쌍으로 (a, b)로 표기합니다. 자연수 n이 매개변수로 주어질 때 두 숫자의 곱이 n인 자연수 순서쌍의 개수를 return하도록 solution 함수를 완성해주세요.
제한사항
1 ≤ n ≤ 1,000,000
입출력 예
| n | result |
| 20 | 6 |
| 100 | 9 |
입출력 예 설명
입출력 예 #1
n이 20 이므로 곱이 20인 순서쌍은 (1, 20), (2, 10), (4, 5), (5, 4), (10, 2), (20, 1) 이므로 6을 return합니다.
입출력 예 #2
n이 100 이므로 곱이 100인 순서쌍은 (1, 100), (2, 50), (4, 25), (5, 20), (10, 10), (20, 5), (25, 4), (50, 2), (100, 1) 이므로 9를 return합니다.
내가 푼 풀이)
def solution(n):
answer = 0
for i in range(1,n//2+1):
if n % i ==0:
answer +=1
return answer+1
시간복잡도:
주어진 n의 절반만큼만 순회합니다. O(n/2)은 O(1/2 * n)이므로 시간복잡도는 O(n)이라고 할 수 있습니다.
공간복잡도:
answer 변수 하나의 값만 추가되므로 공간복잡도는 O(1)입니다.
더 효율적인 풀이)
def solution(n):
answer = 0
i = 1
while i * i <= n: # √n 까지만 확인
if n % i == 0:
if i * i == n:
answer += 1 # 제곱수인 경우 (예: 10*10=100) → 중복 없이 1개만 추가
else:
answer += 2 # (i, n//i), (n//i, i)
i += 1
return answer
시간복잡도:
위 풀이는 주어진 n의 제곱근까지만 순회합니다. 제어문은 모두 O(1)이므로 총 시간복잡도는 O(n^0.5)라고 할 수 있습니다.
공간복잡도:
answer 변수 하나의 값만 추가되므로 공간복잡도는 O(1)입니다.
참고: math.isqrt를 이용한 풀이)
import math
def solution(n):
answer = 0
root = math.isqrt(n) # n의 정수 제곱근
for i in range(1, root + 1):
if n % i == 0:
if i * i == n:
answer += 1 # 제곱수인 경우 (예: 10*10=100) → 중복 없이 1개만
else:
answer += 2 # (i, n//i), (n//i, i) 두 쌍
return answer
시간복잡도:
위 풀이는 효율적 풀이 처럼 주어진 n의 제곱근까지만 순회합니다. 제어문은 모두 O(1)이므로 총 시간복잡도는 O(n^0.5)라고 할 수 있습니다.
공간복잡도:
answer 변수 하나의 값만 추가되므로 공간복잡도는 O(1)입니다.
문제7) 개미군단 - divmod 사용
개미 군단이 사냥을 나가려고 합니다. 개미군단은 사냥감의 체력에 딱 맞는 병력을 데리고 나가려고 합니다. 장군개미는 5의 공격력을, 병정개미는 3의 공격력을 일개미는 1의 공격력을 가지고 있습니다. 예를 들어 체력 23의 여치를 사냥하려고 할 때, 일개미 23마리를 데리고 가도 되지만, 장군개미 네 마리와 병정개미 한 마리를 데리고 간다면 더 적은 병력으로 사냥할 수 있습니다. 사냥감의 체력 hp가 매개변수로 주어질 때, 사냥감의 체력에 딱 맞게 최소한의 병력을 구성하려면 몇 마리의 개미가 필요한지를 return하도록 solution 함수를 완성해주세요.
제한사항
hp는 자연수입니다.
0 ≤ hp ≤ 1000
입출력 예
| hp | result |
| 23 | 5 |
| 24 | 6 |
| 999 | 201 |
입출력 예 설명
입출력 예 #1
hp가 23이므로, 장군개미 네마리와 병정개미 한마리로 사냥할 수 있습니다. 따라서 5를 return합니다.
입출력 예 #2
hp가 24이므로, 장군개미 네마리 병정개미 한마리 일개미 한마리로 사냥할 수 있습니다. 따라서 6을 return합니다.
입출력 예 #3
hp가 999이므로, 장군개미 199 마리 병정개미 한마리 일개미 한마리로 사냥할 수 있습니다. 따라서 201을 return합니다.
내가 푼 풀이)
def solution(hp):
answer = 0
while hp > 0:
if hp >= 5:
hp -=5
answer +=1
elif hp >= 3:
hp -=3
answer +=1
else:
hp-=1
answer +=1
return answer
시간복잡도:
while문을 반복하면서 hp를 줄여나가는 방식의 시간 복잡도는 O(n)입니다.
공간복잡도:
answer 변수 하나의 값만 추가되므로 공간복잡도는 O(1)입니다.
더 효율적인 풀이)
def solution(hp):
answer = 0
for ant in [5, 3, 1]:
d, hp = divmod(hp, ant) ## 몫을 answer에 추가하고 나머지를 hp로 변경함
answer += d
return answer
시간복잡도:
단순히 3번만 반복하면 되므로 시간복잡도는 O(1)입니다.
공간복잡도:
answer 변수 하나의 값만 추가되므로 공간복잡도는 O(1)입니다.
문제8) 공던지기 게임
머쓱이는 친구들과 동그랗게 서서 공 던지기 게임을 하고 있습니다. 공은 1번부터 던지며 오른쪽으로 한 명을 건너뛰고 그다음 사람에게만 던질 수 있습니다. 친구들의 번호가 들어있는 정수 배열 numbers와 정수 K가 주어질 때, k번째로 공을 던지는 사람의 번호는 무엇인지 return 하도록 solution 함수를 완성해보세요.
제한사항
2 < numbers의 길이 < 100
0 < k < 1,000
numbers의 첫 번째와 마지막 번호는 실제로 바로 옆에 있습니다.
numbers는 1부터 시작하며 번호는 순서대로 올라갑니다.
입출력 예
| numbers | k | result |
| [1, 2, 3, 4] | 2 | 3 |
| [1, 2, 3, 4, 5, 6] | 5 | 3 |
| [1, 2, 3] | 3 | 2 |
입출력 예 설명
입출력 예 #1
1번은 첫 번째로 3번에게 공을 던집니다.
3번은 두 번째로 1번에게 공을 던집니다.
입출력 예 #2
1번은 첫 번째로 3번에게 공을 던집니다.
3번은 두 번째로 5번에게 공을 던집니다.
5번은 세 번째로 1번에게 공을 던집니다.
1번은 네 번째로 3번에게 공을 던집니다.
3번은 다섯 번째로 5번에게 공을 던집니다.
입출력 예 #3
1번은 첫 번째로 3번에게 공을 던집니다.
3번은 두 번째로 2번에게 공을 던집니다.
2번은 세 번째로 1번에게 공을 던집니다.
내가 푼 풀이)
def solution(numbers, k):
numbers = numbers * k
answer = numbers[::2][k-1]
return answer
시간복잡도:
numbers 리스트를 순회하면서 새로운 리스트를 생성하고 해당 리스트를 반복하므로 시간복잡도는 O(n)이 됩니다.
공간복잡도:
numbers 리스트가 k만큼 늘어나므로 추가적인 공간은 O(n)만큼 필요하게 됩니다. 따라서 공간복잡도도 O(n)이 됩니다.
더 효율적인 풀이)
def solution(numbers, k):
n = len(numbers)
idx = (2 * (k-1)) % n
return numbers[idx]
시간복잡도:
numbers의 길이 연산에는 O(1) 시간이 필요하고 idx를 구하는 연산도 O(1)이므로 총 시간복잡도는 O(1)입니다.
공간복잡도:
n,idx 변수가 차지할 공간만 추가적으로 필요하므로 공간복잡도는 O(1)입니다.
문제9) 특이한 정렬 - 두가지 기준으로 정렬
정수 n을 기준으로 n과 가까운 수부터 정렬하려고 합니다. 이때 n으로부터의 거리가 같다면 더 큰 수를 앞에 오도록 배치합니다. 정수가 담긴 배열 numlist와 정수 n이 주어질 때 numlist의 원소를 n으로부터 가까운 순서대로 정렬한 배열을 return하도록 solution 함수를 완성해주세요.
제한사항
1 ≤ n ≤ 10,000
1 ≤ numlist의 원소 ≤ 10,000
1 ≤ numlist의 길이 ≤ 100
numlist는 중복된 원소를 갖지 않습니다.
입출력 예
| numlist | n | result |
| [1, 2, 3, 4, 5, 6] | 4 | [4, 5, 3, 6, 2, 1] |
| [10000,20,36,47,40,6,10,7000] | 30 | [36, 40, 20, 47, 10, 6, 7000, 10000] |
입출력 예 설명
입출력 예 #1
4에서 가까운 순으로 [4, 5, 3, 6, 2, 1]을 return합니다.
3과 5는 거리가 같으므로 더 큰 5가 앞에 와야 합니다.
2와 6은 거리가 같으므로 더 큰 6이 앞에 와야 합니다.
입출력 예 #2
30에서 가까운 순으로 [36, 40, 20, 47, 10, 6, 7000, 10000]을 return합니다.
20과 40은 거리가 같으므로 더 큰 40이 앞에 와야 합니다.
내가 푼 풀이)
def solution(numlist, n):
temp_list = []
for num in numlist:
diff = abs(num-n)
temp_list.append((diff,num))
temp_list.sort(key=lambda x:(x[0],-x[1])) ##첫번째 기준으로 오름차순 정렬 후 두번째 기준으로 내림차순 정렬
answer =[x[1] for x in temp_list]
return answer
시간복잡도:
sort함수는 시간복잡도가 O(nlog n)입니다. 그리고 리스트를 생성하는 것은 O(n)의 시간이 발생합니다. 따라서 총 시간복잡도는 O(nlog n)입니다.
공간복잡도:
temp_list와 answer를 생성하는데 추가적인 공간이 O(n)씩 필요하므로 공간복잡도는 O(n)입니다.
문제10) 다항식 더하기
한 개 이상의 항의 합으로 이루어진 식을 다항식이라고 합니다. 다항식을 계산할 때는 동류항끼리 계산해 정리합니다. 덧셈으로 이루어진 다항식 polynomial이 매개변수로 주어질 때, 동류항끼리 더한 결괏값을 문자열로 return 하도록 solution 함수를 완성해보세요. 같은 식이라면 가장 짧은 수식을 return 합니다.
제한사항
0 < polynomial에 있는 수 < 100
polynomial에 변수는 'x'만 존재합니다.
polynomial은 양의 정수, 공백, ‘x’, ‘+'로 이루어져 있습니다.
항과 연산기호 사이에는 항상 공백이 존재합니다.
공백은 연속되지 않으며 시작이나 끝에는 공백이 없습니다.
하나의 항에서 변수가 숫자 앞에 오는 경우는 없습니다.
" + 3xx + + x7 + "와 같은 잘못된 입력은 주어지지 않습니다.
0으로 시작하는 수는 없습니다.
문자와 숫자 사이의 곱하기는 생략합니다.
polynomial에는 일차 항과 상수항만 존재합니다.
계수 1은 생략합니다.
결괏값에 상수항은 마지막에 둡니다.
0 < polynomial의 길이 < 50
입출력 예
| polynomial | result |
| "3x + 7 + x" | "4x + 7" |
| "x + x + x" | "3x" |
입출력 예 설명
입출력 예 #1
"3x + 7 + x"에서 동류항끼리 더하면 "4x + 7"입니다.
입출력 예 #2
"x + x + x"에서 동류항끼리 더하면 "3x"입니다.
내가 푼 풀이)
def solution(polynomial):
cals = polynomial.split(" ")
x = 0 ## x의 계수
c = 0 ## 상수 값
print(cals)
for cal in cals:
if 'x' in cal:
s = cal.replace('x','')
if s:
x += int(s)
else:
x += 1
if "x" not in cal and '+' not in cal:
c += int(cal)
answer = ''
if x:
if x ==1:
if c:
answer = f"x + {c}"
else:
answer = "x"
else:
if c:
answer = f"{x}x + {c}"
else:
answer = f"{x}x"
else:
if c:
answer = f"{c}"
return answer
시간복잡도:
split함수로 분리하여 새로운 리스트를 생성하는데 걸리는 시간은 O(n)입니다. 분리한 리스트인 cals를 순회하는데 걸리는 시간은 O(n)입니다. replace 함수를 실행하는데 문자열을 순회하므로 O(n)이지만 위 문제에서는 전체 문자열을 순회하는 것이 아닌 split으로 잘라낸 문자열의 일부를 순회하므로 상수번 순회한다고 볼 수 있습니다. 따라서 시간복잡도는 O(n * 1)로 O(n)이라고 볼 수 있습니다. 따라서 총 시간복잡도는 O(n)이 됩니다.
공간복잡도:
cals 리스트를 생성하는데 O(n)이 필요합니다.그리고 answer 문자열을 만드는데 O(n)이 필요합니다. 그런데 문자열을 반복문 안에서 만드는 것이 아니라 반복이 종료된 후 생성하기때문에 총 공간복잡도는 O(n)입니다.
더 효율적인 풀이)
def solution(polynomial):
x_sum = 0
c_sum = 0
for term in polynomial.split(" + "):
if term.endswith('x'):
coeff = term[:-1]
x_sum += int(coeff) if coeff else 1
else:
c_sum += int(term)
if x_sum and c_sum:
return f"{x_sum if x_sum > 1 else ''}x + {c_sum}"
elif x_sum:
return f"{x_sum if x_sum > 1 else ''}x"
else:
return str(c_sum)
시간복잡도:
시간복잡도는 위와 동일하게 O(n)입니다. 그러나 위 풀이보다 더 가독성이 좋습니다.
공간복잡도:
공간복잡도도 위와 동일하게 O(n)입니다.
문제11) 문자열 밀기
문자열 "hello"에서 각 문자를 오른쪽으로 한 칸씩 밀고 마지막 문자는 맨 앞으로 이동시키면 "ohell"이 됩니다. 이것을 문자열을 민다고 정의한다면 문자열 A와 B가 매개변수로 주어질 때, A를 밀어서 B가 될 수 있다면 밀어야 하는 최소 횟수를 return하고 밀어서 B가 될 수 없으면 -1을 return 하도록 solution 함수를 완성해보세요.
제한사항
0 < A의 길이 = B의 길이 < 100
A, B는 알파벳 소문자로 이루어져 있습니다.
입출력 예
| A | B | result |
| "hello" | "ohell" | 1 |
| "apple" | "elppa" | -1 |
| "atat" | "tata" | 1 |
| "abc" | "abc" | 0 |
입출력 예 설명
입출력 예 #1
"hello"를 오른쪽으로 한 칸 밀면 "ohell"가 됩니다.
입출력 예 #2
"apple"은 몇 번을 밀어도 "elppa"가 될 수 없습니다.
입출력 예 #3
"atat"는 오른쪽으로 한 칸, 세 칸을 밀면 "tata"가 되므로 최소 횟수인 1을 반환합니다.
입출력 예 #4
"abc"는 밀지 않아도 "abc"이므로 0을 반환합니다.
내가 푼 풀이)
def solution(A, B):
answer = 0
list_a = list(A)
list_b = list(B)
for i in range(len(A)):
if list_a == list_b:
answer = i
break
v = list_a[-1]
list_a.insert(0,v)
del list_a[-1]
else:
answer = -1
return answer
시간복잡도:
리스트를 생성하는 것 모두 O(n)의 시간이 발생합니다. 그리고 배열의 삽입도 O(n)시간이 발생합니다. 여기서 배열의 삭제는 O(1)인데 왜냐하면 맨 뒤의 값만 삭제하기 때문에 다른 요소의 이동이 없기 때문입니다. 따라서 총 시간 복잡도를 계산하면 반복문안에서 매번 삽입이 발생하므로 O(n^2)입니다.
공간복잡도:
리스트가 생성되므로 O(n)입니다. 반복안에서도 기존의 리스트가 변하기만 하므로 공간복잡도는 O(n)입니다.
더 효율적인 풀이)
이 방법은 A문자열을 두개 이어붙여서 B가 A의 부분 문자열인지 확인하는 방법입니다.
def solution(A, B):
if len(A) != len(B):
return -1
double_a = A + A
idx = double_a.find(B)
return idx if idx != -1 else -1
시간복잡도:
double_a 라는 문자열을 생성하는데 걸리는 시간은 O(n)입니다. 그리고 double_a안에서 B문자열을 찾는 find함수도 O(n)의 시간이 걸립니다. 따라서 총 시간복잡도도 O(n)입니다.
공간복잡도:
double_a 문자열은 A 문자열 2개만큼의 공간을 차지합니다. 따라서 공간복잡도는 O(n)입니다. idx는 변수값이므로 공간복잡도는 O(1)입니다. 따라서 총 공간 복잡도는 O(n)입니다.
문제12) 유한소수 판별
소수점 아래 숫자가 계속되지 않고 유한개인 소수를 유한소수라고 합니다. 분수를 소수로 고칠 때 유한소수로 나타낼 수 있는 분수인지 판별하려고 합니다. 유한소수가 되기 위한 분수의 조건은 다음과 같습니다.
기약분수로 나타내었을 때, 분모의 소인수가 2와 5만 존재해야 합니다.
두 정수 a와 b가 매개변수로 주어질 때, a/b가 유한소수이면 1을, 무한소수라면 2를 return하도록 solution 함수를 완성해주세요.
제한사항
a, b는 정수
0 < a ≤ 1,000
0 < b ≤ 1,000
입출력 예
| a | b | result |
| 7 | 20 | 1 |
| 11 | 22 | 1 |
| 12 | 21 | 2 |
입출력 예 설명
입출력 예 #1
분수 7/20은 기약분수 입니다. 분모 20의 소인수가 2, 5 이기 때문에 유한소수입니다. 따라서 1을 return합니다.
입출력 예 #2
분수 11/22는 기약분수로 나타내면 1/2 입니다. 분모 2는 소인수가 2 뿐이기 때문에 유한소수 입니다. 따라서 1을 return합니다.
입출력 예 #3
분수 12/21는 기약분수로 나타내면 4/7 입니다. 분모 7은 소인수가 7 이므로 무한소수입니다. 따라서 2를 return합니다.
Hint
분자와 분모의 최대공약수로 약분하면 기약분수를 만들 수 있습니다.
정수도 유한소수로 분류합니다.
내가 푼 풀이)
import math
def solution(a, b):
so_list = []
gcd = math.gcd(a,b)
giyak = b / gcd
i = 2
if giyak ==1:
return 1
## 소인수 분해
while giyak >= i:
if giyak % i == 0:
if i not in so_list:
so_list.append(i)
giyak //= i
else:
i+=1
if so_list == [2] or so_list == [5] or so_list == [2,5]:
return 1
return 2
시간복잡도:
gcd 메서드는 유클리드 호제법을 사용하므로 시간복잡도는 O(log min(a,b))입니다. 그런데 소인수분해 하는 과정은 O(n)입니다.
따라서 총 시간복잡도는 O(n)이 됩니다.
공간복잡도:
so_list 리스트를 생성하는데 발생하는 추가 공간은 O(log n)개입니다. 왜냐하면 리스트에는 소인수만 담기기 때문입니다.
더 효율적인 풀이)
import math
def solution(a, b):
gcd = math.gcd(a, b)
b //= gcd # 기약분수의 분모
# 분모에서 2와 5를 모두 제거
for p in [2, 5]:
while b % p == 0:
b //= p
return 1 if b == 1 else 2
시간복잡도:
gcd 메서드는 위 풀이와 동일하게 시간복잡도는 O(log min(a,b))입니다. 그런데 분모에서 2와 5를 제거하는데 발생하는 시간은 O(log b)이므로 총 시간복잡도는 O(log n)이 됩니다.
공간복잡도:
2와 5만 담긴 리스트 외에는 새로운 리스트를 생성하지않기 때문에 공간복잡도는 O(1)이 됩니다.
문제13) 배열의 유사도 판단
두 배열이 얼마나 유사한지 확인해보려고 합니다. 문자열 배열 s1과 s2가 주어질 때 같은 원소의 개수를 return하도록 solution 함수를 완성해주세요.
제한사항
1 ≤ s1, s2의 길이 ≤ 100
1 ≤ s1, s2의 원소의 길이 ≤ 10
s1과 s2의 원소는 알파벳 소문자로만 이루어져 있습니다
s1과 s2는 각각 중복된 원소를 갖지 않습니다.
입출력 예
| s1 | s2 | result |
| ["a", "b", "c"] | ["com", "b", "d", "p", "c"] | 2 |
| ["n", "omg"] | ["m", "dot"] | 0 |
입출력 예 설명
입출력 예 #1
"b"와 "c"가 같으므로 2를 return합니다.
입출력 예 #2
같은 원소가 없으므로 0을 return합니다.
내가 푼 풀이)
def solution(s1, s2):
answer = 0
for i in s1:
for j in s2:
if i==j:
answer+=1
break
return answer
시간복잡도:
s1을 반복하면서 s2안에 있는 문자열이 일치하는지 찾습니다. 따라서 이중반복이 되므로 시간복잡도는 O(n^2)가 됩니다.
공간복잡도:
answer 변수 하나의 공간만 필요하므로 공간복잡도는 O(1)입니다.
더 효율적인 풀이)
def solution(s1, s2):
return len(set(s1) & set(s2)) ## 교집합
시간복잡도:
집합 자료구조의 교집합을 사용한 방법입니다. 자료구조 set을 만드는데 발생하는 시간은 O(n)입니다. 2개의 set을 만들기 때문에 시간 복잡도는 O(n)이 됩니다.
공간복잡도:
set 자료구조를 생성하기 때문에 이에 대한 공간이 필요합니다. 따라서 공간복잡도는 O(n)이 됩니다.
문제14) 제곱수 판별
어떤 자연수를 제곱했을 때 나오는 정수를 제곱수라고 합니다. 정수 n이 매개변수로 주어질 때, n이 제곱수라면 1을 아니라면 2를 return하도록 solution 함수를 완성해주세요.
제한사항
1 ≤ n ≤ 1,000,000
입출력 예
| n | result |
| 144 | 1 |
| 976 | 2 |
입출력 예 설명
입출력 예 #1
144는 12의 제곱이므로 제곱수입니다. 따라서 1을 return합니다.
입출력 예 #2
976은 제곱수가 아닙니다. 따라서 2를 return합니다.
내가 푼 풀이)
import math
def solution(n):
answer = 0
a = math.sqrt(n)
if str(a).split(".")[1] == '0':
answer = 1
else:
answer =2
return answer
시간복잡도:
math.sqrt의 시간 복잡도는 O(1)입니다. 그리고 숫자를 문자열로 바꾸는 str()은 O(log n)입니다 따라서 총 시간 복잡도는 O(log n)입니다.
공간복잡도:
상수 크기의 변수 a, answer만 사용하므로 공간복잡도는 O(1)입니다.
더 효율적인 풀이)
import math
def solution(n):
return 1 if math.isqrt(n) ** 2 == n else 2
시간복잡도:
math.isqrt는 정수제곱근을 구하는 함수입니다. 이 함수는 부동소수점 문제를 해결할 수 있으며 시간 복잡도는 O(1)입니다. 제곱 연산이나 제어문의 시간복잡도는 O(1)이므로 총 시간복잡도도 O(1)입니다.
공간복잡도:
추가적인 공간이 거의 필요하지 않으므로 O(1)입니다.
문제15) 세균증식 -> 2배연산
어떤 세균은 1시간에 두배만큼 증식한다고 합니다. 처음 세균의 마리수 n과 경과한 시간 t가 매개변수로 주어질 때 t시간 후 세균의 수를 return하도록 solution 함수를 완성해주세요.
제한사항
1 ≤ n ≤ 10
1 ≤ t ≤ 15
입출력 예
| n | t | result |
| 2 | 10 | 2048 |
| 7 | 15 | 229,376 |
입출력 예 설명
입출력 예 #1
처음엔 2마리, 1시간 후엔 4마리, 2시간 후엔 8마리, ..., 10시간 후엔 2048마리가 됩니다. 따라서 2048을 return합니다.
입출력 예 #2
처음엔 7마리, 1시간 후엔 14마리, 2시간 후엔 28마리, ..., 15시간 후엔 229376마리가 됩니다. 따라서 229,376을 return합니다.
내가 푼 풀이)
def solution(n, t):
for _ in range(t):
n*=2
return n
시간복잡도:
t회까지 증가하면서 n에 2배를 곱하는 방법입니다. t번을 반복하기 때문에 시간 복잡도는 O(n)이 됩니다.
공간복잡도:
추가적인 공간은 필요하지 않으므로 O(1)입니다.
더 효율적인 풀이)
def solution(n, t):
return n * (2 ** t)
시간복잡도:
2**t는 거듭제곱 연산입니다. 이는 일반적으로 O(log n)의 시간을 필요로 합니다.
공간복잡도:
마찬가지로 추가적인 공간은 필요하지 않으므로 O(1)입니다.
참고 : 비트연산자 풀이)
def solution(n, t):
return n << t
시간복잡도:
2배씩 곱하는 것이므로 이진수에서 왼쪽으로 t번 이동하는 것과 같습니다. 비트연산은 하드웨어단에서 연산되며 시간복잡도는 O(1)입니다.
공간복잡도:
마찬가지로 추가적인 공간은 필요하지 않으므로 O(1)입니다.
'Tools & Functions > 코딩 테스트 복기' 카테고리의 다른 글
| 프로그래머스 level1 파이썬 복기 -1 (0) | 2025.09.01 |
|---|---|
| 프로그래머스 level0 파이썬 복기 -3 (2) | 2025.08.26 |
| 프로그래머스 level0 자바 복기 (0) | 2025.08.24 |
| 프로그래머스 level0 파이썬 복기 -1 (0) | 2024.05.19 |