24.03.07_TIL (알고리즘 예제 31-40)

[ 코딩 테스트 연습 ]

 

 

 

31. 세균 증식 

• 어떤 세균은 1시간에 두배만큼 증식한다고 합니다. 처음 세균의 마리수 n과 경과한 시간 t가 매개변수로 주어질 때 t시간 후 세균의 수를 return하도록 solution 함수를 완성해주세요.
• 제한사항
  • 1 ≤ n ≤ 10
  • 1 ≤ t ≤ 15
• 내가 푼 풀이

def solution(n, t):
    return (2 ** t) * n  # **은 거듭제곱

result = solution(2, 10)
# 처음 세균의 마리수 n, 경과한 시간 t, 결과값=t시간후 세균수
print(result) #출력 : 2048

 

• 다른 사람의 풀이

def solution(n, t):
    for i in range(t) :
        n *= 2
    return n

def solution(n, t):
    for time in range(t):
        n = n * 2
    return n

def solution(n, t):
    return n << t

result = solution(2, 10)
# 처음 세균의 마리수 n, 경과한 시간 t, 결과값=t시간후 세균수
print(result) #출력 : 2048

• n << t는 n을 왼쪽으로 t번 시프트(shift)하는 것을 의미합니다. 시프트 연산은 이진수로 표현된 값을 왼쪽이나 오른쪽으로 이동시키는 연산입니다. n이 5이고 t가 2일 때 n << t를 계산하면 5를 이진수로 나타내면 0b101이고, 왼쪽으로 2번 시프트하면 0b10100이 됩니다. 결과적으로 5를 2번 비트 단위로 왼쪽으로 시프트한 값인 20이 반환됩니다. 따라서 n << t는 n을 t만큼 왼쪽으로 시프트한 값을 반환하는 것입니다. 
• n = 5 (이진수로 0b101)
  t = 2
  5 << 2 = 20 (이진수로 0b10100)
  

 

 

 

 

 

 

 

32.  삼각형의 완성조건 (1)

• 선분 세 개로 삼각형을 만들기 위해서는 다음과 같은 조건을 만족해야 합니다.  (** 가장 긴 변의 길이는 다른 두 변의 길이의 합보다 작아야 합니다.)  삼각형의 세 변의 길이가 담긴 배열 sides이 매개변수로 주어집니다. 세 변으로 삼각형을 만들 수 있다면 1, 만들 수 없다면 2를 return하도록 solution 함수를 완성해주세요.
• 제한사항
  • sides의 원소는 자연수입니다.
  • sides의 길이는 3입니다.
  • 1 ≤ sides의 원소 ≤ 1,000
• 내가 푼 풀이

def solution(sides):
    sides.sort() #변을 길이에 따라 정렬
    longest_side = sides[-1] # 가장 긴 길이
    if longest_side < sides[0] + sides[1]:
        return 1
    else:
        return 2

result = solution(sides=[3,6,2])
# sides 는 세변, 가장 긴변은 다른 두변의 합보다 작다
print(result) #출력 : 2

 

 

• 다른 사람의 풀이

def solution(sides):
    return 1 if max(sides) < (sum(sides) - max(sides)) else 2
    # 삼각형이 되기 위한 조건: 세 변의 총합 - 최대 변 길이 > 최대 변 길이

def solution(sides):
    sides.sort()
    return 1 if sides[0]+sides[1]>sides[2] else 2

def solution(sides):
    return 1 if sum(sides) > 2 * max(sides) else 2

 

 

 

 

 

 

 

 

 

33.  중앙값 구하기 

• 중앙값은 어떤 주어진 값들을 크기의 순서대로 정렬했을 때 가장 중앙에 위치하는 값을 의미합니다. 예를 들어 1, 2, 7, 10, 11의 중앙값은 7입니다. 정수 배열 array가 매개변수로 주어질 때, 중앙값을 return 하도록 solution 함수를 완성해보세요.
• 제한사항
  • array의 길이는 홀수입니다.
  • 0 < array의 길이 < 100
  • -1,000 < array의 원소 < 1,000
• 내가 푼 풀이

