숫자 변환하기
문제 설명
제한사항
입출력 예 및 설명
문제 풀이
방법이 생각이 나지를 않아서 다른 분의 코드(블로그로 이동)를 참고했다.
def solution(x, y, n):
answer = 0
dp = set()
dp.add(x)
poss = False # x로 y를 만들어줄 수 있으면 True로 바꿔줄 거임.
while dp:
if y in dp: # y가 dp안에 있다 -> poss를 True
poss = True
break
dp_new = set() # 꼭 새 저장변수를 만들어서 사용해야함. (아래에 설명 자세히)
for i in dp: # dp에 있는 수에 x2, x3, +n 모든 연산을 해서 새 숫자를 만듦.
if i+n <= y:
dp_new.add(i+n)
if i*2 <= y:
dp_new.add(i*2)
if i*3 <= y:
dp_new.add(i*3)
dp = dp_new # 연산결과를 y와 동일한 수가 있는지 확인할 dp에 할당
answer += 1 # 연산 횟수 1 증가
# while이 끝나는 경우가 2가지 존재
# 1. (9번 line) if y in dp : break
# 2. (16번~ 21번 line) i+n, i*2, i*3 연산결과가 y보다 크면 dp_new에 add를 안 하기 때문에
# 모든 연산결과가 y보다 큰 경우에 dp_new는 빈 set일 것이다.
# 22번 line에 dp = dp_new이기 때문에 빈set을 변수에 재할당을 하고
# 그럼 7번 line에서 while을 돌 때 dp는 비어있기 때문에 False로 while 반복문이 종료된다.
# 따라서 (아래로 연결)
if poss == False: # while을 다 돌았는데도 poss가 False라면 x와 연산으로는 y를 만들 수 없다.
answer = -1
return answer채점 결과
코드 작성 중 만난 오류
다른 분의 코드를 참고를 했는데, dp_y라는 새 set()를 만들어서 dp = dp_y를 해주는 코드였었다. 나는 dp에 dp_y를 재할당하지 않고, 그냥 dp에 계속 add를 하면 될 거라고 생각했었다. 근데 아래와 같은 에러가 발생했다. (이것 말고도 문제가 하나 더 있는데, 만들 수 없는 y일 땐 while 반복문이 안 끝남;)
아래는 ChatGPT의 설명이다.
RuntimeError: Set changed size during iteration
[답변]
파이썬에서 반복 중에 컬렉션을 수정하는 행위는 일반적으로 금지되어 있습니다. 그 이유는 반복 중에 컬렉션의 크기가 변경되면 예측할 수 없는 동작이 발생할 수 있기 때문입니다. 이는 여러 가지 문제를 일으킬 수 있으며, 코드를 이해하고 유지보수하기 어렵게 만들 수 있습니다.
근데, 나는 list를 pop()해서 다시 사용하는 코드를 짠 적이 있는 것 같은데 list에서는 가능한 건가? 싶어서 또 물어봤다.
[답변]
리스트(list)에서는 이 규칙이 덜 엄격하게 적용될 수 있습니다. 리스트는 연속된 메모리 위치에 요소를 저장하므로, 요소를 추가하거나 삭제해도 해당 메모리 위치에 대한 포인터만 조절하면 되기 때문입니다. 따라서 리스트를 반복하면서 요소를 추가하거나 삭제해도 인덱스 관리 등이 뒤에서 처리될 수 있습니다.
(정확하게는 모르겠지만, list에서는 요소를 삭제해도 인덱스 관리가 가능하다고 이해함.)
[답변 이어서,,]
그러나 집합(set)과 사전(dict)은 해시 테이블을 기반으로 하며, 이러한 자료 구조는 특정 순서를 갖지 않습니다. 따라서 요소를 추가하거나 삭제할 때 내부 구조가 바뀔 수 있습니다. 반복 중에 집합이나 사전을 수정하면, 현재 처리 중인 요소와 이후의 요소에 대한 정상적인 반복이 보장되지 않습니다. 이러한 이유로 파이썬에서는 이러한 동작을 금지하고 RuntimeError를 발생시킵니다.
따라서 집합이나 사전을 반복하는 동안에는 수정을 피하고, 대신 새로운 집합이나 사전을 만들어서 필요한 수정을 수행하는 것이 안전한 방법입니다.
이런 에러는 set 뿐만 아니라 dict 자료구조에서도 발생하는데, set과 dict의 경우 list와는 달리 요소의 순서가 없기 때문에 요소를 추가 및 삭제함으로써 set, dict을 수정하게 되면 처음과 같은 순서를 갖지 않게 된다. 따라서 원래 의도하고자 했던 반복이 보장되지 않는다! 이런 경우에 로직에 여러 문제가 일어날 수 있기 때문에 파이썬에서 이것을 방지하고자 runtime에러를 발생시킨다! 라고 이해함
근데 또 궁금한 게, 위 코드에서는 for문에서 사용한 dp를 변경하니까 에러가 난 건데, 그럼 while 조건으로 dp를 사용하는 건 괜찮은 건가?
[답변]
while 루프의 경우에도 원칙적으로는 컬렉션을 수정하는 행위는 피하는 것이 좋습니다. while 루프를 사용하더라도 반복 중에 컬렉션을 수정하면 예상치 못한 동작이 발생할 수 있습니다. 그리고 위의 코드 예시에서도 while 루프 내부에서 for 루프가 dp를 변경하고 있기 때문에 예측할 수 없는 동작이 발생할 수 있습니다.
코드를 안전하게 만들기 위해서는 while 루프에서도 컬렉션을 복사한 후에 수정하는 것이 좋습니다.
결론 : for문이든 while문이든 collection은 수정 안 하는 것이 좋다. for문의 경우 set, dict는 아예 불가능. while은 가능은 하지만 피하는 것이 좋음.
해결방법
새 변수를 만들어서 그 변수를 이용할 것.
이렇게!
문제 출처 : 프로그래머스, 숫자 변환하기, Lv2