230803 프로그래머스 Lv1 - 문자열 나누기, 명예의 전당 (1), 기사단원의 무기

문자열 나누기

문제

문자열 s가 입력되었을 때 다음 규칙을 따라서 이 문자열을 여러 문자열로 분해하려고 합니다.

먼저 첫 글자를 읽습니다. 이 글자를 x라고 합시다.
이제 이 문자열을 왼쪽에서 오른쪽으로 읽어나가면서, x와 x가 아닌 다른 글자들이 나온 횟수를 각각 셉니다. 처음으로 두 횟수가 같아지는 순간 멈추고, 지금까지 읽은 문자열을 분리합니다.
s에서 분리한 문자열을 빼고 남은 부분에 대해서 이 과정을 반복합니다. 남은 부분이 없다면 종료합니다.
만약 두 횟수가 다른 상태에서 더 이상 읽을 글자가 없다면, 역시 지금까지 읽은 문자열을 분리하고, 종료합니다.
문자열 s가 매개변수로 주어질 때, 위 과정과 같이 문자열들로 분해하고, 분해한 문자열의 개수를 return 하는 함수 solution을 완성하세요.

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

프로그래머스

접근

cnt1 첫문자 개수, cnt2는 그 후 문자 개수
1. 처음 'a'가 나왔을 때 k라는 변수에 'a'를 저장하고 cnt1에 1을 추가
2. 그 후 'a'가 또 나왔으면 cnt1는 1이 더 추가돼서 2가 된다.
3. 'a'가 연속으로 3번 나왔기에 cnt1은 3이 된다.
4. 'b'가 나왔을 때 cnt2에 1을 더 해준다.
(cnt1=4, cnt2=2) ===> ["aaabba"]
5. ["aaabbacc"]가 될 땐 cnt1과 cnt2가 같아지는 순간이기 때문에 answer에 1을 더해준다.
6. 끝까지 반복

해결

def solution(s):
   answer = 0
   cnt1=0; cnt2=0
   for i in s:
       if cnt1==cnt2:
           answer+=1
           k=i
       if k==i:
           cnt1+=1
       else:
           cnt2+=1
       
   return answer

명예의 전당 (1)

문제

"명예의 전당"이라는 TV 프로그램에서는 매일 1명의 가수가 노래를 부르고, 시청자들의 문자 투표수로 가수에게 점수를 부여합니다. 매일 출연한 가수의 점수가 지금까지 출연 가수들의 점수 중 상위 k번째 이내이면 해당 가수의 점수를 명예의 전당이라는 목록에 올려 기념합니다. 즉 프로그램 시작 이후 초기에 k일까지는 모든 출연 가수의 점수가 명예의 전당에 오르게 됩니다. k일 다음부터는 출연 가수의 점수가 기존의 명예의 전당 목록의 k번째 순위의 가수 점수보다 더 높으면, 출연 가수의 점수가 명예의 전당에 오르게 되고 기존의 k번째 순위의 점수는 명예의 전당에서 내려오게 됩니다.

이 프로그램에서는 매일 "명예의 전당"의 최하위 점수를 발표합니다. 예를 들어, k = 3이고, 7일 동안 진행된 가수의 점수가 [10, 100, 20, 150, 1, 100, 200]이라면, 명예의 전당에서 발표된 점수는 아래의 그림과 같이 [10, 10, 10, 20, 20, 100, 100]입니다.

명예의 전당 목록의 점수의 개수 k, 1일부터 마지막 날까지 출연한 가수들의 점수인 score가 주어졌을 때, 매일 발표된 명예의 전당의 최하위 점수를 return하는 solution 함수를 완성해주세요.

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

프로그래머스

접근

1. 명예의 전당 리스트 생성 top_list
2. score 리스트에서 명예의전당 리스트에 하나씩 넣고
3. 명예의전당 리스트 길이가 k보다 커지면 if len(top_list)>k
4. 가장 작은 값 삭제 top_list.remove(min(top_list))
5. 현재 명예의전당 리스트의 최솟값을 answer 에 append

해결

