원티드 프리온보딩 2-1 알고리즘 (3)

wodnr_P·2023년 8월 31일

leetcode 알고리즘 원티드 원티드 프리온보딩 프리온보딩

LeetCode Top Interview 150

목록 보기

9/32

⭐️ LeetCode 알고리즘 풀이 (with Python)

# Happy Number

[Quetion]

LeetCode 202. Happy Number

📌 접근법

[문제 이해]

입력받은 수를 자리 수별로 별개의 숫자로 판단

각 숫자를 제곱하여 더한 값이 최종적으로 1이 되면 True 반환

처음에는 무슨 말인지 헷갈려서 하나씩 대입해보며 테스트 케이스를 손으로 풀어보았다.

만약 10이 주어진다면 12가 주어진다면 1의 제곱 + 2의 제곱 = 5, 5의 제곱 = 25, 2의 제곱 + 5의 제곱은 29 .... etc 최종 숫자가 1이면 True를 반환하라는 문제였다.

key:value 형태의 해쉬테이블을 활용하는 방법과 주먹구구식이 떠올랐지만 입력받은 수를 문자열로 형변환 하고 그 문자열의 개수대로 반복하여 숫자의 제곱을 더해가는 방식으로 주먹구구식 도전을 해보았다.

💻 구현

class Solution:
    def isHappy(self, n: int) -> bool:
        # 숫자를 문자로 형변환
        k = str(n)
        
        # 각 숫자 제곱의 합을 담을 변수
        r = 0
        
        # k가 1이 아닐 때 까지 반복
        while k != '1':
            if k == '1' or k =='7':
                return True
            
            elif int(k) < 10:
                return False
			
            # k의 개수 만큼 반복
            for i in range(len(k)):
                r += int(k[i])**2
            
            k = str(r)
            r = 0
 			
            # 다시 반복문 상위로 돌아가서 반복
            continue
        return True

Runtime: 32ms | Memory: 16.3MB
LeetCode 코드 중 Runtime 98%, Memory 32% 해당하는 결과

📝 Happy Number 회고

이번 문제는 key:value 형태 보다 주먹구구식 떠오르는 방법을 그대로 적용하는게 코드를 작성하기 쉬울 것 같아서 해당 방법으로 구현했다.
그 결과 반복문을 중첩으로 사용했지만 Runtime은 생각보다 빠르게 나왔고 Memory는 비교적 낮게 나왔다. k의 개수 만큼 r에 k의 제곱값이 저장되어서 그런 것 같다.
속도는 빠르게 나왔기 때문에 크게 변경하지 않고, 변수를 최대한 없애는 방향으로 약간의 변경을 해보았다.

# 개선 후
class Solution:
    def isHappy(self, n: int) -> bool: 
        r = 0
        
        while n != 1:
            if n == 7:
                return True
            
            elif n < 10:
                return False
            
            for i in range(len(str(n))):
                r += int(str(n)[i])**2
            
            n = r
            r = 0
 
            continue
        return True