문제1) split() 함수 (문자열 슬라이스)
문자열 str과 정수 n이 주어집니다.
str이 n번 반복된 문자열을 만들어 출력하는 코드를 작성해 보세요.
예시)
입력: string 5
출력: stringstringstringstringstring (string 5개)
내가 푼 풀이)
a, b = input().strip().split(' ') # 띄어쓰기 기준으로 문자열과 횟수를 분리
b = int(b) 횟수를 int형으로 변경
c = a # 문자열1개를 선언
for _ in range(b-1): # 횟수 -1 개를 반복 -> 첫번째 문자열을 이미 선언 했기때문에
c += a # 반복해서 같은 문자열을 붙임
print(c)
시간복잡도 :
반복문이 (b-1)번 수행되며 문자열은 불변객체이므로 문자열을 붙일때마다 새로운 문자열을 생성합니다.
따라서 매 연산때마다 O(len(c) + len(a)) 시간이 소요됩니다. 따라서 반복이 끝났을때 총 시간 복잡도는
O(len(a)×(1+2+⋯+b))=O(len(a)×b^2)이 되어 O(n^2)이 됩니다.
공간복잡도 :
문자열 c가 점점 커져 최종적으로 길이가 m × n인 문자열을 저장되어 공간복잡도는 O(m × n), 즉 O(n)이 됩니다.
더 효율적인 풀이)
a, b = input().strip().split(' ')
b = int(b)
print(a * b)
시간복잡도 :
a,b는 내부적으로 1번만 실행하므로 시간복잡도는 O(m*n), 즉 O(n)이 됩니다.
공간복잡도 :
공간복잡도는 위와 동일하게 O(n)입니다.
문제2) swapcase() 함수 (문자 대소문자 변경)
영어 알파벳으로 이루어진 문자열 str이 주어집니다. 각 알파벳을 대문자는 소문자로 소문자는 대문자로 변환해서 출력하는 코드를 작성해 보세요.
예시)
입력: aBcDeFg
출력: AbCdEfG
풀이)
str = input() # 입력값 받음
print(str.swapcase()) # 대소문자를 변경하는 함수
시간 복잡도:
swapcase() 함수는 문자열을 반복하면서 하나씩 검사 후 반환합니다. 따라서 시간복잡도는 O(n)이 됩니다.
공간복잡도:
새로운 문자열을 만들어서 반환하므로 공간복잡도도 O(n)이 됩니다.
문제3) 집합 사용
1부터 6까지 숫자가 적힌 주사위가 세 개 있습니다. 세 주사위를 굴렸을 때 나온 숫자를 각각 a, b, c라고 했을 때 얻는 점수는 다음과 같습니다.
세 숫자가 모두 다르다면 a + b + c 점을 얻습니다.
세 숫자 중 어느 두 숫자는 같고 나머지 다른 숫자는 다르다면 (a + b + c) × (a2 + b2 + c2 )점을 얻습니다.
세 숫자가 모두 같다면 (a + b + c) × (a2 + b2 + c2 ) × (a3 + b3 + c3 )점을 얻습니다.
세 정수 a, b, c가 매개변수로 주어질 때, 얻는 점수를 return 하는 solution 함수를 작성해 주세요.
풀이)
def solution(a, b, c):
s = {a, b, c}
sum1 = a + b + c
sum2 = a**2 + b**2 + c**2
sum3 = a**3 + b**3 + c**3
if len(s) == 1: # 모두 같음
return sum1 * sum2 * sum3
elif len(s) == 2: # 두 개 같음
return sum1 * sum2
else: # 모두 다름
return sum1
시간복잡도:
a,b,c를 구하는데 상수시간이 소모되며 이후에는 3개의 숫자만 산술연산을 실행하므로 시간복잡도는 O(1)이 됩니다.
공간복잡도:
공간복잡도 또한 3개의 숫자만 다루며 다른 변수가 없으므로 O(1)이 됩니다.
문제4) 좌표이동 - zip()함수, 딕셔너리 사용
정수 n과 문자열 control이 주어집니다. control은 "w", "a", "s", "d"의 4개의 문자로 이루어져 있으며, control의 앞에서부터 순서대로 문자에 따라 n의 값을 바꿉니다.
"w" : n이 1 커집니다.
"s" : n이 1 작아집니다.
"d" : n이 10 커집니다.
"a" : n이 10 작아집니다.
위 규칙에 따라 n을 바꿨을 때 가장 마지막에 나오는 n의 값을 return 하는 solution 함수를 완성해 주세요.
내가 푼 풀이)
def solution(n, control):
key = dict(zip(['w','s','d','a'], [1,-1,10,-10])) #zip으로 묶어서 사전형으로 변환
return n + sum([key[c] for c in control]) # 문자열을 반복하면서 key값에 따른 value값의 합 + 기본 n값
시간복잡도:
딕셔너리를 생성하는 것은 O(1)입니다. 그러나 sum(list)는 리스트를 반복하므로 O(n)이 됩니다. 따라서 총 시간복잡도는 O(n)이 됩니다.
공간복잡도:
list를 생성한 후 sum으로 리스트의 합계를 구하는 방식은 list를 생성하기 때문에 O(n)이 됩니다.
더 효율적인 풀이)
def solution(n, control):
key = {'w': 1, 's': -1, 'd': 10, 'a': -10}
total = n
for c in control:
total += key[c]
return total
시간복잡도:
딕셔너리를 생성하는 것은 O(1)입니다. 그러나 sum(list)는 리스트를 반복하므로 O(n)이 됩니다. 따라서 총 시간복잡도는 O(n)이 됩니다.
공간복잡도:
기존 풀이와 달리 리스트를 생성하지 않으므로 O(1)이 됩니다.
문제5) zip()함수, 딕셔너리 사용
정수 배열 numLog가 주어집니다. 처음에 numLog[0]에서 부터 시작해 "w", "a", "s", "d"로 이루어진 문자열을 입력으로 받아 순서대로 다음과 같은 조작을 했다고 합시다.
"w" : 수에 1을 더한다.
"s" : 수에 1을 뺀다.
"d" : 수에 10을 더한다.
"a" : 수에 10을 뺀다.
그리고 매번 조작을 할 때마다 결괏값을 기록한 정수 배열이 numLog입니다. 즉, numLog[i]는 numLog[0]로부터 총 i번의 조작을 가한 결과가 저장되어 있습니다.
주어진 정수 배열 numLog에 대해 조작을 위해 입력받은 문자열을 return 하는 solution 함수를 완성해 주세요.
예시)
입력: numLog : [0, 1, 0, 10, 0, 1, 0, 10, 0, -1, -2, -1]
결과: "wsdawsdassw"
내가 푼 풀이)
def solution(numLog):
answer = ''
key = dict(zip([1,-1,+10,-10],['w','s','d','a']))
for i in range(1,len(numLog)):
answer+=key[numLog[i] - numLog[i-1]]
return answer
시간복잡도:
zip함수를 사용해서 딕셔너리를 생성하는 것은 O(1)입니다. 그러나 리스트를 반복하면서 새로운 문자열을 계속 생성하기 때문에 총 시간 복잡도는 O(n^2)이 됩니다.
공간복잡도:
문자열의 길이가 .n-1이기때문에 공간복잡도는 O(n)이 됩니다.
더 효율적인 풀이)
def solution(numLog):
key = {1:'w', -1:'s', 10:'d', -10:'a'}
res = []
for i in range(1, len(numLog)):
res.append(key[numLog[i] - numLog[i-1]])
return ''.join(res)
시간복잡도:
zip함수를 사용해서 딕셔너리를 생성하는 것은 O(1)입니다. 그리고 리스에 append하는 것은 O(1)입니다. 따라서 한번의 리스트를 반복하는 O(n)이며 join을 사용하면 불변객체 문자열을 한번만 생성하므로 O(1)이 되어 총 시간복잡도는 O(n)이 됩니다.
공간복잡도:
리스트를 저장하기 때문에 공간복잡도는 O(n)이 됩니다.
문제6) 파이썬 함수의 특징 사용-> 리스트를 다수의 변수로 만들기
정수 배열 arr와 2차원 정수 배열 queries이 주어집니다. queries의 원소는 각각 하나의 query를 나타내며, [i, j] 꼴입니다.
각 query마다 순서대로 arr[i]의 값과 arr[j]의 값을 서로 바꿉니다.
위 규칙에 따라 queries를 처리한 이후의 arr를 return 하는 solution 함수를 완성해 주세요.
예시)
arr = [0, 1, 2, 3, 4]
queries = [[0, 3],[1, 2],[1, 4]]
result = [3, 4, 1, 0, 2]
풀이)
def solution(arr, queries):
for i, j in queries:
arr[i], arr[j] = arr[j], arr[i]
return arr
시간복잡도:
queries 는 이중리스트지만 내부 리스트의 길이는 항상 2개이므로 queries 를 반복하는 것의 시간복잡도는 O(n)입니다.
그리고 값을 서로 변경하는 것은 O(1)이므로 총 시간복잡도는 O(n)입니다.
공간복잡도:
새로운 리스트를 할당하는 것이 아닌 원 리스트인 arr을 바꾸며 변수 i,j외에는 사용하지 않으므로 공간복잡도는 O(1)이 됩니다.
문제7) 최빈값 구하기 - 딕셔너리 사용
최빈값은 주어진 값 중에서 가장 자주 나오는 값을 의미합니다. 정수 배열 array가 매개변수로 주어질 때, 최빈값을 return 하도록 solution 함수를 완성해보세요. 최빈값이 여러 개면 -1을 return 합니다.
제한사항
0 < array의 길이 < 100
0 ≤ array의 원소 < 1000
입출력 예
| array | result |
| [1, 2, 3, 3, 3, 4] | 3 |
| [1, 1, 2, 2] | -1 |
| [1] | 1 |
입출력 예 설명
입출력 예 #1
[1, 2, 3, 3, 3, 4]에서 1은 1개 2는 1개 3은 3개 4는 1개로 최빈값은 3입니다.
입출력 예 #2
[1, 1, 2, 2]에서 1은 2개 2는 2개로 최빈값이 1, 2입니다. 최빈값이 여러 개이므로 -1을 return 합니다.
입출력 예 #3
[1]에는 1만 있으므로 최빈값은 1입니다.
내가 푼 풀이)
def solution(array):
array_set_list = list(set(array))
answer_list = [(array.count(num),num) for num in array_set_list]
answer_list.sort(key=lambda x: x[0], reverse=True)
if len(answer_list) >=2:
if answer_list[0][0] == answer_list[1][0]:
return -1
answer = answer_list[0][1]
return answer
시간복잡도:
array_set_list를 생성하는 것은 중복이 최대일때는 한번이지만 중복이 없을때는 array와 동일한 리스트를 만드는것과 같으므로 시간 복잡도는 O(1)~O(n)입니다. 또한 리스트 컴프리헨션을 만드는 것은 O(n)입니다. 따라서 총 시간복잡도는 O(n)~O(n^2)이 됩니다.
공간복잡도:
array_set_list를 만드는것도 O(n) answer_list를 만드는 것도 O(n)이므로 총 공간복잡도도 O(n)이 됩니다.
더 효율적인 풀이)
def solution(array):
freq = {}
for num in array:
freq[num] = freq.get(num, 0) + 1
# 빈도 최댓값 찾기
max_count = max(freq.values())
# 최빈값 후보 추리기
candidates = [num for num, cnt in freq.items() if cnt == max_count]
if len(candidates) > 1:
return -1
return candidates[0]
시간복잡도:
딕셔너리를 만드는 것은 array의 모든 요소를 순회하므로 O(n)이 됩니다. 그러나 max값을 찾는것은 O(1)이 되며 딕셔너리를 순회하는 것도 O(1)입니다 따라서 총 시간 복잡도는 O(n)이 됩니다.
공간복잡도:
딕셔너리가 존재할 공간만 있으면 되므로 O(n)이 됩니다.
문제8) 피자나눠먹기 - math함수 사용
머쓱이네 피자가게는 피자를 여섯 조각으로 잘라 줍니다. 피자를 나눠먹을 사람의 수 n이 매개변수로 주어질 때, n명이 주문한 피자를 남기지 않고 모두 같은 수의 피자 조각을 먹어야 한다면 최소 몇 판을 시켜야 하는지를 return 하도록 solution 함수를 완성해보세요.
제한사항
1 ≤ n ≤ 100
입출력 예
| n | result |
| 6 | 1 |
| 10 | 5 |
| 4 | 2 |
입출력 예 설명
입출력 예 #1
6명이 모두 같은 양을 먹기 위해 한 판을 시켜야 피자가 6조각으로 모두 한 조각씩 먹을 수 있습니다.
입출력 예 #2
10명이 모두 같은 양을 먹기 위해 최소 5판을 시켜야 피자가 30조각으로 모두 세 조각씩 먹을 수 있습니다.
입출력 예 #3
4명이 모두 같은 양을 먹기 위해 최소 2판을 시키면 피자가 12조각으로 모두 세 조각씩 먹을 수 있습니다.
내가 푼 풀이)
def solution(n):
pizza = 6
while 1:
print(pizza)
if pizza % n ==0:
return pizza // 6
pizza += 6
시간복잡도:
pizza를 6씩 늘려가며 pizza % n == 0인지 검사하므로 사실상 최소공배수를 찾는 과정입니다. 이때 최대 6n까지 늘어날 수 있으므로 시간복잡도는 O(n)이 됩니다.
공간복잡도:
pizza와 n 변수 2개만 사용하므로 공간복잡도는 O(1)입니다.
더 효율적인 풀이)
import math
def solution(n):
return (n * 6) // math.gcd(n, 6) // 6
시간복잡도:
math함수에서 gcd는 유클리드 호제법이라는 것을 사용합니다. 유클리드 호제법에서 시간복잡도의 계산은 O(log(min(n, 6)))입니다. 그런데 6은 상수이므로 총 시간복잡도는 O(1)이 됩니다.
공간복잡도:
이 풀이에서는 n 변수 1개와 상수만 사용하므로 공간복잡도는 O(1)입니다.
문제9) find함수 사용
문자열 myString과 pat가 주어집니다. myString의 부분 문자열중 pat로 끝나는 가장 긴 부분 문자열을 찾아서 return 하는 solution 함수를 완성해 주세요.
제한사항
5 ≤ myString ≤ 20
1 ≤ pat ≤ 5
pat은 반드시 myString의 부분 문자열로 주어집니다.
myString과 pat에 등장하는 알파벳은 대문자와 소문자를 구분합니다.
입출력 예
| myString | pat | result |
| "AbCdEFG" | "dE" | "AbCdE" |
| "AAAAaaaa" | "a" | "AAAAaaaa" |
입출력 예 설명
입출력 예 #1
"AbCdEFG"에서 "dE"는 한 번 등장하며 처음부터 해당 위치까지 잘라내면 "AbCdE"가 됩니다. 따라서 이 문자열이 "dE"로 끝나는 가장 긴 문자열이며, "AbCdE"를 return 합니다.
입출력 예 #2
"AAAAaaaa"에서 "a"는 총 네 번 등장하며 이 중 가장 마지막에 있는 위치까지 잘라내면 "AAAAaaaa"가 됩니다. 따라서 이 문자열이 "a"로 끝나는 가장 긴 문자열이며, "AAAAaaaa"를 return 합니다.
풀이)
def solution(myString, pat):
##find() 함수는 왼쪽부터 찾고 rfind() 함수는 오른쪽부터 찾아서 index를 반환한다.
idx = myString.rfind(pat) # pat이 마지막으로 나타나는 시작 위치
return myString[:idx + len(pat)]
시간복잡도:
rfind함수는 내부적으로 '고성능 문자열 탐색 알고리즘'을 사용하는 함수입니다. 이는 일반적인 문자열 탐색 보다는 빠르다고합니다. 시간복잡도는 문자열 중복이 많지않다면 O(n)이 되고 문자열 중복이 매우 많은 경우는 최악이 되며 O(n^2)이 될 수 있습니다.
공간복잡도:
파이썬의 문자열을 불변객체입니다. 따라서 문자열을 슬라이싱하면 새로운 문자열이 생성이 되며 새로운 메모리공간을 필요로 하게됩니다. 따라서 공간복잡도는 O(n)이 됩니다.
문제10) maketrans()와 translate() 함수 - 여러 문자 치환
임의의 문자열이 주어졌을 때 문자 "a", "b", "c"를 구분자로 사용해 문자열을 나누고자 합니다.
예를 들어 주어진 문자열이 "baconlettucetomato"라면 나눠진 문자열 목록은 ["onlettu", "etom", "to"] 가 됩니다.
문자열 myStr이 주어졌을 때 위 예시와 같이 "a", "b", "c"를 사용해 나눠진 문자열을 순서대로 저장한 배열을 return 하는 solution 함수를 완성해 주세요.
단, 두 구분자 사이에 다른 문자가 없을 경우에는 아무것도 저장하지 않으며, return할 배열이 빈 배열이라면 ["EMPTY"]를 return 합니다.
제한사항
1 ≤ myStr의 길이 ≤ 1,000,000
myStr은 알파벳 소문자로 이루어진 문자열 입니다.
입출력 예
| myStr | result |
| "baconlettucetomato" | ["onlettu", "etom", "to"] |
| "abcd" | ["d"] |
| "cabab" | ["EMPTY"] |
입출력 예 설명
입출력 예 #1
문제 설명의 예시와 같습니다.
입출력 예 #2
"c" 이전에는 "a", "b", "c" 이외의 문자가 없습니다.
"c" 이후에 문자열 "d"가 있으므로 "d"를 저장합니다.
따라서 ["d"]를 return 합니다.
입출력 예 #3
"a", "b", "c" 이외의 문자가 존재하지 않습니다. 따라서 저장할 문자열이 없습니다.
따라서 ["EMPTY"]를 return 합니다.
풀이)
def solution(myStr):
## a->1, b->1, c->1로 변환한다.
table = myStr.maketrans('abc','111')
new_str = myStr.translate(table)
answer = [x for x in new_str.split("1") if x != '']
if not answer:
answer = ["EMPTY"]
return answer
시간복잡도:
maketrans함수는 고정크기의 데이터를 매핑하는 테이블을 생성하는 함수입니다. 이는 딕셔너리와 유사하게 동작하며 시간복잡도는 O(1)입니다. translate함수는 문자열을 순회하며 매핑된 값을 적용하는 함수입니다. 이에 대한 시간복잡도는 O(n)이 됩니다.
split함수로 인해 문자열을 또 순회하므로 시간복잡도는 O(n)이 추가로 발생합니다.
마지막으로 리스트 컴프리헨션으로 문자열 리스트를 반복하므로 O(n)이 추가로 발생하여 총 시간복잡도는 O(1)+O(3*n) = O(n)이 됩니다.
공간복잡도:
매핑 테이블이 적용된 문자열을 생성하므로 O(n), split으로 리스트를 생성하므로 O(n), 새로운 리스트를 또 하나 생성하므로 O(n)이 되어 총 공간복잡도는 O(3*n) = O(n)이 됩니다.
문제11) 먼저 나오는 문자를 기준으로 원하는 값 찾기 - enumerate
문자열 리스트 str_list에는 "u", "d", "l", "r" 네 개의 문자열이 여러 개 저장되어 있습니다. str_list에서 "l"과 "r" 중 먼저 나오는 문자열이 "l"이라면 해당 문자열을 기준으로 왼쪽에 있는 문자열들을 순서대로 담은 리스트를, 먼저 나오는 문자열이 "r"이라면 해당 문자열을 기준으로 오른쪽에 있는 문자열들을 순서대로 담은 리스트를 return하도록 solution 함수를 완성해주세요. "l"이나 "r"이 없다면 빈 리스트를 return합니다.
제한사항
1 ≤ str_list의 길이 ≤ 20
str_list는 "u", "d", "l", "r" 네 개의 문자열로 이루어져 있습니다.
입출력 예
| str_list | result |
| ["u", "u", "l", "r"] | ["u", "u"] |
| ["l"] | [] |
입출력 예 설명
입출력 예 #1
"r"보다 "l"이 먼저 나왔기 때문에 "l"의 왼쪽에 있는 문자열들을 담은 리스트인 ["u", "u"]를 return합니다.
입출력 예 #2
"l"의 왼쪽에 문자열이 없기 때문에 빈 리스트를 return합니다.
풀이)
def solution(str_list):
for i, s in enumerate(str_list):
## l이든 r이든 먼저 나온 문자를 기준으로 리턴
if s == "l":
return str_list[:i] # "l" 왼쪽
elif s == "r":
return str_list[i+1:] # "r" 오른쪽
return []
시간복잡도:
str_list를 순회하기 때문에 이에 대한 시간복잡도는 O(n)입니다. 문자가 'l'인지 'r'인지 비교하는 연산의 O(1)이며 문자열 슬라이싱에 대한 시간복잡도는 O(n)입니다 따라서 총 시간복잡도는 O(n)+O(n)+(1) = O(n)이 됩니다.
공간복잡도:
리스트를 슬라이싱하여 새로운 리스트를 생성하므로 공간복잡도는 O(n)이 됩니다.
문제12) 나선형으로 데이터 채우기 - 좌표 및 충돌방지
양의 정수 n이 매개변수로 주어집니다. n × n 배열에 1부터 n2 까지 정수를 인덱스 [0][0]부터 시계방향 나선형으로 배치한 이차원 배열을 return 하는 solution 함수를 작성해 주세요.
제한사항
1 ≤ n ≤ 30
입출력 예
| n | result |
| 4 | [[1, 2, 3, 4], [12, 13, 14, 5], [11, 16, 15, 6], [10, 9, 8, 7]] |
| 5 | [[1, 2, 3, 4, 5], [16, 17, 18, 19, 6], [15, 24, 25, 20, 7], [14, 23, 22, 21, 8], [13, 12, 11, 10, 9]] |
입출력 예 설명
입출력 예 #1
예제 1번의 n의 값은 4로 4 × 4 배열에 다음과 같이 1부터 16까지 숫자를 채울 수 있습니다.
| 행 \ 열 | 0 | 1 | 2 | 3 |
| 0 | 1 | 2 | 3 | 4 |
| 1 | 12 | 13 | 14 | 5 |
| 2 | 11 | 16 | 15 | 6 |
| 3 | 10 | 9 | 8 | 7 |
따라서 [[1, 2, 3, 4], [12, 13, 14, 5], [11, 16, 15, 6], [10, 9, 8, 7]]를 return 합니다.
입출력 예 #2
예제 2번의 n의 값은 5로 5 × 5 배열에 다음과 같이 1부터 25까지 숫자를 채울 수 있습니다.
| 행 \ 열 | 0 | 1 | 2 | 3 | 4 |
| 0 | 1 | 2 | 3 | 4 | 5 |
| 1 | 16 | 17 | 18 | 19 | 6 |
| 2 | 15 | 24 | 25 | 20 | 7 |
| 3 | 14 | 23 | 22 | 21 | 8 |
| 4 | 13 | 12 | 11 | 10 | 9 |
따라서 [[1, 2, 3, 4, 5], [16, 17, 18, 19, 6], [15, 24, 25, 20, 7], [14, 23, 22, 21, 8], [13, 12, 11, 10, 9]]를 return 합니다.
풀이)
def solution(n):
# n x n 배열을 0으로 초기화
arr = [[0] * n for _ in range(n)]
# 이동 방향 (오른쪽, 아래, 왼쪽, 위)
directions = [(0,1), (1,0), (0,-1), (-1,0)]
dir_idx = 0 # 현재 방향 인덱스
x, y = 0, 0 # 시작 위치
num = 1 # 채울 숫자
while num <= n*n:
arr[x][y] = num
num += 1
# 다음 좌표
dx, dy = directions[dir_idx]
nx, ny = x + dx, y + dy
# 범위를 벗어나거나 이미 채워진 경우 → 방향 전환
if nx < 0 or nx >= n or ny < 0 or ny >= n or arr[nx][ny] != 0:
dir_idx = (dir_idx + 1) % 4
dx, dy = directions[dir_idx]
nx, ny = x + dx, y + dy
# 이동
x, y = nx, ny
return arr
시간복잡도:
요소의 값이 모두 0인 2차원 리스트를 생성하는데 O(n^2)의 시간이 필요합니다. 딕셔너리를 매핑하는데듣 시간복잡도가 O(1)이며
2차원 리스트를 모두 순회해야 하므로 이에대한 시간복잡도도 O(n^2)입니다. 순회중에서 조건이 발생하는데 필요한 시간복잡도는 O(1)이므로 총 시간복잡도는 O(n^2)이 됩니다.
공간복잡도:
2차원 리스트가 들어갈 공간이 O(n^2)가 필요하므로 공간복잡도도 O(n^2)이 됩니다.
문제13) 소인수분해
소인수분해란 어떤 수를 소수들의 곱으로 표현하는 것입니다. 예를 들어 12를 소인수 분해하면 2 * 2 * 3 으로 나타낼 수 있습니다. 따라서 12의 소인수는 2와 3입니다. 자연수 n이 매개변수로 주어질 때 n의 소인수를 오름차순으로 담은 배열을 return하도록 solution 함수를 완성해주세요.
제한사항
2 ≤ n ≤ 10,000
입출력 예
| n | result |
| 12 | [2, 3] |
| 17 | [17] |
| 420 | [2, 3, 5, 7] |
입출력 예 설명
입출력 예 #1
12를 소인수분해하면 2 * 2 * 3 입니다. 따라서 [2, 3]을 return합니다.
입출력 예 #2
17은 소수입니다. 따라서 [17]을 return 해야 합니다.
입출력 예 #3
420을 소인수분해하면 2 * 2 * 3 * 5 * 7 입니다. 따라서 [2, 3, 5, 7]을 return합니다.
풀이)
def solution(n):
answer = []
i=2
while i <= n:
if n % i ==0: ## n을 i로 나눠서 떨어지면
if i not in answer: ## 리스트에 i가 없다면
answer.append(i) ## 리스트에 추가
n //= i ## n을 i로 나눈값을 n으로 변경한다
else: ## i로 나눠서 떨어지지않는다면 i를 1증가시킨다.
i+=1
return answer
시간복잡도:
리스트를 반복하는데 걸리는 시간은 O(n)이며 i값이 answer에 없는지 검증하는데 발생하는 시간은 O(log n)입니다. 왜냐하면 answer 리스트에는 최대 log n개의 소인수만 들어갈 수 있기 때문입니다.
따라서 시간복잡도는 O(n*log n)이 됩니다.
공간복잡도:
소인수가 들어갈 리스트에는 최대 log n개의 값만 들어갈 수 있으므로 공간복잡도는 O(log n)이 됩니다.
문제14) 문자열로 된 숫자를 변환 - 딕셔너리 사용
영어가 싫은 머쓱이는 영어로 표기되어있는 숫자를 수로 바꾸려고 합니다. 문자열 numbers가 매개변수로 주어질 때, numbers를 정수로 바꿔 return 하도록 solution 함수를 완성해 주세요.
제한사항
numbers는 소문자로만 구성되어 있습니다.
numbers는 "zero", "one", "two", "three", "four", "five", "six", "seven", "eight", "nine" 들이 공백 없이 조합되어 있습니다.
1 ≤ numbers의 길이 ≤ 50
"zero"는 numbers의 맨 앞에 올 수 없습니다.
입출력 예
| numbers | result |
| "onetwothreefourfivesixseveneightnine" | 123456789 |
| "onefourzerosixseven" | 14067 |
입출력 예 설명
입출력 예 #1
"onetwothreefourfivesixseveneightnine"를 숫자로 바꾼 123456789를 return합니다.
입출력 예 #1
"onefourzerosixseven"를 숫자로 바꾼 14067를 return합니다.
내가 푼 풀이)
def solution(numbers):
numbers_dict = dict(
zero='0',
one='1',
two='2',
three='3',
four='4',
five='5',
six='6',
seven='7',
eight='8',
nine='9'
)
answer =''
temp_char = ''
for char in numbers:
temp_char += char
if temp_char in numbers_dict:
answer += numbers_dict.get(temp_char)
temp_char = ''
return int(answer)
시간복잡도:
딕셔너리를 매핑하는데는 O(1)의 시간이 발생합니다. numbers를 반복하는데는 O(n)의 시간이 필요하며 그런데 문자열은 불변객체라 문자열 생성에는 O(n)의 시간이 발생하는데 반복문 내부에서 계속해서 문자열을 생성하므로 총 시간복잡도는 O(n^2)이 됩니다.
공간복잡도:
반복문 내에서 문자열이 계속 생성되므로 O(n^2)이 될거라 생각했지만, 실제 공간복잡도는 O(n)이 됩니다. 왜냐하면 최종완성된 문자열 외에는 GC(가비지 콜렉터)에 의해 해제되기 때문입니다.
더 효율적인 풀이)
def solution(numbers):
numbers_dict = {
"zero":"0","one":"1","two":"2","three":"3","four":"4",
"five":"5","six":"6","seven":"7","eight":"8","nine":"9"
}
for word, digit in numbers_dict.items():
numbers = numbers.replace(word, digit) # 한 번에 치환
return int(numbers)
시간복잡도:
딕셔너리를 매핑하는데는 O(1)의 시간이 발생하며 만들어진 딕셔너리를 순회하는데는 상수시간이 발생합니다 따라서 O(1)입니다.
replace는 O(n)이 발생하므로 총 시간복잡도는 O(n)이 됩니다.
공간복잡도:
공간복잡도는 최종 완성된 문자열이 차지할 공간인 O(n)입니다.
문제15) 삼각형의 완성조건 -> 수학적 지식 필요
선분 세 개로 삼각형을 만들기 위해서는 다음과 같은 조건을 만족해야 합니다.
가장 긴 변의 길이는 다른 두 변의 길이의 합보다 작아야 합니다.
삼각형의 두 변의 길이가 담긴 배열 sides이 매개변수로 주어집니다. 나머지 한 변이 될 수 있는 정수의 개수를 return하도록 solution 함수를 완성해주세요.
제한사항
sides의 원소는 자연수입니다.
sides의 길이는 2입니다.
1 ≤ sides의 원소 ≤ 1,000
입출력 예
| sides | result |
| [1, 2] | 1 |
| [3, 6] | 5 |
| [11, 7] | 13 |
입출력 예 설명
입출력 예 #1
두 변이 1, 2 인 경우 삼각형을 완성시키려면 나머지 한 변이 2여야 합니다. 따라서 1을 return합니다.
입출력 예 #2
가장 긴 변이 6인 경우
될 수 있는 나머지 한 변은 4, 5, 6 로 3개입니다.
나머지 한 변이 가장 긴 변인 경우
될 수 있는 한 변은 7, 8 로 2개입니다.
따라서 3 + 2 = 5를 return합니다.
입출력 예 #3
가장 긴 변이 11인 경우
될 수 있는 나머지 한 변은 5, 6, 7, 8, 9, 10, 11 로 7개입니다.
나머지 한 변이 가장 긴 변인 경우
될 수 있는 한 변은 12, 13, 14, 15, 16, 17 로 6개입니다.
따라서 7 + 6 = 13을 return합니다.
풀이)
def solution(sides):
a, b = sides
big, small = max(a, b), min(a, b)
# 1. x가 가장 긴 변일 때: (big+small) - 1 개
case1 = (a + b - 1) - big
# 2. 기존 변이 가장 긴 변일 때: (big - small) 개
case2 = small
return case1 + case2
시간복잡도:
max, min 함수의 시간 복잡도는 O(1)이며 산술연산의 시간복잡도도 O(1)입니다. 따라서 총 시간복잡도는 O(1)이 됩니다.
공간복잡도:
공간복잡도는 상수값이 들어갈 변수만 발생하므로 O(1)이 됩니다.
'Tools & Functions > 코딩 테스트 복기' 카테고리의 다른 글
| 프로그래머스 level1 파이썬 복기 -1 (0) | 2025.09.01 |
|---|---|
| 프로그래머스 level0 파이썬 복기 -3 (2) | 2025.08.26 |
| 프로그래머스 level0 파이썬 복기 -2 (5) | 2025.08.26 |
| 프로그래머스 level0 자바 복기 (0) | 2025.08.24 |