programming / algorithms

[Programmers school] 코딩 기초 트레이닝 Day 7

2023년 09월 13일

true

반복문 개념(for, while)을 응용한 문제를 풀었습니다.

1. 수열과 구간 쿼리 4

정수 배열 arr와 2차원 정수 배열 queries이 주어집니다. queries의 원소는 각각 하나의 query를 나타내며, [s, e, k] 꼴입니다.
각 query마다 순서대로 s ≤ i ≤ e인 모든 i에 대해 i가 k의 배수이면 arr[i]에 1을 더합니다.
위 규칙에 따라 queries를 처리한 이후의 arr를 return 하는 solution 함수를 완성해 주세요.

1 ≤ arr의 길이 ≤ 1,000
- 0 ≤ arr의 원소 ≤ 1,000,000
1 ≤ queries의 길이 ≤ 1,000
- 0 ≤ s ≤ e < arr의 길이
- 0 ≤ k ≤ 5

arr	queries	result
[0, 1, 2, 4, 3]	[[0, 4, 1],[0, 3, 2],[0, 3, 3]]	[3, 2, 4, 6, 4]

입출력 예 설명

입출력 예 #1

각 쿼리에 따라 arr가 다음과 같이 변합니다.

arr
[0, 1, 2, 4, 3]
[1, 2, 3, 5, 4]
[2, 2, 4, 5, 4]
[3, 2, 4, 6, 4]

따라서 [3, 2, 4, 6, 4]를 return 합니다.

def solution(arr, queries):
    answer = []
    return answer

queries에 있는 각각의 list를 query로 받아서 판단근거로 사용
i 는 s보다 크면서 e보다 작은 숫자
이 int 인 i가 k의 배수인 경우, arr[i] 에 +1 을 해야 함

for문으로 queries에 대해 query들을 추출
추출된 query로 s, e+1 범위 만큼 iteration하면서 i가 k의 배수인지 판단.
만약 i가 k의 배수라고 판단되면 arr[i] 에 + 1

def solution(arr, queries):
		# queries 내의 각 list 불러오기
    for query in queries:
				# 개별 list를 query로 불러오기
        s, e, k = query
				# s ≤ i ≤ e인 모든 i 찾기
        for i in range(s, e + 1):
            if i % k == 0:  # i가 k의 배수인지 확인
                arr[i] += 1  # k의 배수면 arr[i]에 1을 +
    return arr

테스트 1
입력값 〉	[0, 1, 2, 4, 3], [[0, 4, 1], [0, 3, 2], [0, 3, 3]]
기댓값 〉	[3, 2, 4, 6, 4]
실행 결과 〉	테스트를 통과하였습니다.

처음엔 어제 풀었던 문제 처럼 arr[s:k+1] 같은식으로 추출한 값들에 대해 판단하도록 작성했는데 i 자체가 리스트로 뽑혀서 제대로 실행이 되지 않았음
배열과 리스트에 대한 기본적인 이해, 반복문, 조건문, 인덱싱, 슬라이싱, 나머지 연산자 등을 모두 알아야 하고, 문제를 단순화 할수 있어야 풀 수 있는 문제 였따.
막상 코드로 구현해놓고 보니 간단한건데, 처음에 문제를 읽을땐 이해가 어려웠다.
아무리 문제를 쪼갠다고 해도 기본적인 개념(배열, 리스트 등) 이 없으면 이해가 어려울 수 있음을 새삼 느낌
배열이나 리스트 자체에 대한 개념적 인식은 있지만, 그걸 인덱싱, 슬라이싱 할때의 이해가 부족했던 것 같다.

2. 배열 만들기 2

정수 l과 r이 주어졌을 때, l 이상 r이하의 정수 중에서 숫자 “0”과 “5”로만 이루어진 모든 정수를 오름차순으로 저장한 배열을 return 하는 solution 함수를 완성해 주세요.
만약 그러한 정수가 없다면, -1이 담긴 배열을 return 합니다.

• 1 ≤ l ≤ r ≤ 1,000,000

l	r	result
5	555	[5, 50, 55, 500, 505, 550, 555]
10	20	[-1]

