매일 3개씩 알고리즘
1) 프로그래머스 - 문자열 압축
2) 프로그래머스 - 수식 최대화
3) 프로그래머스 - 2개 이하로 다른 비트
10:10 ~ 11:50(1h 40m)
3번 하나 풀었다. 그것도 힌트보고 풀음...
나머지 문제는 시간상 문제도 못읽음
어렵다..
코멘트
: 일단 문제를 처음 풀 때 '완전탐색법'을 바탕으로 풀었으나, 어떻게보면 당연하게도 시간복잡도에서 걸렸다. 그래서 분명히 규칙이 있을 것이라는 생각에 DP적 접근으로 규칙을 찾고자 했다. 그래서 내가 처음에 발견해낸 규칙은 다음 수와의 다른 비트 수를 계속 적어보니 0부터 시작했을 때, 1,2,1,3,1,2,1,4,1,2,1,3,1,2,1,5 ....
이런식으로 가더라. 그래서 [1,2,1,False] 이런 규칙을 찾아냈다. 즉, 4번 주기로 2이하로 다를 수 없는 비트가 나오는 것이다. 그래서
l = [True,True,True,False]
for el in numbers:
if l[el % 4]:
answer.append(el+1)
else:
if check(el+1):
answer.append(el+(2**(int(math.log2(el+1))-1)))
else:
answer.append(el+2)
: 처음에는 위와 같이 짰다. 즉, numbers 안의 수가 해당 주기의 False에 해당하는 주기일 때를 제외하면 모두 +1한수가 2개 이하로 다른 비트이고, False에 해당할 때만 분기처리를 해주면 된다 생각했기 때문이다. check()함수는
def check(n):
if (n & (n - 1)):
return False
else:
return True
: 이러한 함수로 2^n에 해당하는 수인지 판별하는 함수이다.
이렇게 짠 이유는 규칙을 또 보니
3,7,15 등 (2^n)-1에 해당하는 수들의 2개 이하로 다른 비트의 값이
3의 경우는 3 + 2^(n-1) = 5
7의 경우는 7 + 2^(n-1) = 11 이런식이어서 적용했다.
그러면 나머지 5,11,13 등에 대한 처리가 필요했는데,
초반까지의 규칙을 보니까 +2를 하면 되는 것 같아서 그렇게 처리했는데, 그게 아니었다..ㅎ
결과적으로 봤을 때, (2^n) - 1에 해당하는 수들에 적용한 규칙은 맞았는데, 그 외의 처리가 잘못됐다. + 다른 사람들을 보니 짝수 및 홀수로 나눠서 푼 케이스가 많더라. 그래서 나도 짝수 홀수로 나눴다.
import math
def check(n):
if (n & (n - 1)):
return False
else:
return True
def solution(numbers):
answer = []
for el in numbers:
if el % 2 == 0:
# 짝수면 끝에 1만 붙이면됨
answer.append(el+1)
else:
if check(el+1):
answer.append(el+(2**(int(math.log2(el+1))-1)))
else:
std = int_to_bin(el)
for j in range(len(std)-1, -1, -1):
if j == 0:
std = ["0b"] + std
elif std[j] == "0":
std[j] = "1"
std[j+1] = "0"
break
answer.append(int("0b"+"".join(std),2))
return answer
: 최종적으로 제출하여 통과한 내코드는 위와 같다. 짝수 홀수로 나눠서 홀수 내에서 내가 찾아낸 규칙을 끼워넣었다.. 저렇게 하면 2^n-1 케이스에 한정해서 시간복잡도를 좀더 효율적으로 할 수 있다는 생각에 저렇게 했다. 그리고 아래에
for j in range(len(std)-1, -1, -1):
if j == 0:
std = ["0b"] + std
elif std[j] == "0":
std[j] = "1"
std[j+1] = "0"
break
: 이 부분의 규칙은 솔직히 어떻게 생각했나들 싶다.. 내가 부족한 것이겠지만 좀더 노력이 필요한 것 같다. 이런 유형에 익숙해져야겠다. 이건 생각해보면 DP라기보다 단순 규칙 찾기 문제였던 것 같다. 이런 문제일수록 차분하게 규칙을 찾는 접근을 하자.
알아둘 것
1) int(n진수 x,n) 이렇게 인풋을 넣어주면 n진수 값 x를 10진수로 바꿔준다.
2) bin(x) : x의 2진수 값을 리턴해줌(string타입) 대신 앞에 "0b"가 붙음.
3) 특정 값이 2의 n승에 해당하는지 아는 법 = 비트연산을 활용해서 만든 함수
def check(n):
if (n & (n - 1)):
return False
else:
return True
