Level2 - 7~12

1. 전화번호부 목록

https://programmers.co.kr/learn/courses/30/lessons/42577

def solution(phone_book):
    p_set=set()
    len_s=set()
    phone_book.sort(key=len)
    
    for phone in phone_book:
        for l in len_s:
            if phone[:l] in p_set:
                return False
        
        p_set.add(phone)
        len_s.add(len(phone))
    
    return True

#난 set을 이용해 풀었지만, 문자열의 startswith를 쓰는 방법과 문자열의 한글자씩 늘려가며 해쉬에 있는지 확인하는 방법도 있다

 

 

2. 멀쩡한 사각형

https://programmers.co.kr/learn/courses/30/lessons/62048

def gcd(a,b):
    if a>b:
        a,b=b,a
    
    if a==0:
        return b
    
    return gcd(a,b%a)

def solution(w,h): 
    wh_gcd=gcd(w,h)
    answer=w*h-((w//wh_gcd+h//wh_gcd)-1)*wh_gcd     # 분배해서 -w+h+gcd 해줘도 됨
    
    return answer

# 참고 풀이 https://leedakyeong.tistory.com/entry/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-%EB%A9%80%EC%A9%A1%ED%95%9C-%EC%82%AC%EA%B0%81%ED%98%95-in-python
# 잘 보면 대각선이 지나가는 길마다 작은 블럭들이 반복적으로 생김, 이 것은 w,h의 최대공약수 만큼 있다.
# 핵심은, 전체크기에서 가로+세로만큼 지나가므로 이걸 빼주고 각 블럭마다 중복되어 빼지는 것이 있으므로 블럭 개수를 더한다.
# 결국 w*h-(w+h)+gcd(w,h)

 

 

3. 다음 큰 숫자

https://programmers.co.kr/learn/courses/30/lessons/12911

def solution(n):
    count_1=bin(n).count('1')
    i=n+1
    while bin(i).count('1')!=count_1:
        i+=1

    return i
    
 # 당연히 브루트포스는 시간복잡도에서 걸릴줄 알고 시도조차 안했는데 이게 되다니.. 허무

 

 

 

4. 큰 수 만들기

https://programmers.co.kr/learn/courses/30/lessons/42883

#스택을 이용해서 O(n)으로 만들어보자

def solution(number, k):
    stack=[]
    for i,n in enumerate(number):
        while k>0 and stack and stack[-1]<n:
            stack.pop()
            k-=1
        if k==0:
            stack.extend(number[i:])
            break
        stack.append(n)

    return ''.join(stack[:-k]) if k else ''.join(stack) 


#내 처음 풀이 -> 길이가 채워질때까지 max를 매번 구함(시간초과)
# def solution(number, k):
#     begin,end=0,k+1
#     answer=""

#     while len(answer)<len(number)-k and end-begin>1:
#         idx,val=max(enumerate(number[begin:end]),key=lambda x:x[1])
#         answer+=val
#         begin+=idx+1
#         end+=1
#     if len(answer)<len(number)-k:
#         answer+=number[begin:]
    
#     return answer

    #수가 내림차순으로 되어있으면 pop할 기회가 없어 k가 0이상인 상태에서 빠져나오게 된다.
    #이럴땐 뒤에 원소 k개를 뺀다.

 

 

5. 2개 이하로 다른 비트

https://programmers.co.kr/learn/courses/30/lessons/77885#

def solution(numbers):
    answer=[]
    for n in numbers:		#일부 테케에서 n을 int형으로 바꿔줘야 런타임 오류가 안나게 바뀜;
        bin_n=list('0'+bin(int(n))[2:])		
        #0이 없는 경우를 대비해 맨 첫비트에 0을 붙여주고 비트를 수월하게 변경하기 위해 리스트로 변환
        idx0=''.join(bin_n).rfind('0')		#rfind는 문자에서 오른쪽부터 찾아줌
        if idx0==len(bin_n)-1: #제일 마지막으로 나오는 0이 맨끝(=짝수)
            answer.append(n+1)
        else:
            bin_n[idx0],bin_n[idx0+1]='1','0'
            answer.append(int(''.join(bin_n),2))
        
    return answer

 

 

6. 피로도

https://programmers.co.kr/learn/courses/30/lessons/87946#

def solution(k, dungeons):
    answer=[]
    
    def dfs(dungeons,cur,count):
        answer.append(count)
        for i,(need,use) in enumerate(dungeons):
            if need<=cur:
                dfs(dungeons[:i]+dungeons[i+1:],cur-use,count+1)
        
    dfs(dungeons,k,0)
    return max(answer)

# 순열로 모든 경우의 수의 순서로 구해보고 싶다 => dfs 사용!! (반복문+재귀)
# 중첩함수는 바깥의 변수를 마음껏 쓸수는 있지만 재할당 할 수는 없다. => 리스트로 함..
# (첫번째 방법)dfs에서 간 표시를 하고 돌아와서 복구하는 식 -> (2번째 방법)해당 원소를 뺀 리스트를 넘겨줌