입출력 예 #1
- 5 이상 555 이하의 0과 5로만 이루어진 정수는 작은 수부터 5, 50, 55, 500, 505, 550, 555가 있습니다. 따라서 [5, 50, 55, 500, 505, 550, 555]를 return 합니다.
입출력 예 #2
- 10 이상 20 이하이면서 0과 5로만 이루어진 정수는 없습니다. 따라서 [-1]을 return 합니다.

def solution(l, r):
    answer = []
    return answer

주어진 정수 범위내에서 숫자 0 과 5 로 이뤄진 값들이 있는지를 확인해야 함
이 숫자들은 모두 오름차순 정렬되어 배열로 만들어져야 함
해당 되는 숫자가 범위내에 없는 경우 -1을 return해야

배열을 담을 빈 리스트 (answer) 생성
주어진 l과 r을 가지고 for문을 작성하여 iteration
범위내의 정수를 str로 변경
변경된 str에 0 또는 5가 포함되어 있는지 확인 (all함수 사용)
조건이 일치하는 경우 answer 에 append
-1은 함수의 맨 마지막에 return할때 조건문으로 입

def solution(l, r):
    answer = [] # 결과 저장할 빈 리스트 
    for i in range(l, r+1): # 주어진 범위에서 iteration
        # 문자열로 변환 (all 함수가 iterable한 객체만 받을 수 있는데 int는 not iterable함)
        str_i = str(i)
        # 해당 문자열에 "0" 또는 "5" 가 들어 있는지 체크하고 True인 값들만 return
				# all(c in ["0", "5"] for c in str_i) 로 작성할 수 도 있음
        if all(c == "0" or c == "5" for c in str_i):
            answer.append(i)
    return answer if answer else [-1]

테스트 1
입력값 〉	5, 555
기댓값 〉	[5, 50, 55, 500, 505, 550, 555]
실행 결과 〉	테스트를 통과하였습니다.
테스트 2
입력값 〉	10, 20
기댓값 〉	[-1]
실행 결과 〉	테스트를 통과하였습니다.

def solution(l, r):
    # 결과를 담을 빈 리스트 생성
    answer = []
    
    # l부터 r까지의 정수에 대해서 순회
    for i in range(l, r+1):
        # 각 정수 i를 문자열로 변환하고, 그 문자열을 set으로 만든 뒤, {"0", "5"}의 부분집합인지 판단
        if set(str(i)).issubset({"0", "5"}):
            # 조건을 만족하면 answer 리스트에 추가
            answer.append(i)
    
    # 결과 리스트가 비어있지 않으면 그대로 반환, 비어있다면 [-1] 반환
    return answer if answer else [-1]

print(solution(5, 555))

범위내에서 추출한 정수 i를 문자열로 변환한뒤, 각 문자를 set 으로 변환 ( set 은 ‘5’, ‘0’ 이 됨)
issubset({"0", "5"})를 이용해서 i로 만든 set이 ‘0’ 과 ‘5’ 의 부분집합인지 확인
set은 중복된 값을 허용하지 않고, 순서가 존재하지 않는 다는 점을 응용한

0 또는 5가 들어있는 숫자만 추출해야 한다고 해서 처음에는 int인 그 상태에서 어떻게 숫자를 구분하지? 라는 생각에 고민을 좀 오래 했다.
문자든, 숫자든 범위내에 특정 값이 있는지 없는지를 탐색하는것에는 str 상태에서 검색하는게 훨씬 효율적이라는 점을 배웠다.
all() 함수를 어떤 식으로 적용할지 잘 몰랐는데, 이런식으로 응용할 수 있다는 점을 배웠다.

3. 카운트 업

정수 start_num와 end_num가 주어질 때, start_num부터 end_num까지의 숫자를 차례로 담은 리스트를 return하도록 solution 함수를 완성해주세요.

0 ≤ start_num ≤ end_num ≤ 50

start_num	end_num	result
3	10	[3, 4, 5, 6, 7, 8, 9, 10]

입출력 예 #1
- 3부터 10까지의 숫자들을 담은 리스트 [3, 4, 5, 6, 7, 8, 9, 10]를 return합니다.

def solution(start_num, end_num):
    answer = []
    return answer

지정된 범위내에 있는 모든 숫자를 iteration 하면서 각 숫자들을 배열로 만들어야 하는 문제

