문제
제한 사항
문제를 보고 든 생각
이 문제를 풀기 전 별 하나짜리 문제에서도 좀 헤맸다는 느낌이 들었다.
아무래도 문제 풀기를 약 2주만에 해서 그런지 문제를 푸는 감이 없어진 것 같다.
물론 원래도 그렇게 있지는 않았지만.
솔직히 그렇게 어려울 거라고 생각이 들지 않았다.
그냥 구현 문제 같았다.
참 이상하게 약수를 어떻게 구할지 생각이 나지를 않았다.
심지어는 혼자서 "약수가 뭐였지" 이랬던 것 같기도 하다.
왜 이럴까^^...
나의 아이디어
마음에 들지 않았지만 이중 for문을 이용했다.
첫 번째 for는 약수를 찾을 정수를 읽을 용도로
두 번째 for는 각 정수의 약수를 찾을 용도로
그리고 약수는 모두 해시테이블에 담았다.
마지막에는 테이블을 정렬한 다음 출력을 시켰다.
결과
table = dict()
a, b = map(int, input().split())
for num in range(a, b + 1):
table[num] = table.get(num, 0) + 1
for i in range(2, int(num**(1/2)) + 1):
if num % i == 0:
table[i] = table.get(i, 0) + 1
# key값 기준 정렬
# print(sorted(table.items(), reverse=True))
# value 값이 같으면 key가 더 작은 걸 출력
table = sorted(table.items(), key=lambda x : (x[1], x[0]), reverse=True)
if table[0][1] == table[-1][1]:
print(table[-1][0])
else:
print(table[0][0])총 11개의 케이스 중 2개에서 런타임 에러, 1개에서 시간초과를 받았다.
물론 이 코드를 시도하기 전에 한 3번의 코드는 더 시도했었다.
이 코드가 내 힘으로 작성하여 제출한 마지막 코드이다.
음, 솔직히 이 문제에 전력을 다했다고 말을 못하겠어서 부끄럽다.
쓸데없는 자존심 때문에, 잘 하지도 못하는데 쉬워보이는 문제를 보면 자만심이 든다.
그리고 뭔가 "이건 진짜 내가 풀어내야겠다."라는 생각이 들지 않았다.
왜 그랬을까.
그래서 조금 생각해보다가 해설을 보았다.
해설을 보고 알게 된 내용
가장 충격적이었던 건, 이게 그리디 알고리즘이었다는 거다.
진짜 생각도 못했다.
구현 문제로 생각하고 계속 코드를 짠 나로서는, 그래서인지 뭘 어떻게 하라는 건지 묘안이 떠오르지 않았다.
알고보니 그냥 문제에 잘못 접근한 거였다.
내가 자만하고 문제에 접근해서 이 문제에 어떻게 접근할지에 대한 생각이 짧았다는 것을 인정한다.
그러지 말자, 다음부터는.
또, 알게 된 내용은 그리디를 사용해서 풀어야 해결이 가능한 문제였어서 이중 for문이 통하지 않았다는 걸 알 수 있었다.
코드를 제출하면서 이중 for문 때문에 시간 초과가 나는 것 같다는 생각은 들었다.
근데 이게 어떻게 이중 for문 없이 풀릴지 떠오르지가 않았다.
그리디라는 걸 알았다면, 더 나았을까?
해설을 보고 알게 된 풀이
a, b = map(int, input().split())
if a != b:
print(2)
else:
a_min = 0
for i in range(2, int(a**(1/2)) + 1):
if a % i == 0:
a_min = i
break
if a_min == 0:
print(a)
else:
print(a_min)이 문제를 해결할 key point는 바로, a와 b가 다를 때 약수의 개수는 가장 많은 건 언제나 2라는 것을 파악하냐였다.
좀 생각해보면 당연하다는 걸 알 수 있다.
a가 3이고 b가 1000일 때, 우리는 a부터 b까지 수를 증가시키면서 약수의 개수를 세야했다.
하지만 그럴 필요가 없었다. 약수의 개수를 따지자면 무조건 2가 제일 많을 수밖에 없다.
이제 남은 건, a와 b가 같을 경우이다.
이때는 어떤 약수가 가장 개수가 많은 약수일까?
a와 b가 11이라고 해보자.
약수는 1과 11이 존재한다.
하지만 1은 제외하라고 했으니 답은 11이다.
a와 b가 9라고 해보자.
약수는 1, 3, 9가 존재한다.
1은 제외하라고 했으니 3과 9가 남는다.
여기에서 가장 작은 수를 고르는 것이니 답은 3이다.
그러니까 정리하면 뭐냐?
a와 b가 같으면?
약수 중 2 이상의 가장 작은 약수를 출력시키면 된다!
느낀점
문제에게 접근할 때 오만하게 다가갔다는 것이 후회된다.
그리고 항상 느끼지만 그리디 알고리즘 문제에 많이 취약하다. 진짜 많이 풀어봐야할 문제 유형이다.
동적계획법도 마찬가지이다.
공부할 게 산더미다.
모르는 게 너무 많다.
하나씩 하면 그래도 채워지겠지?
