W1. D2 - 그리디 문제1~3

그리디

현재 상황에서 가장 좋아 보이는 것만을 선택하는 알고리즘
(코테에서는 그리디 알고리즘의 정당성을 고민하면서 문제 해결방안을 떠올려야 한다)

---

🔥의 개수는 체감 난이도

✏️문제1> 모험가 길드 🔥🔥

입력조건: 첫째 줄에 모험가의 수 N이 주어진다,둘째줄에 각 모험가의 공포도의 값을 N이하의 자연수로 주어지며 각 자연수는 공백으로 구분한다.
출력조건: 여행을 떠날 수 있는 그룹 수의 최댓값을 출력한다

n번째 공포도<= n이면 그룹 1개 추가 & n 리셋

내 코드

N=int(input())
gongpodo= list(map(int, input().split()))
gongpodo.sort()
##print(gongpodo)
seq=0
GroupCnt=0
for i in gongpodo:
    seq=seq+1
    if i <=seq:
        GroupCnt=GroupCnt+1
        seq=0
print(GroupCnt)

---

✏️문제2> 곱하기 혹은 더하기 🔥

입력조건:첫번째줄에 여러개의 숫자로 구성된 하나의 문자열 S가 주어진다.(0<=S<=20)
출력조건:첫째 줄에 만들어질 수 있는 가장 큰 수를 출력한다.

0,1->"+"
그 외 숫자->"x"

내 코드

S=input()
res=int(S[0]) ###첫 번쨰 문자를 숫자로 변경하여 대입
for i in range(1,len(S)):
    value=int(S[i])
    if value=0 or value=1 or res=0 or res=1:
        res=res+value
    else:
        res=res*value
print(res)

Feedback

if value=0 or value=1 or res=0 or res=1:
-> if value<=1 or res<=1:
왜 이 생각을 못했지....;;

---

✏️문제3> 문자열 뒤집기 🔥🔥🔥

입력조건:첫째줄에 0,1로만 이루어진 문자열 S가 주어진다. S의 길이는 100만보다 작다.
출력조건:첫째 줄에 다솜이가 해야하는 행동의 최소 횟수를 출력한다.

1과 0의 cnt를 모두 구하고 비교하여 작은 값을 구한다

내 코드

N=input()
C0=0 ##0으로 
C1=0 ##1로
##101100101
if N[0]=='0': ##1번째 숫자에 대한 초깃값 설정
    C1=C1+1 ##1로 바꾼다
##N[0]=='1'
else:
    C0=C0+1 ##0으로 바꾼다

for i in range(len(N)-1): ##N번 반복
    if N[i]==N[i+1]:
        continue
    else:
        if N[i+1]=='0':
            C1=C1+1
        else:
            C0=C0+1
if C0>=C1:
    print(C1)
else:
    print(C0)

Feedback

중략...

# 두 번째 원소부터 모든 원소를 확인하며
for i in range(len(data) - 1):
    if data[i] != data[i + 1]:
        # 다음 수에서 1로 바뀌는 경우
        if data[i + 1] == '1':
            count0 += 1
        # 다음 수에서 0으로 바뀌는 경우
        else:
            count1 += 1

print(min(count0, count1))

min을 사용하는 방법이 있었지...😂 아직 갈길이 멀다..제발 좀 외우자..
if data[i] != data[i + 1]:을 먼저 쓰니 코드가 훨씬 간결해진다..

보완할 점

파이썬 문법을 좀 다시 봐야겠다. (쉬운 방법을 놔두고 돌아돌아 풀다니..비효율적인 것..)