Algorithm

[프로그래머스] 두 원 사이의 정수 쌍

Yongbaldae · 2024. 8. 8. 00:55

안녕하십니까.

금일은 교육에서 코딩테스트 모의고사가 있었습니다.

뭐 어려운 문제가 나오지는 않고 레벨1~2에서 나온다고 하길래

전날에 파이썬 재활 겸 몇문제 키보드 좀 두들기다가 잤습니다만....

발렸습니다.

총 세 문제였는데 첫번째 문제는 너무 쉬웠고

두번째 문제가 [프로그래머스 LV.2 두 원 사이의 정수 쌍] , 세번째 문제는 금년도 카카오 코테 기출문제 였네요...

두번째 문제가 100점이 안나오고 계속 70점정도에서 시간초과가 났는데 나중에 확인해보니

반지름이 1,000,000 까지라서 터지는 것 같더군요...

문제자체는 굉장히 익숙합니다. 아마 수능수학을 보신 경험이 있으시다면 한번쯤은 기출문제에서 보셨을

"격자점 세기"

알고리즘 문제를 풀이해주는 대부분의 강의 영상들에서 강조하는 주요 포인트는

"절대 키보드부터 잡지 말라" 입니다.

펜과 종이를 이용해서 문제를 해결하고 키보드로는 그것을 단지 받아적는 듯한 뉘앙스로 풀어야 한다...

라는것인데 이번 문제는 저에게는 오히려 발목을 잡는 포인트가 되어버렸습니다.

옛날에 수능 기출문제집에서 식 몇 개 세운뒤에 엣지부분에서는 격자점을 샤프로 하나하나 찍어보던 그 감성....

"뭐야? 쉽네,,, 대충 2중 for문 잡고서 세면 되겠는데?"

"사분면 전체말고 하나의 사분면에서 격자점을 센 뒤에 4를 곱하자" 라는 아이디어까지는 도달하였으나

격자점을 세는 과정을 손으로 풀다보니 시간 초과가 나도 이중for문에서 생각의 틀이 벗어나지를 못해버렸습니다.

나중에는 피자마냥 y=x를 기준으로 상부만 점을 세서 8을 곱하면 해결이 되려나? 라는 말같지도 않은 생각을 해버린....

다시 풀어보니 for 하나로도 충분히 해결이 되는데 말이죠.... 껄껄

~~말이 너무 많네요.~~ 코드는 아래와 같습니다.

import math

def solution(r1, r2):
    ans = 0
    for i in range(r2):
        b = int(math.sqrt(r2 * r2 - i * i))
        if i < r1:
            s = int(math.sqrt(r1 * r1 - i * i))
            ans += b - s
            if s == math.sqrt(r1 * r1 - i * i):
                ans += 1

        else:
            ans += int(math.sqrt(r2 * r2 - i * i))
    return ans * 4

위와 같이 for를 하나만 써도 되는 아이디어가 어디서 나오느냐? 라고 스스로 다시 물어보니

예전에도 비슷한 문제를 봤던 경험이 있는데 코테에 나오는 대부분의 좌표문제는

축에 평행하게 계산해 나가야한다 라는 느낌을 받았던 기억이 납니다.

y=x 직선위에 존재하는 점을 어쩌구 저쩌구 다 필요없이 그냥 x=0일때, x=1 일때 쭉쭉쭉 나가면서 점을 세버리면 끝나는 문제인 것이죠.

아래는 헛짓거리를 해버린 저의 노트입니다. (~~저기 희미하게 보이는 y=x 그래프가 보이시나요? ㅎㅎㅎㅎ~~)