[Python/파이썬] [🥈4] 백준 알고리즘 1065 - 한수

📖[Python/파이썬][🥈4] 백준 알고리즘 1065 - 한수

📜문제

---

📕풀이방향

우선, 1~99까지 숫자는 한수의 개수가 N개임.
100이상은 입력받는 수를 배열에 넣고, [0],[1] 차이와 [2],[1] 차이가 같으면 cnt를 증가시켜,
cnt를 return 해보자

---

📝알고리즘 구현순서

1. HanSu(n) 함수 만들기
2. 100미만 / 100이상 기준으로 if문을 사용하는데, 100이상 케이스는 바로 한수인 것만 카운트하기

   /* if/for 문 알고리즘 */
   1~1000까지 반복문 i를 돌리면서 케이스 if문으로 구분.
   N이 100미만 : 바로 N 출력
   N이 100이상 : list에 자릿수를 집어넣어 [0],[1],[2] 비교해서 한수만 cnt++

---

💻결과코드

def HanSu(n):
    cnt = 0;
    for i in range(1,n+1):
    	# 1부터 n까지의 수를 배열에 저장
        han = list(map(int,str(i)))
        
        # 100미만 : 경우 자기자신이 한수이기 때문에 cnt 증가
        if i < 100 :
            cnt += 1;
            
        # 100이상 : 한수(첫번째 두번째 수 차이 == 두번쨰 세번째 수 차이)인 경우 cnt 증가 
        elif han[0]-han[1] == han[1]-han[2] :
            cnt += 1;
    return cnt
    
N = int(input())
print(HanSu(N))

---

✏️1. HanSu(n) 함수 만들기

def HanSu(n):
  cnt = 0; #우선 한수 계산할 변수 미리 만들어두기
  for i in range(1, n+1):
    if i < 100 :
      # 100미만인 경우 코드
    elif i >= 100 :
      # 100이상인 경우 코드
  return cnt;

N = int(input())
print(HanSu(N))

쓸데없는 범위지정을 줄이고 딱 2가지 케이스의 하나의 반복문으로 구현했음

---

✏️2. 100미만 / 100이상 케이스 구현

(중략)

for i in range(1,n+1):
  han = list(map(int,str(i))) #han에 3자릿수 각각 인덱싱
  
  #100미만 : cnt++
  if i < 100 :
    cnt += 1;
    
  #100이상 : 각 자릿수 비교 후 일치하면 cnt++
  elif han[0]-han[1] == han[1]-han[2] :
    cnt += 1;

👉🏻num_list 없이 바로 한수를 카운팅

---

📚기존 내 알고리즘의 오류와 비효율적인 이유 정리

※ 내가 처음 구현한 d(n) 함수
(결론적으론 정답이긴 하지만, 비효율적임)

<def HanSu(N):
    if N > 110 : #110보다 클 때 한수는 99에서 더해가야함
        cnt = 99;
        for j in range(110, int(N)+1):
            han_list = list(map(int,str(j))) # [1],[1],[0]
            #num이라는 비교 list를 만들자 (이건 무조건 han list 보다 한자릿수 작다)
            num_list = [0]*(len(han_list)-1)
            
            #이 반복문은 han_list에 담긴 배열 인덱스의 순서를 돌면서
            #차이를 num_list에 저장하기 위한 for문이다
            for i in range(len(han_list)):
            
                #"[i+1]번째 인덱스 - [i]번째 인덱스"를 num_list에 넣을 예정
                #han_list보다 num_list가 크면 안되니까 길이를 지정해두자
                if i+1 < len(han_list) :
                    num_list[i] = (han_list[i+1])-(han_list[i])
            
            #위 반복문에서 만들어둔 num_list의 [0]번째 인덱스와 나머지 인덱스가 중복되면(count)
            #cnt++를 하며 최상위 for문을 다시 반복한다
            if num_list.count(num_list[0]) == (len(han_list)-1) :
                cnt += 1;
    
    elif N < 100 : #100보다 작으면 한수는 N개
        cnt = N;

    else: #100보다 크고 110보다 작을땐 한수는 99개
        cnt = 99;

    return cnt

---

1. 범위오류

1) 100보다 작으면 한수는 N개,
2) 100보다 크고 110보다 작으면 한수는 99개로 통일 ← 이게 필요가 없는 과정임
3) 110보다 크면 자릿수마다 비교해가면서 한수를 더해야 함

👉🏻맞다. 결론적으로 범위지정부터 잘못되었다.
"1~99 / 100~109 / 110~ == 1~99 / 100~" 이므로 굳이 99~110으로 나눌 필요도 없었거니와,
100~110은 "110~"의 케이스와 동일하게 동작하므로 두 케이스를 합쳐도 상관없다

2. 알고리즘 오류

1) 두자릿수 이하면 배열의 [2]번째 인덱스가 없으므로 N으로 출력해줘야 하는 것이고,
2) 세자릿수면 [0][1] [2] 다 있으므로 "[1]-[0] == [2]-[1]"으로 비교를 할 수 있는데,
3) 네자릿수면???? [3]도 필요하니까 흠,,, 자릿수 차이 비교를 위한 num_list를 만들자.
🤷🏻‍♀️ "[1]-[0] == [2]-[1]" 대신 "[i+1]-[i]"를 num_list에 넣는걸로 하고,
대신, "if i+1 < len(han_list)"라는 범위지정을 하자

👉🏻총제적 난국..
일단 문제에서 N은 1~1000까지의 수, 즉 "3자릿수까지"라고 범위를 명시했다.
[3]번째 인덱스는 고려할 필요도 없었던 것임!
결론적으로 num_list도 쓸데없는 메모리낭비...