숫자를 담을 빈 리스트 생성(answer)
for 문으로 start_num ~ end_num 인 범위를 iteration하도록 작성
각 num을 answer 에 append

def solution(start_num, end_num):
    answer = []
    
    for num in range(start_num , end_num + 1):
        answer.append(num)
    return answer

테스트 1
입력값 〉	3, 10
기댓값 〉	[3, 4, 5, 6, 7, 8, 9, 10]
실행 결과 〉	테스트를 통과하였습니다.

간단하게 for문을 알고 있다면 쉽게 풀 수 있는 문제

4. 콜라츠 수열 만들기

모든 자연수 x에 대해서 현재 값이 x이면 x가 짝수일 때는 2로 나누고, x가 홀수일 때는 3 * x + 1로 바꾸는 계산을 계속해서 반복하면 언젠가는 반드시 x가 1이 되는지 묻는 문제를 콜라츠 문제라고 부릅니다.
그리고 위 과정에서 거쳐간 모든 수를 기록한 수열을 콜라츠 수열이라고 부릅니다.
계산 결과 1,000 보다 작거나 같은 수에 대해서는 전부 언젠가 1에 도달한다는 것이 알려져 있습니다.
임의의 1,000 보다 작거나 같은 양의 정수 n이 주어질 때 초기값이 n인 콜라츠 수열을 return 하는 solution 함수를 완성해 주세요.

1 ≤ n ≤ 1,000

n	result
10	[10, 5, 16, 8, 4, 2, 1]

입출력 예 #1

순서대로 연산한 결과를 표로 만들면 다음과 같습니다.

연산 횟수	x	홀짝 여부
0	10	짝수
1	5	홀수
2	16	짝수
3	8	짝수
4	4	짝수
5	2	짝수
6	1	홀수

따라서 [10, 5, 16, 8, 4, 2, 1]을 return 합니다.

def solution(n):
    answer = []
    return answer

현재값을 기준으로 조건부 연산을 하고 그 값을 업데이트 해서 반복하는 작업을 해야 함

while문으로 n이 1이 될때까지 작동하도록 지정
x값이 짝수인지 홀수인지에 따라 조건부 연산 수행
연산을 수행한 결과를 업데이트 하여 while문이 다시 작동하도록 설정

def solution(n):
    answer = [n]  # 초기값 n을 미리 넣어둡니다.
    
    while n != 1:
        if n % 2 == 0:  # n이 짝수일 때
            n = n // 2  # n을 2로 나눈다
        else:  # n이 홀수일 때
            n = 3 * n + 1  # n에 3을 곱하고 1을 더한다
        answer.append(n)  # 변환된 n을 answer에 추가한다
				# 변환된 n이 다시 while문에 적용된다.

    return answer

테스트 1
입력값 〉	10
기댓값 〉	[10, 5, 16, 8, 4, 2, 1]
실행 결과 〉	테스트를 통과하였습니다.

def solution(n):
    answer = []
    
    while n != 1:
        for x in range(n, -1):
            # x가 짝수 일때
            if x % 2 == 0:
                calculated_x = x / 2 # x를 2로 나누기
                answer.append(calculated_x) # x를 2로 나눈 값 append
                n = calculated_x # n 값 update
                
            # x 가 홀수 일때
            elif x % 2 != 0:
                calculated_x = 3 * x + 1 # x에 3을 곱하고 + 1
                answer.append(calculated_x) # x에 3을 곱하고 + 1 한 값 append
                n = calculated_x # n 값 update

    return answer

애초에 for문을 작성하지 않고 while문 내에서 n값을 업데이트 하면서 문제를 해결할 수 있음
그리고 작성한 for문 자체로 인해 무한루프에 빠지게 됨
for x in range(n, -1): 은 어떤 원소도 순회할 수 없음
- range(n, -1) 이 n부터 -1 까지 감소하는 숫자를 생성하는것
- 원래 의도는 n부터 -1씩 감소하는 숫자를 x로 return 하도록 하는 것이 었는데 코드를 잘못 작성함
- for i in range(n, 0, -1) 로 작성했어야 원래 의도대로 작성하는 것
- 따라서 코드상으로는 이미 시작값 n이 -1보다 크거나 같으므로 반복문 자체가 작동하지 않음
- 결국 x 자체가 변하지 않고 n값이 변할 일도 없으므로 while문이 무한루프에 빠질 수 밖에 없는 것