def solution(k, score):
    answer = []
    top_list = []
    for i in score:
        top_list.append(i)
        if len(top_list)>k:
            top_list.remove(min(top_list))
        answer.append(min(top_list))
    return answer

기사단원의 무기

문제

숫자나라 기사단의 각 기사에게는 1번부터 number까지 번호가 지정되어 있습니다. 기사들은 무기점에서 무기를 구매하려고 합니다.

각 기사는 자신의 기사 번호의 약수 개수에 해당하는 공격력을 가진 무기를 구매하려 합니다. 단, 이웃나라와의 협약에 의해 공격력의 제한수치를 정하고, 제한수치보다 큰 공격력을 가진 무기를 구매해야 하는 기사는 협약기관에서 정한 공격력을 가지는 무기를 구매해야 합니다.

예를 들어, 15번으로 지정된 기사단원은 15의 약수가 1, 3, 5, 15로 4개 이므로, 공격력이 4인 무기를 구매합니다. 만약, 이웃나라와의 협약으로 정해진 공격력의 제한수치가 3이고 제한수치를 초과한 기사가 사용할 무기의 공격력이 2라면, 15번으로 지정된 기사단원은 무기점에서 공격력이 2인 무기를 구매합니다. 무기를 만들 때, 무기의 공격력 1당 1kg의 철이 필요합니다. 그래서 무기점에서 무기를 모두 만들기 위해 필요한 철의 무게를 미리 계산하려 합니다.

기사단원의 수를 나타내는 정수 number와 이웃나라와 협약으로 정해진 공격력의 제한수치를 나타내는 정수 limit와 제한수치를 초과한 기사가 사용할 무기의 공격력을 나타내는 정수 power가 주어졌을 때, 무기점의 주인이 무기를 모두 만들기 위해 필요한 철의 무게를 return 하는 solution 함수를 완성하시오.

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

프로그래머스

접근

1-1. 약수의 개수 리스트 생성 num_divisor
1-2. i=1 부터 while문으로 i가 number+1 보다 작을 때 까지 반복

2. 약수 구하기
2-1.divisor_list 생성
2-2.for문으로 약수 구하기
2-3.divisor를 약수 리스트에 append
3. 갯수 구하기 - len(divisor_list)
4. num_divisor 리스트에서 limit보다 큰 원소를 power 로 바꿔주기
5. 다 더하기

1차 시도

# 1차 시도
def solution(number, limit, power):
    answer = 0
    num_divisor = []
    i = 1
    while i < number+1:
        divisor_lst=[]
        for divisor in range(1, i+1):
            if i % divisor == 0:
                divisor_lst.append(divisor)
        num_divisor.append(len(divisor_lst))
        i+=1
    for n in range(len(num_divisor)):
        if num_divisor[n] > limit:
            num_divisor[n] = power

    answer = sum(num_divisor)
    return answer

이렇게 했더니 시간 초과하는 테스트케이스가 발생

현재 코드의 시간 복잡도는 O(number^2)이기 때문
이는 number가 커질수록 실행 시간이 기하급수적으로 증가하게 된다.

해결 방안

1. 불필요한 계산 줄이기
2. 미리 계산한 결과 재활용하기:
약수의 개수를 빠르게 계산하는 방법을 사용한다. 
예를 들면, 10의 약수는 1, 2, 5, 10으로 총 4개인데, 10의 약수는 2와 5의 곱으로 이루어져 있다. 이러한 특성을 활용하여 약수의 개수를 빠르게 계산할 수 있음.
-  O(number) 시간 복잡도

 

2차 시도 (해결)

# 코드개선, 2차시도

def solution(number, limit, power):
    answer = 0
    num_divisor = [0] * (number + 1)  # 약수 개수를 저장할 리스트 초기화

    for divisor in range(1, number + 1):
        for i in range(divisor, number + 1, divisor):
            num_divisor[i] += 1

    for n in range(1, number + 1):
        if num_divisor[n] > limit:
            num_divisor[n] = power

    answer = sum(num_divisor)
    return answer

성공!!