[백준1105번] 팔

팔
사용언어 : python
Greedy Alogorithm
난이도 : 실버1

✍ 문제

💻 코드

✔ 알고리즘 1 (스스로 생각해낸 알고리즘)

L,R=map(int,input().split())
Min=R
if L==R:
    count=0
    l=list(str(L))  
    for i in range(len(l)):
        if l[i]=="8":
            count+=1
else :
    for k in range(L,R):
        count=0
        l=list(str(k))
        for i in range(len(l)):
            if l[i]=="8":
                count+=1
        if count<Min:
            Min=count
        if count==0:
            break
print(Min)

💡알고리즘

처음에 접근한 방식 : 시간초과로 오류 발생
시간복잡도가 높아서 발생한 문제인 것 같다

이를 해결하기 위해 다른 발상으로 생각을 해보았다
1. 자릿수가 다르면 최솟값 무조건 0
2. 자릿수가 같은 경우 중 첫번째수가 다르면 무조건 0
3. 자릿수가 같은 경우 중 첫번째수가 같으면 min+1 하고 두번째수로 2번 반복해서 최솟값(min)을 찾아낸다

✔ 최종 알고리즘

L,R=map(int,input().split())
Min=0
l=str(L)
r=str(R)

if len(str(L))!=len(str(R)):
    Min=0
else :
    for i in range(len(str(R))):
        if l[i]==r[i]:
            if l[i]=='8':
                Min+=1
        else:
            break
print(Min)

위 알고리즘 대로 구현한 코드 성공!!