for문에서 range로 내가 원하는 범위 만큼 작동하게 하는 법에 대한 이해가 너무 부족했던 것 같다.
while문을 사용한다고 생각한 포인트는 좋았지만, 결국 제대로 이해를 못하고 있었기 때문에 for문을 중간에 넣는 실수를 하게 된 것

5. 배열 만들기 4

정수 배열 arr가 주어집니다. arr를 이용해 새로운 배열 stk를 만드려고 합니다.
변수 i를 만들어 초기값을 0으로 설정한 후 i가 arr의 길이보다 작으면 다음 작업을 반복합니다.
- 만약 stk가 빈 배열이라면 arr[i]를 stk에 추가하고 i에 1을 더합니다.
- stk에 원소가 있고, stk의 마지막 원소가 arr[i]보다 작으면 arr[i]를 stk의 뒤에 추가하고 i에 1을 더합니다.
- stk에 원소가 있는데 stk의 마지막 원소가 arr[i]보다 크거나 같으면 stk의 마지막 원소를 stk에서 제거합니다.
위 작업을 마친 후 만들어진 stk를 return 하는 solution 함수를 완성해 주세요.

1 ≤ arr의 길이 ≤ 100,000
- 1 ≤ arr의 원소 ≤ 100,000

arr	result
[1, 4, 2, 5, 3]	[1, 2, 3]

입출력 예 #1

각 작업을 마친 후에 배열의 변화를 나타내면 다음 표와 같습니다.

i	arr[i]	stk
0	1	[]
1	4	[1]
2	2	[1, 4]
2	2	[1]
3	5	[1, 2]
4	3	[1, 2, 5]
4	3	[1, 2]
-	-	[1, 2, 3]

따라서 [1, 2, 3]을 return 합니다.

def solution(arr):
    stk = []
    return stk

주어진 배열(arr)을 이용해서 새로운 배열을 생성하는 문제
새로운 배열 (stk)는 조건에 따라 arr 의 원소들을 저장하도록 되어 있음

새로 생성할 배열을 빈 배열로 생성하고, i 값도 초기화
while문을 사용해서 특정 범위내에서 동일 작업을 반복하도록 설정
stk를 만드는 조건별로 조건문 작성

def solution(arr):
    stk = []
    i = 0
    while i < len(arr):
        if not stk:  # stk가 빈 배열인 경우
            stk.append(arr[i])
            i += 1
        elif stk[-1] < arr[i]:  # stk의 마지막 원소가 arr[i]보다 작은 경우
            stk.append(arr[i])
            i += 1
        else:  # stk의 마지막 원소가 arr[i]보다 크거나 같은 경우
            stk.pop()
    return stk

테스트 1
입력값 〉	[1, 4, 2, 5, 3]
기댓값 〉	[1, 2, 3]
실행 결과 〉	테스트를 통과하였습니다.

def solution(arr):
    stk = []
    i = 0
    while i < len(arr):
        if stk == []:
            stk.append(arr[i])
        elif stk != [] and stk[-1] < arr[i]:
            stk.append(arr[i])
            i.append(1)
        elif stk != [] and stk[-1] >= arr[i]:
            stk.pop() # 또는 stk = stk[:-1] 또는 del stk[-1]
    return stk

i에 +1 하는 코드가 잘못되었음
- i.append(1) 이 아니라 i += 1 로 해야 원래 의도대로 작동함
- ~.append() 는 대상이 list일때만 쓰는 것인데 정수를 더해야 하는 것에 append()를 써버림
이로 인해 조건에 해당이 되는 경우임에도 i의 값이 증가되지 않아 무한루프에 빠짐

append에 대한 개념이 명확하지 않으니까 이런 실수를 하는 것
문제 풀이 계획은 나쁘지 않았는데 잔실수가 많았다.
사실 문제 자체가 그렇게 어려운 문제는 아니었음

반복문 개념(for, while)을 응용한 문제를 풀었습니다.

