백준 4673번
안녕하세요?
오늘은 저한테는.. 정말 너무너무너무 힘들었던 백준 4673번 문제를 반성하는 시간을 가져보도록 하겠습니다..ㅎ
문제는 아래와 같습니다.
몇번의 시행착오(?) 끝에 그래도 문제에서 원하는 모든 답을 출력하는 코드를 만들었습니다.
1) 에라토스테네스의 체 기법 응용한 코드
# 1부터 10000까지의 숫자 리스트 생성
num_list = []
for a in range(10000) :
num_list.append(a+1)
# 생성자로부터 새로운 수를 만드는 함수 정의
def d(n) :
n = str(n)
new_n = int(n)
for b in range(len(n)):
b = b+1
new_n = new_n + int(n[-b])
return new_n
# 주어진 숫자(생성자)로부터 만들 수 있는 모든 수를 하나씩 만들며 num_list에서 제거
def cycle(c) :
while 1 :
num = d(c)
if num >= max(num_list) :
break
if num in num_list :
num_list.remove(num)
c = num
# 에라토스테네스의 체 기법 활용
while 1 :
if len(num_list) == 1 :
break
cycle(min(num_list))
print(min(num_list))
num_list.remove(min(num_list))이코드가... 뭐 누군가에겐 굉장히 쉽고 별 것 아닌 것처럼 보일지만.. 머리가 나쁜 저는 진짜 한 4~5시간 고민해서 ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ 짠건데..
출력이 잘 되길래 기쁜 마음으로 검사해봐야지 ^^ 하고 딱 했는데
'시간초과'
OTL ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ
이게 진짜 뭐가 잘못된건지를 모르겠고 이 만까지 가는 계산을 뭐 어떻게 시간을 줄이라는 건데... 라는 생각에 멘탈이 와르르 무너졌었답니다...
그래도 뭐 나름 계산을 줄일려면 어떻게 해야하지? 고민하면서 일일이 계산해서 하나씩 빼던걸 집합 연산으로 바꿔서 다 모아놓고 한번에 확 빼는걸로 바꿔보기도해보고 반복문도 조금조금씩 길이를 줄이긴 했는데..
이게 결과적으로는 하는 방법이 다 똑같은거 같아서 그런건지 조금씩 줄여봐도 코드가 실행되는데 20~30초대가 나오더군요...ㅎ
그래서.. 너무 절망적이어서 일단 그냥 포기하고 냅뒀습니다...
그러고 다음날 문제에 대해 계속 고민하다가 아예 새로운 방법으로 접근해보자 해서 다른 코드를 만들어봤는데..
2) 셀프넘버인지 아닌지 바로 판별해서 출력 (생성자에 의해 생성된 숫자인지 판별하고 출력)
num_list = []
for a in range(10000) :
num_list.append(a+1)
def d(n) :
n = str(n)
new_n = int(n)
for b in range(len(n)):
b = b+1
new_n = new_n + int(n[-b])
return new_n
def check_span(n) :
for i in num_list :
if n != d(i) :
continue
if n == d(i) :
return '생성숫자'
break
for j in num_list :
if not(check_span(j) == '생성숫자') :
print(j)이 코드가 실행해보니까 한 8초 정도 나오더군요!!??
그래서 20초대에서 8초? 와 이건 미쳤다 하고 너무 기쁜마음에 또 채점을 돌렸는데
'시간초과'
ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ
아.... 이게 1~2초대가 나와야 되는 거구나???
지금 나랑 장난하자는 건가?
진짜 두번째코드도 안될때는 멘탈 회복이 아예 안되더군요.....
그래서 도저히 안되겠어서... 같이 공부하는 친구들에게 헬프를 요청했습니다...
그랬더니 오히려 8초대가나온 2번풀이보다 20초대가 나온 1번풀이 접근 방법이 훨씬 좋다더군요..??
아니 근데 도대체 어떻게 시간을 줄이라는 건지 참...
이게 뭔가 좋은 문법이나 방법이 있는 것 같은데 제가 그걸 몰라서 푸는 느낌이라 너무 답답하고 지칠대로 지쳐서 차라리 솔루션을 보고 빨리 배워가는게 맞지 않나..라는 생각이 너무나 지배적이었는데
친구들이 아주 약간의 조언과 포기하지 말라고 말해줘서.. 결국 풀었습니다. . . . . .
(친구들..에게 너무 고맙다는 말을...)
3) 나의 풀이
num_list = list(range(1, 10001))
def d(n) :
n = str(n)
new_n = int(n)
for b in range(len(n)):
b = b+1
new_n = new_n + int(n[-b])
return new_n
def cycle(c) :
while 1 :
num = d(c)
if num >= 10001 :
break
num_list[num-1] = 0
c = num
for i in num_list :
if i > 0 :
cycle(i)
for i in num_list :
if i != 0 :
print(i)저는 몰랐는데 코드에는 '시간복잡도'라는 개념이 존재하더군요...
원래 제 1번풀이는 일일이 생성숫자를 구해서 리스트에서 remove를 했는데 이 리스트의 원소를 일일이 반복적으로 remove하는 과정이 시간이 엄청 오래걸린다고합니다. (리스트에서 원소를 하나 빼고 그 뒤에 있는 원소들의 자리를 한칸씩 앞으로 땡기는 과정을 거치느라)
그래서 생성된 숫자를 remove하지 않고 그 숫자를 0으로 바꾸고 그대로 그자리에 냅두게끔 했습니다.
그리고 나중에 리스트 원소들 중에서 0이 아닌 원소들만 출력하게 했습니다.
그리고 리스트를 만들때 for문을 사용하지 않고 바로 list(range(~~ 를 사용하는게 가능하더군요..ㅋㅋㅋ 몰랐습니다..
하. 이제 맘놓고 다른분들의 솔루션을 보고 제가 어느부분이 부족했나 확인할 수 있겠습니다..ㅎ
1) 구글 풀이 1
numbers = list(range(1,10_001))
remove_list=[] #생성자 리스트
for num in numbers:
for n in str(num):
num += int(n)
if num <= 10_000:
remove_list.append(num)
for remove_num in set(remove_list):
numbers.remove(remove_num)
for self_num in numbers:
print(self_num)생성숫자를 만들때 바로 for문에 str을 박아버리는게 가능하군요...str도 iterable한 객체라는 사실을 새까맣게 잊고있었습니다..ㅋㅋㅋ그리고 이 문제가 함수 알고리즘 부분에 있는 문제인데 함수를 안써서 풀 생각은 전혀못했네요...제가 너무 함수를 써서 풀어야 된다는 생각에서 못벗어났던 것 같습니다.
2) 구글풀이 2
def d(n) :
n = n+ sum( map(int, str(n)) )
return n
nonSelfNum = set()
for i in range(1, 10001) :
nonSelfNum.add(d(i))
for j in range(1, 10001) :
if j not in nonWelfNum :
print(j)와 ㅋㅋㅋㅋㅋㅋㅋstr이 iterable한 객체니까 map 함수에 적용도 이렇게 가능하네요..!!!!!!!놀랍습니다..
오늘 백준 4673 문제를 반성하며 배운 것은
1. 어떤 원소가 일일이 리스트에 체크하고(if ~~ in : ) -> 빼는건(remove) 시간이 굉장히 오래걸리는 연산이다.
=> set으로 한번에 빼거나, 원소를 빼지말고 0으로 바꿔서 푸는 방법으로 바꾸어봤다.. . .
2. str은 iterable한 객체이다.
=> for문을 엄청 짧게 만들 수 있고, map 함수에도 바로 신박하게 적용이 가능하다!