자연수 n이 매개변수로 주어질 때, 연속된 자연수들로 n을 표현하는 방법의 수를 return하는 solution를 완성해주세요.
제한사항
n은 10,000 이하의 자연수 입니다.
풀이
1 2 3 4 5 6 7 8 9 10 11 12 13
defsolution(n): q = [1] answer, i, total = 1, 1, 1 mid = int((n+1) / 2) # 절반보다 큰 값부터는 값이 없으니 절반까지 반복문 실행 while i < mid: i += 1 total += i q.append(i) while total > n: total -= q.pop(0) if total == n: answer += 1 return answer
defjosephus(n,k): res = [] q = Queue() # 직접 구현한 Queue 클래스 for i inrange(n): q.enqueue(i+1) while q.front.next: # 끝에서 2번째 원소까지 반복 for _ inrange(k-1): q.enqueue(q.dequeue()) res.append(q.dequeue()) res.append(q.dequeue()) # 마지막 원소 출력 return res
1번부터 N 번까지 N명의 사람이 원을 이루면서 앉아있고, 양의 정수 K(≤ N)가 주어진다. 이제 순서대로 K 번째 사람을 제거한다. 한 사람이 제거되면 남은 사람들로 이루어진 원을 따라 이 과정을 계속해 나간다. 이 과정은 N명의 사람이 모두 제거될 때까지 계속된다. 원에서 사람들이 제거되는 순서를 (N, K)-요세푸스 순열이라고 한다. 예를 들어 (7, 3)-요세푸스 순열은 <3, 6, 2, 7, 5, 1, 4>이다.
N과 K가 주어지면 (N, K)-요세푸스 순열을 구하는 프로그램을 작성하시오.
예시
입력: 7, 3
출력: [3, 6, 2, 7, 5, 1, 4]
1. list로 풀기
예시대로 3번째 마다 사람을 제거하려면, 처음에는 시작점이니 2번만 인덱스를 이동하고 제거한 후 이 후에는 3번 인덱스를 이동해서 제거한다.
첫 시작을 0이 아닌 -1로 시작하는 점에 유의하자.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
defjosephus(n,k): res = [] line = [1for _ inrange(n)] # 값이 1이면 제거 대상, 0이면 제거 완료 i = -1
for _ inrange(n-1): count = 0 while count < k: i = (i + 1) % n # i는 0~6까지 순회해야하므로 나머지로 계산한다. if line[i]: # line의 원소가 0이 아니면... count += 1 line[i] = 0 res.append(i+1)
res.append(line.index(1)+1) return res
line 배열을 1로 초기화 해준다. 1은 아직 제거안된 요소이고 0은 제거된 요소로 처리
마지막 1개가 남을 때 까지 반복하므로 n-1회 반복한다.
count 변수는 제거되지 않은 원소를 지나온 순서를 카운팅하기 위해 사용한다.
0 ~ 6까지 index가 순회해야하므로, n으로 나눈 나머지 값을 이용한다.
i를 순회하면서 line의 요소가 0이 아니면, 즉 아직 제거되지 않았으면 순서를 카운팅 해준다.
순서를 카운팅 해서 k번째 순서에 도달하면, 반복을 멈추고 해당 index 요소를 0으로 바꾼다. (요소 제거)
해당 index는 0부터 시작했으므로, 결과 배열에 넣어줄 땐 +1을 해준다. 왜냐하면 문제에선 1부터 시작한다 했으니 때문이다.
이렇게 n-1번 반복하게되면 line의 요소는 1개 남는다. 이 때는 index 메서드를 사용하여 1인 요소의 index를 구한 뒤 결과배열에 추가한다. 이 때도 + 1 을 해줘야한다.
functioncalculateDDay(targetDateStr) { // 현재 날짜와 시간을 가져옵니다. const now = newDate(); // 현재 날짜에 시간을 00:00:00으로 설정하여 날짜만 비교하게 합니다. now.setHours(0, 0, 0, 0);
// 목표 날짜를 Date 객체로 변환합니다. const targetDate = newDate(targetDateStr); targetDate.setHours(0, 0, 0, 0);
// 두 날짜의 차이를 밀리초 단위로 계산한 후 일(day) 단위로 변환합니다. const diffMilliseconds = targetDate.getTime() - now.getTime(); const diffDays = diffMilliseconds / (1000 * 60 * 60 * 24);