[프로그래머스] 레벨 2 풀기 (1)

행동대장

1. 잘 모르겠으면 일단 0부터 하나씩 대입하면서 패턴을 찾자. -> 1번 문제 보면 안다..

---

1. 멀리 뛰기

 

문제

 

풀이

#1칸 또는 2칸 뛰기 가능
#1 = (1, 1) 1가지
#2 = (1, 1), (2) 2가지
#3 = (1, 1, 1), (1, 2), (2, 1) 3가지
#4 = 5가지
#이전거 + 그 이전거

def solution(n):
    answer = 0
    a, b=0, 1
    
    for i in range(n):
        a, b = b, a+b
        
    answer = b

    return answer % 1234567

패턴을 보니 이전 수와 이전전 수를 더하면 나온다는 것을 앎. 그것이 바로 피보나치 수열!
일단 a, b 초기값을 0과 1로 지정 후 계속 swap 하면 됨

def solution(n):
    answer = 0
    if n==1:
        return 1
    arr=[0] * (n+1)
    arr[1] = 1
    arr[2] = 2
    for i in range(3, n+1):
        arr[i] = arr[i-1] + arr[i-2]
        
    answer = arr[n]

    return answer % 1234567

0으로 채워진 배열을 만듦. 여기서 중요한 점은 i-2 인덱스를 사용하기 때문에 n+1

---

2. 의상

문제

코딩테스트 연습 - 의상 | 프로그래머스 스쿨

프로그래머스

너무 길어서 대체..

 

풀이

def solution(clothes):
    answer = 1
    dict={}
    for _, type in clothes:
        if type not in dict:
            dict[type] = 1
        else:
            dict[type] += 1
    
    for i in dict.values():
        answer *= (i+1)
        
    return answer - 1

문제를 해석해보면.. type별로 어떻게 계산되는지 구해야 됨. type + 1씩 서로 곱하고 나중에 1을 빼는게 답임.
_,는 clothes가 2차원 배열인데 첫 번째 요소는 고려하지 않겠다는 것임, 두 번째 요소를 type이라는 것

---

3. JadenCase 문자열 만들기

문제

풀이

def solution(s):
    words = s.split(' ')
    for i in range(len(words)):
        if (len(words[i]) > 0):
            words[i] = words[i][0].upper() + words[i][1:].lower()
        
    result = ' '.join(words)
    
    return(result)

split()은 그냥 공백에 따라 나눔, 공백이 몇 개 있어도 상관 X, 예를 들어 "A  B"이 있으면 ['A', 'B']로 나뉘어짐
split(' ')은 공백 '1개'에 따라 나눔, 예를 들어 "A  B"이 있으면 ['A', ' ', 'B']로 나뉘어짐, A, B 사이에 공백이 하나 있으면 걔를 절단선으로 사용(?) 이렇게 해야 원본 데이터가 그대로 남음
len(words[i])>0을 하는 이유는 ' ' 같은 애들은 카운팅이 안 돼서 얘보단 길어야 함
에효 걍 몰라.. upper()는 대문자, lower()는 소문자로 만들어줌
.join(문자열)은 그냥 쓰면 안되고 어떤 값에 대입해줘야함

---

4. 이진 변환 반복하기

문제

코딩테스트 연습 - 이진 변환 반복하기 | 프로그래머스 스쿨

프로그래머스

풀이

#0111010 -> 1111 -> 100
#1. 0의 갯수 count
#2. 전체 길이에서 0의 갯수 뺀 수를이진변환
#3. 반복..
#언제까지? -> 이진변환한게 1이 될때까지

def solution(s):
    zero_cnt, change_cnt, current_cnt = 0, 0, 0
    while int(s) != 1:
        current_cnt = s.count("0")
        zero_cnt += current_cnt # 0의 갯수 카운트
        
        new_length = len(s)-current_cnt # 0 제거 후 길이
        
        s=bin(new_length)[2:]
        change_cnt += 1

    return [change_cnt, zero_cnt]

1. 언제까지? -> 이진변환이 1이 될 때 까지 해야하니까 while문으로 조건을 걸어준다

2. 이진으로 변환하는 함수는 bin, 근데 0b~~ 형태로 나오니까 2부터 슬라이싱 해줘야함

3. 마지막에 배열만 딱 리턴할때 그냥 출력하고 싶은 값만 저 배열 안에 넣어주삼. 난 모르고 append 2개 함

---

5. 다음 큰 숫자

문제

풀이

#while로 bin한거 1 카운트 해서 같을 때까지
#계속 + 하는데 같으면 걍 바로 break 걸고 탈출

def solution(n):
    answer = n+1
    
    while bin(n).count("1") != bin(answer).count("1"):
        answer += 1
    
    return answer

1. 내가 몰랐던 사실: bin은 문자열 형태다.. 그래서 count(1)했을 때 틀렸었던 것

---

6. 구명보트

문제

코딩테스트 연습 - 구명보트 | 프로그래머스 스쿨

프로그래머스

풀이

#구명 보트: 한 번에 2명
#제한 100kg, 구명보트 최대한 적게, 모든 사람 구출
#50 50 70 80
#1. 처음 + 끝 사람 태우고 안 되면 계속 줄이는 방식
#2. 젤 가벼운 애랑 안 되면 걔는 계속 안 되는 거임 ㅇㅇ 혼자 타셈

def solution(people, limit):
    answer = 0
    people.sort()
    light = 0
    weight = len(people)-1
    while (light <= weight):
        if people[light] + people[weight] <= limit: # 1. 젤 가벼운 애랑 젤 무거운 애 비교해서 100보다 작음
            light += 1 # 2. 그 다음 가벼운 애랑
        weight -= 1 # 3. 그 다음 무거운 애랑 비교, 3-1. 만약 100보다 크면 
        answer +=1 # 3-2. 일단 무거운 애 보내! 
                
    
    return answer

그리디 알고리즘. 

접근은 좋았다! weight -= 1을 통해 무거운 애는 일단 보내는게 포인트

---

7.

ㅁ

코딩테스트 연습 - 연속 부분 수열 합의 개수 | 프로그래머스 스쿨

 

풀이

def solution(el):
    n = len(el)
    answer = set() # 중복되지 않은 값
    
    for i in range(n):
        ssum = el[i] # 첫 번째 원소
        answer.add(ssum) # 는 일단 넣고
        
        for j in range(i+1, i+n): # 그 다음 원소부터
            ssum += el[j % n] # 그 다음 원소에서 n 나누는 이유는 원형이니까 다시 돌아와야돼서..?
            answer.add(ssum)
            
    return len(answer)

1. 한 숫자를 기준으로 누적해서 더해가기

2. n을 나누는 이유 -> 원형이니까 다시 되돌아와야됨. ex) i=4라면 5%5=0번 인덱스부터 더해야되니까 n으로 나누는게 중요!!