URL : https://programmers.co.kr/learn/courses/30/lessons/77885
문제 설명
- 양의 정수 x에 대한 함수 f(x)를 다음과 같이 정의합니다.
- x보다 크고 x와 비트가 1~2개 다른 수들 중에서 제일 작은 수
- 예를 들어,
f(2) = 3 입니다. 다음 표와 같이 2보다 큰 수들 중에서 비트가 다른 지점이 2개 이하이면서 제일 작은 수가 3이기 때문입니다. |수|비트|다른 비트의 개수| |—|—|—| |2|000…0010|| |3|000…0011|1|
- f(7) = 11 입니다. 다음 표와 같이 7보다 큰 수들 중에서 비트가 다른 지점이 2개 이하이면서 제일 작은 수가 11이기 때문입니다.
수 | 비트 | 다른 비트의 개수 |
---|---|---|
7 | 000…0111 | |
8 | 000…1000 | 4 |
9 | 000…1001 | 3 |
10 | 000…1010 | 3 |
11 | 000…1011 | 2 |
- 정수들이 담긴 배열 numbers가 매개변수로 주어집니다. numbers의 모든 수들에 대하여 각 수의 f 값을 배열에 차례대로 담아 return 하도록 solution 함수를 완성해주세요.
제한 사항
- 1 ≤ numbers의 길이 ≤ 100,000
- 0 ≤ numbers의 모든 수 ≤ 1015
문제 풀이
- 1) 일단 10진수를 2진수로 변환한다면 짝수라면 맨뒤가 무조건 0으로 끝난다. 그리고 그 수보다 1이 더 큰수라면 마지막 0이 1로 바뀌기 떄문에 numbers가 짝수라면 무조건 +1을 해주면 된다. (다른 위치는 1개)
- 2) 문제는 홀수인데 맨 끝에서 0을 1로 바뀌고 그 다음의 위치의 1을 0으로 바꾸면 2개의 위치가 다른 2진법이 완성되고 이를 다시 10진법으로 변환시키면 된다.
- 해당 팁은 프로그래머스 질문하기에서 찾을수 있었다.
- 3) solution 함수 :
- numbers의 요소 number가 짝수라면 answer list에 +1을 해서 append해주는 방식으로 했다.
- number가 홀수라면 format함수를 이용해서 2진법으로 변환하여 temp 변수에 선언해준다.
- 만일 temp에 0이 없다면 맨 앞에 0을 더 해주었다. (conver_odd에서 맨 뒤의 0을 1로 바꿔야 하기때문)
- 4) conver_odd 함수:
- 2진법으로 변환된 temp를 파라미터로 받는다.
- temp의 제일 뒤에있는 0을 찾기위해 temp의 역순으로 list형태로 변환시킨다.
- list로 바꾸는 이유는 str 형태 일때는 0을 1로 바꾸는 요소변환이 안되서 이다. (replace를 사용하면 가능하긴 하나, 하나씩 0을 1로 1을 0으로 바꾸는건 쉽지않음)
- ls_temp를 for문을 돌면서 원소가 1이라면 idx를 1씩 더하고 만일 0이라면 중단한다.
- 이후 ls_temp의 index를 사용하여 0인 위치는 1로 변환하고 그보다 한칸 앞을 0으로 변환한다.
- ls_temp는 처음에 역순으로 저장한것이기 떄문에 다시 역순으로 변환하며 int를 사용하여 2진법을 10진법으로 변환한 값을 리턴한다.
- 5) 홀수는 위의 conver_odd 함수를 적용한 10진법을 answer에 저장후 최종 answer list를 리턴한다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
# 홀수일때 0과 1의 위치를 바꿔주는 함수
def convert_odd(temp):
ls_temp = list(temp[::-1])
idx = 0
for i in ls_temp:
if i == '1':
idx += 1
else :
break
ls_temp[idx] = '1'
ls_temp[idx-1] = '0'
return int(''.join(ls_temp)[::-1], 2)
def solution(numbers):
answer=[]
for number in numbers:
if number % 2 == 0:
answer.append(number+1)
else:
temp = format(number, 'b')
if '0' not in temp:
temp = '0' + temp
temp = convert_odd(temp)
answer.append(temp)
return answer
1
2
numbers = [2,7]
solution(numbers)
1
[3, 11]
1
2
3
# 추가 테스트 케이스
numbers = [1001, 337, 0, 1, 333, 673, 343, 221, 898, 997, 121, 1015, 665, 779, 891,421,222,256,512,128,100]
solution(numbers)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
[1002,
338,
1,
2,
334,
674,
347,
222,
899,
998,
122,
1019,
666,
781,
893,
422,
223,
257,
513,
129,
101]
1