1. 수열과 구간 쿼리 4

정수 배열 arr와 2차원 정수 배열 queries이 주어집니다. queries의 원소는 각각 하나의 query를 나타내며, [s, e, k] 꼴입니다.
각 query마다 순서대로 s ≤ i ≤ e인 모든 i에 대해 i가 k의 배수이면 arr[i]에 1을 더합니다.
위 규칙에 따라 queries를 처리한 이후의 arr를 return 하는 solution 함수를 완성해 주세요.

1 ≤ arr의 길이 ≤ 1,000
- 0 ≤ arr의 원소 ≤ 1,000,000
1 ≤ queries의 길이 ≤ 1,000
- 0 ≤ s ≤ e < arr의 길이
- 0 ≤ k ≤ 5

arr	queries	result
[0, 1, 2, 4, 3]	[[0, 4, 1],[0, 3, 2],[0, 3, 3]]	[3, 2, 4, 6, 4]

입출력 예 설명

입출력 예 #1

각 쿼리에 따라 arr가 다음과 같이 변합니다.

arr
[0, 1, 2, 4, 3]
[1, 2, 3, 5, 4]
[2, 2, 4, 5, 4]
[3, 2, 4, 6, 4]

따라서 [3, 2, 4, 6, 4]를 return 합니다.

def solution(arr, queries):
    answer = []
    return answer

queries에 있는 각각의 list를 query로 받아서 판단근거로 사용
i 는 s보다 크면서 e보다 작은 숫자
이 int 인 i가 k의 배수인 경우, arr[i] 에 +1 을 해야 함

for문으로 queries에 대해 query들을 추출
추출된 query로 s, e+1 범위 만큼 iteration하면서 i가 k의 배수인지 판단.
만약 i가 k의 배수라고 판단되면 arr[i] 에 + 1

def solution(arr, queries):
		# queries 내의 각 list 불러오기
    for query in queries:
				# 개별 list를 query로 불러오기
        s, e, k = query
				# s ≤ i ≤ e인 모든 i 찾기
        for i in range(s, e + 1):
            if i % k == 0:  # i가 k의 배수인지 확인
                arr[i] += 1  # k의 배수면 arr[i]에 1을 +
    return arr

테스트 1
입력값 〉	[0, 1, 2, 4, 3], [[0, 4, 1], [0, 3, 2], [0, 3, 3]]
기댓값 〉	[3, 2, 4, 6, 4]
실행 결과 〉	테스트를 통과하였습니다.

처음엔 어제 풀었던 문제 처럼 arr[s:k+1] 같은식으로 추출한 값들에 대해 판단하도록 작성했는데 i 자체가 리스트로 뽑혀서 제대로 실행이 되지 않았음
배열과 리스트에 대한 기본적인 이해, 반복문, 조건문, 인덱싱, 슬라이싱, 나머지 연산자 등을 모두 알아야 하고, 문제를 단순화 할수 있어야 풀 수 있는 문제 였따.
막상 코드로 구현해놓고 보니 간단한건데, 처음에 문제를 읽을땐 이해가 어려웠다.
아무리 문제를 쪼갠다고 해도 기본적인 개념(배열, 리스트 등) 이 없으면 이해가 어려울 수 있음을 새삼 느낌
배열이나 리스트 자체에 대한 개념적 인식은 있지만, 그걸 인덱싱, 슬라이싱 할때의 이해가 부족했던 것 같다.

2. 배열 만들기 2

정수 l과 r이 주어졌을 때, l 이상 r이하의 정수 중에서 숫자 “0”과 “5”로만 이루어진 모든 정수를 오름차순으로 저장한 배열을 return 하는 solution 함수를 완성해 주세요.
만약 그러한 정수가 없다면, -1이 담긴 배열을 return 합니다.

• 1 ≤ l ≤ r ≤ 1,000,000

l	r	result
5	555	[5, 50, 55, 500, 505, 550, 555]
10	20	[-1]

입출력 예 #1
- 5 이상 555 이하의 0과 5로만 이루어진 정수는 작은 수부터 5, 50, 55, 500, 505, 550, 555가 있습니다. 따라서 [5, 50, 55, 500, 505, 550, 555]를 return 합니다.
입출력 예 #2
- 10 이상 20 이하이면서 0과 5로만 이루어진 정수는 없습니다. 따라서 [-1]을 return 합니다.

