1️⃣ 문제
https://school.programmers.co.kr/learn/courses/30/lessons/12923#qna
2️⃣ 풀이
처음 풀었을 땐 정확성 테스트 13번과 효율성 테스트에서 전부 틀렸다고 나왔지만
도로의 길이는 1000000000(십억)까지지만, 블록은 10000000(천만)까지라는 것을 알고 코드를 수정했다
def solution(begin, end):
answer = []
def count(num):
if num < 2:
return 0
result = num
for i in range(2, int(num**0.5)+1):
if num % i == 0 and num // i <= 10000000:
result = i
break
return num // result
for num in range(begin, end+1):
count(num)
return answer
하지만 여전히 실패..☹️
그래서 정답을 구글링해봤는데 내 풀이랑 똑같았다
알고보니 올해 2월에 테스트케이스가 변경되어 예전 코드가 통과되지 않는 것이었음
👉 프로그래머스 질문하기에 '아이스아메리카노'님이 올리신 반례
난 말하는 🥔 라 이해하는데 오래 걸렸지만, 내가 이해한 걸 정리해보겠다
1 * 100,000,015(일억십오) = 5 * 20,000,003(이천만삼)
(이때 n은 1과 5, k는 100000015와 20000003)
- 블록은 1이 적힌 블록부터 숫자를 1씩 증가시키며 순서대로 설치되기 때문에, 처음 일억십오 칸에는 1이 설치되었을 것이다
- 그런데 일억십오는 5의 배수이다. 그러므로 기존에 설치된 1을 빼고 5를 설치했을 것이다
- 따라서 정답은 5가 되어야 한다. 하지만 기존 코드는 1이 정답이었다
문제에서 (n <= 천만)이라고 주어졌지만, k에 대한 조건은 없는데
풀이에는 (k <= 천만) 조건이 들어가 있는 것!!!
내 풀이도 일억십오에 대해 정답이 1로 나왔다.. 따라서 이 부분을 수정해주었다
def solution(begin, end):
answer = []
def count(num):
if num < 2:
return 0
result = 1 # 블록에 적힌 번호 n
for i in range(2, int(num**0.5)+1):
if num % i == 0 and i <= 10000000:
if num // i <= 10000000: # (num//i <= 천만)이면 num//i도 n이 될 수 있음
result = max(result, i, num//i)
else:
result = max(result, i)
return result
for num in range(begin, end+1):
answer.append(count(num))
return answer
항상 생각하는 거지만, 코테 수학 문제는 알고리즘 실력이 느는 느낌이 아닌데 오래 걸린단 말이지🤔
이 문제도 결국 1시간 넘게 걸렸넹
🐥👩💻💰