2023 팀네이버 신입 공채 준비 (7) 프로그래머스 탐욕법 & 완전탐색

오늘 한 리스트

1. 프로그래머스 완전탐색 3 문제
2. 프로그래머스 탐욕법 1 문제

프로그래머스 완전탐색 피로도

• 문제 유형 : 완전탐색
  던전 피로도 확인

  from itertools import *
  def solution(k, dungeons):
    dungeons=sorted(dungeons,reverse=True)
    length=len(dungeons)
    answer=0
    for i in list(permutations(dungeons,length)):
        check=k
        num=0
        for j in i:
            max_p=j[0]
            use_p=j[1]
            if j[0]>check:
                continue
            else:
                if j[1]<=check:
                    check-=j[1]
                    num+=1
        if num>answer:
            answer=num
    return answer
  

  모든 경우의 수를 구한 다음 가장 많은 try수를 return 했음

프로그래머스 완전탐색 전력망을 둘로 나누기

• 문제 유형 : 완전탐색
  전력망 둘로 나누기 ``` def check_line(wires): check_wires=[] p1=[] ck_wr=wires.pop() p1.append(ck_wr) check_wires.append(ck_wr[0]) check_wires.append(ck_wr[1]) rm_wires=[] ck_num=0 while check_wires and wires: last_p=[] for i in check_wires: for num,j in enumerate(wires): if i in j: rm_wires.append(num) last_p.append(j) p1.append(j) rm_wires=sorted(rm_wires) while rm_wires: wires.pop(rm_wires.pop()) rm_wires=[] check_wires=[] if last_p: for i in last_p: for j in i: check_wires.append(j) num_p1=[] for i in p1: for j in i: num_p1.append(j) num_p1=len(set(num_p1)) return num_p1

def solution(n, wires): length=len(wires) num=0 ch_num=1000 for i in range(length): num+=1 ck_wr=wires.pop(0) num_p=check_line(wires.copy()) if abs(n-2num_p)<ch_num: ch_num=abs(n-2num_p) wires.append(ck_wr) return ch_num

어처피 둘로 나눠야하기 때문에 하나씩 뺸 후에 모든 경우의 수를 계산해본 코드이다.

## 프로그래머스 완전탐색 모음사전
* 문제 유형 : 완전탐색  
모음사전 만들기

from itertools import * def solution(word1): answer = 0 init_word=[“A”,”E”,”I”,”O”,”U”] code_book=[] for i in range(1,6): for j in product(init_word,repeat=i): word=”” for k in j: word+=k code_book.append(word)

code_book=sorted(code_book)
answer=code_book.index(word1)
return answer+1 ``` 모든 경우의 수를 담고있는 code_book을 만든 후에 sorted를 해준 후에 그 index를 찾으면 된다.

프로그래머스 탐욕법 체육복

• 문제 유형 : 탐욕법
  체육복을 도난 당했을 때 빌려주는 법

  def solution(n, lost, reserve):
    person = [0 for i in range(n)]
    com=[]
    for i in lost:
        if i in reserve:
            com.append(i)
    for i in com:
        lost.pop(lost.index(i))
        reserve.pop(reserve.index(i))
    for i in lost:
        person.pop()
    reserve=sorted(reserve)
    while lost and reserve:
        pro=0
        num=reserve.pop(0)
        m,p=num-1,num+1
        if m in lost:
            pro=1
            lost.pop(lost.index(m))
            person.append(0)
        if p in lost:
            if pro==0:
                lost.pop(lost.index(p))
                person.append(0)
        if len(person)==n:
            break
          
    return len(person)
  

  생각보다 복잡했고 lost, reserve가 순서가 무작위라서 이거 해결하느라 애먹엇다.