def solution(l, r):
    answer = []
    return answer

주어진 정수 범위내에서 숫자 0 과 5 로 이뤄진 값들이 있는지를 확인해야 함
이 숫자들은 모두 오름차순 정렬되어 배열로 만들어져야 함
해당 되는 숫자가 범위내에 없는 경우 -1을 return해야

배열을 담을 빈 리스트 (answer) 생성
주어진 l과 r을 가지고 for문을 작성하여 iteration
범위내의 정수를 str로 변경
변경된 str에 0 또는 5가 포함되어 있는지 확인 (all함수 사용)
조건이 일치하는 경우 answer 에 append
-1은 함수의 맨 마지막에 return할때 조건문으로 입

def solution(l, r):
    answer = [] # 결과 저장할 빈 리스트 
    for i in range(l, r+1): # 주어진 범위에서 iteration
        # 문자열로 변환 (all 함수가 iterable한 객체만 받을 수 있는데 int는 not iterable함)
        str_i = str(i)
        # 해당 문자열에 "0" 또는 "5" 가 들어 있는지 체크하고 True인 값들만 return
				# all(c in ["0", "5"] for c in str_i) 로 작성할 수 도 있음
        if all(c == "0" or c == "5" for c in str_i):
            answer.append(i)
    return answer if answer else [-1]

테스트 1
입력값 〉	5, 555
기댓값 〉	[5, 50, 55, 500, 505, 550, 555]
실행 결과 〉	테스트를 통과하였습니다.
테스트 2
입력값 〉	10, 20
기댓값 〉	[-1]
실행 결과 〉	테스트를 통과하였습니다.

def solution(l, r):
    # 결과를 담을 빈 리스트 생성
    answer = []
    
    # l부터 r까지의 정수에 대해서 순회
    for i in range(l, r+1):
        # 각 정수 i를 문자열로 변환하고, 그 문자열을 set으로 만든 뒤, {"0", "5"}의 부분집합인지 판단
        if set(str(i)).issubset({"0", "5"}):
            # 조건을 만족하면 answer 리스트에 추가
            answer.append(i)
    
    # 결과 리스트가 비어있지 않으면 그대로 반환, 비어있다면 [-1] 반환
    return answer if answer else [-1]

print(solution(5, 555))

범위내에서 추출한 정수 i를 문자열로 변환한뒤, 각 문자를 set 으로 변환 ( set 은 ‘5’, ‘0’ 이 됨)
issubset({"0", "5"})를 이용해서 i로 만든 set이 ‘0’ 과 ‘5’ 의 부분집합인지 확인
set은 중복된 값을 허용하지 않고, 순서가 존재하지 않는 다는 점을 응용한

0 또는 5가 들어있는 숫자만 추출해야 한다고 해서 처음에는 int인 그 상태에서 어떻게 숫자를 구분하지? 라는 생각에 고민을 좀 오래 했다.
문자든, 숫자든 범위내에 특정 값이 있는지 없는지를 탐색하는것에는 str 상태에서 검색하는게 훨씬 효율적이라는 점을 배웠다.
all() 함수를 어떤 식으로 적용할지 잘 몰랐는데, 이런식으로 응용할 수 있다는 점을 배웠다.

3. 카운트 업

정수 start_num와 end_num가 주어질 때, start_num부터 end_num까지의 숫자를 차례로 담은 리스트를 return하도록 solution 함수를 완성해주세요.

0 ≤ start_num ≤ end_num ≤ 50

start_num	end_num	result
3	10	[3, 4, 5, 6, 7, 8, 9, 10]

입출력 예 #1
- 3부터 10까지의 숫자들을 담은 리스트 [3, 4, 5, 6, 7, 8, 9, 10]를 return합니다.

def solution(start_num, end_num):
    answer = []
    return answer

지정된 범위내에 있는 모든 숫자를 iteration 하면서 각 숫자들을 배열로 만들어야 하는 문제

숫자를 담을 빈 리스트 생성(answer)
for 문으로 start_num ~ end_num 인 범위를 iteration하도록 작성
각 num을 answer 에 append

