코딩테스트 연습(leetcode #231, #202, #415)
231. Power of Two( https://leetcode.com/problems/power-of-two/ )
- 내가 작성한 코드(runtime : 41ms, memory: 16.46MB)
class Solution:
def isPowerOfTwo(self, n: int) -> bool:
self.solution = [2**x for x in range(32)]
if n in self.solution:
return 1
else:
return 0- 교수님 코드1(runtime : 36ms, memory: 16.51MB)
def solution1(n):
if n == 0: return False
# 2의 배수와 2의 제곱수 해당하는 제어문으로
# 2의 배수는 1아닌 수로 제어문 탈출
# 2의 제곱수는 1로 제어문 탈출
while n % 2== 0:
n = n / 2
if n == 1: True #여기에는 그냥 1(2의 0승)도 포함
else: False시간복잡도: O(lg n)
- - 교수님 코드2(runtime : 27ms, memory: 16.5MB)
def isPowerOfTwo(n):
if n == 0:
return False
diff_bits = n & (n-1)
if diff_bits == 0:
return True
else:
return False시간복잡도:O(1)
+ 비트 연산자(&): and 비트 연산자
: 이전의 수와 비트 and 연산을 통해 결과값이 0이라면 2제곱수이다.
ex) 8의 이진수 1000 + 7(8 - 1)의 이진수 0111 = 0000
202. Happy Number( https://leetcode.com/problems/happy-number/description/ )
- 내가 작성한 코드 -> 미완성(실패, 무한 반복문에서 걸림, sum하는 과정만 작성함)
class Solution:
def get_next(n):
happy = list(map(int, [x for x in str(n)]))
happy = [x**2 for x in happy]
return sum(happy)- 교수님이 작성한 코드
class Solution:
def isHappy(self, n: int) -> bool:
def get_next(n):
total_sum = 0
while n > 0:
n, digit = divmod(n, 10)
total_sum += digit**2
return total_sum
seen = set()
while n!= 1 and n not in seen:
seen.add(n)
n = get_next(n)
return n == 1설명:
(1) 입력받은 정수 n이 1 or 무한반복일때까지 반복함.
(2) get_next를 통해서 각 자리수의 제곱의 합을 계산함.
+ divmod()함수 : divmod(8, 2) -> (4(몫),0(나머지)) == (8 // 2, 8 % 2) -> (4, 0)
(3) 무한반복의 여부는 set을 이용하여 정수 생성시 set에 있는 경우 false, 없는 경우 set에 추가함
(4) 따라서 무한반복이 끝나면 또는 n(합이) 반복문에서 탈출하는데 return값에서 n == 1임을 재확인함으로써
무한반복을 수행하지만 각 자리수 합이 1인 경우에 true가 return 됨
415. Add Strings( https://leetcode.com/problems/add-strings/description/ )
- 교수님이 작성한 코드(runtime : 45ms, memory : 17.20MB)
class Solution:
def addStrings(self, num1: str, num2: str) -> str:
res = []
carry = 0
p1 = len(num1) - 1
p2 = len(num2) - 1
while p1 >= 0 or p2 >= 0:
#삼항 연산자,ternary operator
#[true value] if [condition] else [false_value]
x1 = ord(num1[p1]) - ord('0') if p1 >=0 else 0
x2 = ord(num2[p2]) - ord('0') if p2 >= 0 else 0
value = (x1 + x2 + carry) % 10
carry = (x1 + x2 + carry) // 10
res.append(value)
p1 -= 1
p2 -= 1
if carry:
res.append(carry)
return ''.join(str(x) for x in res[::-1])설명:
1) 각 자리 수를 입력받을 배열 res와 다음 자리 수 계산 시 포함되는 수를 나타내는 carry int 변수 초기화
2) p1, p2는 num1,num2의 자리를 나타낼 인덱스로 일의 자리숫자부터 시작하기 때문에 배열의 끝인 len(num) - 1로 초기값 설정
3) 인덱스 p1, p2는 0일때 까지 반복 수행
4) x1, x2는 각 자리의 문자열을 숫자로 변형함 이때 반복문은 or로 이뤄져 있기 때문에 삼항 연산자를 이용한 인덱스 조건을 개별적으로 설정
5) 합산되어 확정되어 버린 자리의 수를 변수 value로 설정하고 다음 자리 수로 올라가는 수는 carry로 재설정
6) 이렇게 생성된 value는 list에 저장하며 자리수는 증가함으로 p1, p2는 감소함
7) 반복문에서 빠져나온 carry는 제일 큰 자릿수의 결과로 그 값이 0보다 큰 경우 list에 추가함
8) list의 값은 int값으로 문제 형식에 맞게 str으로 형변환하여 join메소드를 통해 결합함
+)
ord(문자)함수 : 문자를 인자로 받아 해당문자의 유니코드 정수를 반환함 ex. ord('a) -> 97
char(정수)함수