def solution(array):
    i = sorted(array)
    n = len(i)
    # 배열을 정리한 뒤 배열의 길이를 알아낸다
    if n % 2 == 1 :
        return i[n//2]
    else:
        return i[n//2-1]


result = solution([9,-1,0])
print(result) #출력 : 0

 

• 처음에 sort 로 풀었다가 에러가 났다ㅠㅠ sort는 원본 리스트를 직접 변경하고, sorted는 새로운 정렬된 리스트를 반환하기 때문에 다른 코드!  위 코드에서는 원본 리스트를 변경하지 않고 중앙값을 구해야 하므로 sorted 함수를 사용해야만 한다. 만약 원본 리스트를 변경하고 싶다면 sort 메소드를 사용

 

 

• 다른 사람의 풀이

def solution(array):
    return sorted(array)[len(array) // 2]

 

 

 

 

 

 

 

 

 

34.  짝수는 싫어요 

• 정수 n이 매개변수로 주어질 때, n 이하의 홀수가 오름차순으로 담긴 배열을 return하도록 solution 함수를 완성해주세요.
• 제한사항 : 1 ≤ n ≤ 100
• 내가 푼 풀이

def solution(n):
    a = []
    for i in range(1, n+1, 2):
        a.append(i)
    return a


print(solution(10)) #출력 : [1, 3, 5, 7, 9]

 

• 다른 사람의 풀이 

def solution(n):
    return [i for i in range(1, n+1, 2)]

 

 

 

 

 

 

 

 

 

35.  순서쌍의 개수 

• 순서쌍이란 두 개의 숫자를 순서를 정하여 짝지어 나타낸 쌍으로 (a, b)로 표기합니다. 자연수 n이 매개변수로 주어질 때 두 숫자의 곱이 n인 자연수 순서쌍의 개수를 return하도록 solution 함수를 완성해주세요.
• 제한사항 : 1 ≤ n ≤ 1,000,000
• 내가 푼 풀이

def solution(n):
    pairs = []
    count = 0

    # 1부터 n까지 반복하여 가능한 모든 순서쌍을 검사
    for i in range(1, n + 1):
        for j in range(1, n + 1):
            if i * j == n:            # 두 숫자의 곱이 n인 경우
                pairs.append((i, j))  # 순서쌍 추가
                count += 1            # 순서쌍 개수 증가

    return [pairs, count]

print(solution(20))
#출력:[[(1, 20), (2, 10), (4, 5), (5, 4), (10, 2), (20, 1)], 6]

 

• 위 코드는 결과는 제대로 잘 나오는데 시간초과로 실패!!!! ㅠㅠ
• 시간복잡도를 줄이기 위해서 다시 코드를 map으로 짜야한다. map은 for 문을 간편하게 돌리는 식.
• chat GPT와 씨름함 ^^ ㅎㅎ...시간 복잡도 O(√n)는 알고리즘의 실행 시간이 입력 크기 n의 제곱근(**0.5 와 같은 말)에 비례한다는 것을 의미합니다. 효율적인 약수를 찾는 방법을 사용할 때 쓴다.  for 루프가 int(n**0.5) + 1 번 실행하면서 약수를 찾는다. 예를 들어, 36의 경우 루트(36)은 6이므로 가능한 약수의 범위는 1부터 6까지입니다. 이 때, 이 알고리즘은 최대 약수를 찾을 때까지 루프를 돌게 됩니다. <= 시간이 줄어든다. 1-36까지 도는 것보다 1-6까지만 돌게 되니까

 

def solution(n):
    return sum(map(lambda x: n % x == 0, range(1, int(n**0.5) + 1))) * 2

print(solution(100))
#출력:10

• 여기서 n % x == 0은 x가 n의 약수인지를 확인하는 조건이고, * 2를 하는 이유는 모든 약수를 찾은 후에도 하나의 쌍이 더 카운트되기 때문에 해준다.
• 출력값이 9 여야 하는데 10이 나와버렸다ㅠㅠ   (1, 100), (2, 50), (4, 25), (5, 20), (10, 10), (20, 5), (25, 4), (50, 2), (100, 1) 이므로 9를 return해야하는데 무조건 *2를 해서 (10,10)도 두개가 되어버린것!

 

def solution(n):
    count = 0

    for i in range(1, int(n ** 0.5) + 1):
        if n % i == 0:
            count += 1
            
            if i != n // i: # i가 n의 제곱근이 아닌 경우, n을 i로 나눈 몫도 약수이므로 count를 +1 해줘야함
                count += 1

    return count

print(solution(100))  #출력:9

 

 

 

 

• 다른 사람의 풀이

def solution(n):
    answer =0
    for i in range(n):
        if n % (i+1) ==0:
            answer +=1
    return answer

def solution(n):
    answer = 0
    for i in range(1,n+1):
        if n % i == 0:
            answer += 1
    return answer

def solution(n):
    return len(list(filter(lambda v: n % (v+1) == 0, range(n))))

def solution(n):
    return len([number for number in range(1, n+1) if n%number == 0])

 

 

 

 

 

 

 

 

 

 

36.  모음 제거 

• 영어에선 a, e, i, o, u 다섯 가지 알파벳을 모음으로 분류합니다. 문자열 my_string이 매개변수로 주어질 때 모음을 제거한 문자열을 return하도록 solution 함수를 완성해주세요.
• 제한사항 :
  • my_string은 소문자와 공백으로 이루어져 있습니다.
  • 1 ≤ my_string의 길이 ≤ 1,000
• 내가 푼 풀이
• 21번 특정문자 제거하기 응용

def solution(my_string):
    vowels = {'a', 'e', 'i', 'o', 'u'}
    return ''.join(i for i in my_string if i.lower() not in vowels)

print(solution("nice to meet you"))
#출력:nc t mt y

 

 

• 다른 사람의 풀이

def solution(my_string):
    return "".join([i for i in my_string if not(i in "aeiou")])

def solution(my_string):
    vowels = ['a','e','i','o','u']
    for vowel in vowels:
        my_string = my_string.replace(vowel, '')
    return my_string

def solution(my_string):
    answer = ''

    for c in my_string:
        if c in ['a', 'e', 'i', 'o', 'u']:
            continue
        answer += c

    return answer

 

 

 

 

 

 

 

 

 

 

37.  문자 반복 출력하기 

• 문자열 my_string과 정수 n이 매개변수로 주어질 때, my_string에 들어있는 각 문자를 n만큼 반복한 문자열을 return 하도록 solution 함수를 완성해보세요.
• 제한사항 :
  • 2 ≤ my_string 길이 ≤ 5
  • 2 ≤ n ≤ 10
  • "my_string"은 영어 대소문자로 이루어져 있습니다.
• 내가 푼 풀이

def solution(my_string, n):
    return ''.join(i * n for i in my_string)

print(solution("hello",2))
#출력:hheelllloo

 

 

• 다른 사람의 풀이

def solution(my_string, n):
    answer = ''
    for m in my_string:
        answer += (m * n)
    return answer

def solution(my_string, n):
    answer = ''
    for i in range(0, len(my_string)):
        answer += my_string[i] * n
    return answer

 

 

 

 

 

 

 

 

38.  옷가게 할인 받기 

• 머쓱이네 옷가게는 10만 원 이상 사면 5%, 30만 원 이상 사면 10%, 50만 원 이상 사면 20%를 할인해줍니다.
  구매한 옷의 가격 price가 주어질 때, 지불해야 할 금액을 return 하도록 solution 함수를 완성해보세요.
• 제한사항 :
  • 10 ≤ price ≤ 1,000,000 (price는 10원 단위로(1의 자리가 0) 주어집니다.)
  • 소수점 이하를 버린 정수를 return합니다.
• 내가 푼 풀이

def solution(price):
    x = 0 # x는 discount price

    if price >= 500000:
        x = 0.2
    elif price >= 300000:
        x = 0.1
    elif price >= 100000:
        x = 0.05

    i = price * (1 - x) # i는 최종가격
    return int(i)

print(solution(150000))
#출력:142500

 

• 다른 사람의 풀이

def solution(price):
    x = {500000: 0.8, 300000: 0.9, 100000: 0.95, 0: 1}
    for j, i in x.items():
        if price >= j:
            return int(price * i)
# discount_rates = x : 할인률 딕셔너리
# discount_rate = i : 할인율
# discount_price = j : 할인된 가격

• • discount_rates: 할인 금액과 해당 할인을 받을 수 있는 최소 가격의 쌍을 저장하는 딕셔너리입니다. 딕셔너리의 키는 할인된 가격을, 값은 해당 할인율을 나타냅니다. 예를 들어, 500000 원 이상 구매 시 20% 할인을 받는다면 {500000: 0.8}이 딕셔너리에 포함됩니다.
  • for discount_price, discount_rate in discount_rates.items(): discount_rates 딕셔너리를 반복하면서 할인 금액과 할인율을 순회합니다.
  • if price >= discount_price:: 현재 할인의 최소 가격이 구매 가격보다 작거나 같은지 확인합니다. 만약 그렇다면 해당 할인이 적용 가능합니다.
  • return int(price * discount_rate): 할인된 가격을 계산하여 반환합니다. 이 때 할인된 가격은 주어진 가격에 해당 할인율을 곱한 값이 됩니다. 그리고 int() 함수를 사용하여 소수점 이하를 버리고 정수 부분만 반환합니다.
  • discount_rates.items() :

    이는 딕셔너리의 각 항목이 (key, value)의 형태로 튜플로 묶여 있는 리스트를 반환하는 것입니다. 따라서 for discount_price, discount_rate in discount_rates.items():와 같이 사용하면 딕셔너리의 각 항목에 접근할 수 있습니다.

     

 

 

 

 

 

 

 

39.  제곱수 판별하기  

• 어떤 자연수를 제곱했을 때 나오는 정수를 제곱수라고 합니다. 정수 n이 매개변수로 주어질 때, n이 제곱수라면 1을 아니라면 2를 return하도록 solution 함수를 완성해주세요.
• 제한사항 : 10 ≤ price ≤ 1,000,000
• 내가 푼 풀이

def solution(n):
    root = int(n ** 0.5)  # 주어진 수의 제곱근을 계산
    if root * root == n:  # 제곱근을 제곱했을 때 원래 수가 나오는지 확인
        return 1  # 제곱수일 경우 1 반환
    else:
        return 2  # 제곱수가 아닐 경우 2 반환

print(solution(144))
#출력:1

 

• 다른 사람의 풀이

def solution(n):
    if n**(1/2) == int(n**(1/2)) :
        return 1
    else :
        return 2

def solution(n):
    return 1 if (n ** 0.5) % 1 == 0 else 2

def solution(n):
    for i in range(1,n):
        if n == i * i:
            return 1
    return 2

 

 

 

 

 

 

 

 

40.  숨어있는 숫자의 덧셈 (1) 

• 문자열 my_string이 매개변수로 주어집니다. my_string안의 모든 자연수들의 합을 return하도록 solution 함수를 완성해주세요.
• 제한사항 :
  • 1 ≤ my_string의 길이 ≤ 1,000
  • my_string은 소문자, 대문자 그리고 한자리 자연수로만 구성되어있습니다.
• 내가 푼 풀이

def solution(my_string):
    num = []  # 숫자를 저장할 리스트
    let = []  # 문자(letters)를 저장할 리스트
    total = 0
    for i in my_string:
        if i.isdigit(): # 숫자인 경우
            num.append(i)
        else: let.append(i) # 문자인 경우

    for j in num:
        total += int(j)

    return num, let, total

print(solution("1a2b3c4d123"))
# 출력 : (['1', '2', '3', '4', '1', '2', '3'], ['a', 'b', 'c', 'd'], 16)

 

 

• 다른 사람의 풀이

def solution(my_string):
    return sum(int(i) for i in my_string if i.isdigit())

print(solution("1a2b3c4d123"))
# 출력 : 16

def solution(my_string):
    answer = 0

    for i in my_string :
        if not i.isalpha() :
            answer += int(i)

    return answer

 

• isalpha() 함수를 사용하여 현재 문자 i가 알파벳인지 확인한다. 현재 문자가 알파벳인 경우에는 True를 반환하고, 그렇지 않은 경우에는 False를 반환합니다. not i.isalpha()로 현재 문자가 알파벳이 아닌 경우를 확인하여 현재 문자가 알파벳이 아닌 경우에만 다음을 수행하니까 숫자만 추출한다.
•  

def solution(my_string):
    return sum(map(int, filter(lambda x: x.isdigit(), my_string)))

 

• filter(lambda x: x.isdigit(), my_string): filter() 함수를 사용하여 my_string의 각 문자를 검사합니다. lambda x: x.isdigit()는 주어진 문자열 x가 숫자인지를 확인하는 함수입니다. 따라서 이 함수를 사용하면 my_string에서 숫자만을 남기게 됩니다. map(int, ...): map() 함수를 사용하여 숫자들을 정수로 변환합니다. 이렇게 하면 숫자들을 정수로 변환한 이터러블이 생성됩니다. sum(...): sum() 함수를 사용하여 이터러블에 포함된 모든 숫자들의 합을 계산합니다. 최종적으로 숫자들의 합이 반환됩니다.