def solution(start_num, end_num):
    answer = []
    
    for num in range(start_num , end_num + 1):
        answer.append(num)
    return answer

테스트 1
입력값 〉	3, 10
기댓값 〉	[3, 4, 5, 6, 7, 8, 9, 10]
실행 결과 〉	테스트를 통과하였습니다.

간단하게 for문을 알고 있다면 쉽게 풀 수 있는 문제

4. 콜라츠 수열 만들기

모든 자연수 x에 대해서 현재 값이 x이면 x가 짝수일 때는 2로 나누고, x가 홀수일 때는 3 * x + 1로 바꾸는 계산을 계속해서 반복하면 언젠가는 반드시 x가 1이 되는지 묻는 문제를 콜라츠 문제라고 부릅니다.
그리고 위 과정에서 거쳐간 모든 수를 기록한 수열을 콜라츠 수열이라고 부릅니다.
계산 결과 1,000 보다 작거나 같은 수에 대해서는 전부 언젠가 1에 도달한다는 것이 알려져 있습니다.
임의의 1,000 보다 작거나 같은 양의 정수 n이 주어질 때 초기값이 n인 콜라츠 수열을 return 하는 solution 함수를 완성해 주세요.

1 ≤ n ≤ 1,000

n	result
10	[10, 5, 16, 8, 4, 2, 1]

입출력 예 #1

순서대로 연산한 결과를 표로 만들면 다음과 같습니다.

연산 횟수	x	홀짝 여부
0	10	짝수
1	5	홀수
2	16	짝수
3	8	짝수
4	4	짝수
5	2	짝수
6	1	홀수

따라서 [10, 5, 16, 8, 4, 2, 1]을 return 합니다.

def solution(n):
    answer = []
    return answer

현재값을 기준으로 조건부 연산을 하고 그 값을 업데이트 해서 반복하는 작업을 해야 함

while문으로 n이 1이 될때까지 작동하도록 지정
x값이 짝수인지 홀수인지에 따라 조건부 연산 수행
연산을 수행한 결과를 업데이트 하여 while문이 다시 작동하도록 설정

def solution(n):
    answer = [n]  # 초기값 n을 미리 넣어둡니다.
    
    while n != 1:
        if n % 2 == 0:  # n이 짝수일 때
            n = n // 2  # n을 2로 나눈다
        else:  # n이 홀수일 때
            n = 3 * n + 1  # n에 3을 곱하고 1을 더한다
        answer.append(n)  # 변환된 n을 answer에 추가한다
				# 변환된 n이 다시 while문에 적용된다.

    return answer

테스트 1
입력값 〉	10
기댓값 〉	[10, 5, 16, 8, 4, 2, 1]
실행 결과 〉	테스트를 통과하였습니다.

def solution(n):
    answer = []
    
    while n != 1:
        for x in range(n, -1):
            # x가 짝수 일때
            if x % 2 == 0:
                calculated_x = x / 2 # x를 2로 나누기
                answer.append(calculated_x) # x를 2로 나눈 값 append
                n = calculated_x # n 값 update
                
            # x 가 홀수 일때
            elif x % 2 != 0:
                calculated_x = 3 * x + 1 # x에 3을 곱하고 + 1
                answer.append(calculated_x) # x에 3을 곱하고 + 1 한 값 append
                n = calculated_x # n 값 update

    return answer

애초에 for문을 작성하지 않고 while문 내에서 n값을 업데이트 하면서 문제를 해결할 수 있음
그리고 작성한 for문 자체로 인해 무한루프에 빠지게 됨
for x in range(n, -1): 은 어떤 원소도 순회할 수 없음
- range(n, -1) 이 n부터 -1 까지 감소하는 숫자를 생성하는것
- 원래 의도는 n부터 -1씩 감소하는 숫자를 x로 return 하도록 하는 것이 었는데 코드를 잘못 작성함
- for i in range(n, 0, -1) 로 작성했어야 원래 의도대로 작성하는 것
- 따라서 코드상으로는 이미 시작값 n이 -1보다 크거나 같으므로 반복문 자체가 작동하지 않음
- 결국 x 자체가 변하지 않고 n값이 변할 일도 없으므로 while문이 무한루프에 빠질 수 밖에 없는 것

for문에서 range로 내가 원하는 범위 만큼 작동하게 하는 법에 대한 이해가 너무 부족했던 것 같다.
while문을 사용한다고 생각한 포인트는 좋았지만, 결국 제대로 이해를 못하고 있었기 때문에 for문을 중간에 넣는 실수를 하게 된 것

5. 배열 만들기 4

정수 배열 arr가 주어집니다. arr를 이용해 새로운 배열 stk를 만드려고 합니다.
변수 i를 만들어 초기값을 0으로 설정한 후 i가 arr의 길이보다 작으면 다음 작업을 반복합니다.
- 만약 stk가 빈 배열이라면 arr[i]를 stk에 추가하고 i에 1을 더합니다.
- stk에 원소가 있고, stk의 마지막 원소가 arr[i]보다 작으면 arr[i]를 stk의 뒤에 추가하고 i에 1을 더합니다.
- stk에 원소가 있는데 stk의 마지막 원소가 arr[i]보다 크거나 같으면 stk의 마지막 원소를 stk에서 제거합니다.
위 작업을 마친 후 만들어진 stk를 return 하는 solution 함수를 완성해 주세요.

1 ≤ arr의 길이 ≤ 100,000
- 1 ≤ arr의 원소 ≤ 100,000

arr	result
[1, 4, 2, 5, 3]	[1, 2, 3]

입출력 예 #1

각 작업을 마친 후에 배열의 변화를 나타내면 다음 표와 같습니다.

i	arr[i]	stk
0	1	[]
1	4	[1]
2	2	[1, 4]
2	2	[1]
3	5	[1, 2]
4	3	[1, 2, 5]
4	3	[1, 2]
-	-	[1, 2, 3]

따라서 [1, 2, 3]을 return 합니다.

def solution(arr):
    stk = []
    return stk

주어진 배열(arr)을 이용해서 새로운 배열을 생성하는 문제
새로운 배열 (stk)는 조건에 따라 arr 의 원소들을 저장하도록 되어 있음

새로 생성할 배열을 빈 배열로 생성하고, i 값도 초기화
while문을 사용해서 특정 범위내에서 동일 작업을 반복하도록 설정
stk를 만드는 조건별로 조건문 작성

def solution(arr):
    stk = []
    i = 0
    while i < len(arr):
        if not stk:  # stk가 빈 배열인 경우
            stk.append(arr[i])
            i += 1
        elif stk[-1] < arr[i]:  # stk의 마지막 원소가 arr[i]보다 작은 경우
            stk.append(arr[i])
            i += 1
        else:  # stk의 마지막 원소가 arr[i]보다 크거나 같은 경우
            stk.pop()
    return stk

테스트 1
입력값 〉	[1, 4, 2, 5, 3]
기댓값 〉	[1, 2, 3]
실행 결과 〉	테스트를 통과하였습니다.

def solution(arr):
    stk = []
    i = 0
    while i < len(arr):
        if stk == []:
            stk.append(arr[i])
        elif stk != [] and stk[-1] < arr[i]:
            stk.append(arr[i])
            i.append(1)
        elif stk != [] and stk[-1] >= arr[i]:
            stk.pop() # 또는 stk = stk[:-1] 또는 del stk[-1]
    return stk

i에 +1 하는 코드가 잘못되었음
- i.append(1) 이 아니라 i += 1 로 해야 원래 의도대로 작동함
- ~.append() 는 대상이 list일때만 쓰는 것인데 정수를 더해야 하는 것에 append()를 써버림
이로 인해 조건에 해당이 되는 경우임에도 i의 값이 증가되지 않아 무한루프에 빠짐

append에 대한 개념이 명확하지 않으니까 이런 실수를 하는 것
문제 풀이 계획은 나쁘지 않았는데 잔실수가 많았다.
사실 문제 자체가 그렇게 어려운 문제는 아니었음

Kim Gabe's DS Blog

[Programmers school] 코딩 기초 트레이닝 Day 7

1. 수열과 구간 쿼리 4

2. 배열 만들기 2

3. 카운트 업

4. 콜라츠 수열 만들기

5. 배열 만들기 4

카테고리

태그

댓글