URL 과제 (java)

요구사항, 해결 방법

• 과제에서 가장 중요한 점은 원본 URL을 고유하고 짧은 URL로 변경하는 방법과, 단축 URL을 원본 URL로 리다이렉트 시키는 방법일 것 입니다.

---

1. 원본 URL을 고유하고 짧은 URL로 변경

• 처음엔 자바의 randomUUID를 사용해서 36자의 고유값을 얻은뒤 앞의 몇글자만 잘라서 사용할려고 했었다.

  
  

  하지만 이렇게 사용하게 된다면 굳이 UUID를 사용할 필요가 있나?
  그리고 36자의 고유한 숫자인데 앞의 몇글자만 사용한다면 고유한 숫자라는 의미가 없어지고 중복이 자주 발생하지 않나?
  라는 멘토님의 질문에 빠르게 생각을 접었다 . . .

  
  

  그럼 random을 사용해서 숫자를 받는다? 이것도 결국 중복이 생기기 마련이다.
  이 문제를 해결하기 위해선 중복이 없는 숫자가 존재해야한다. 그런게 있을까..
  도저히 내 머리론 생각하지 못해서 결국 이 방법에 대해 서치를 했다.
  결과는 허탈했고 조금만 생각을 바꾸면 됐었는데.. 그래서 나온 결과는

  
  
  1. 사용자가 원본 URL을 입력한다.
  2. 원본 URL의 저장순서를 숫자로 나타내는 고유 ID를 생성한다. 예)첫번째->1, 두번째->2, 세번째->3 •••
  3. 고유 ID를 Base62(숫자(0–9), 영문 소문자(a–z), 영문 대문자(A–Z) 총 62개의 문자를 사용해 숫자를 더 짧은 문자열로 변환하는 인코딩 방식)로 변환한다.
  4. 변환된 문자열은 짧은 고유 URL이 된다.
     

  그렇다면 Base62는 정말 신뢰할 수 있을까?
  결론부터 말하면 숫자 ID만 고유하다면 Base62 결과 문자열도 절대 중복되지 않는다.

  
  

  그 이유는 Base62가 서로 다른 숫자를 서로 다른 문자열로 변환하는 1:1 매핑 방식이기 때문이다.

  
  

  즉, 같은 숫자 ID가 아닌 이상 동일한 단축 URL이 생성될 수 없다.
  Base62를 사용한 이유는 영문 대소문자와 숫자만으로 구성되어 URL에서 추가 인코딩 없이 안전하게 사용할 수 있기 때문이다.

  
  

  반면 Base64는 +, /, = 같은 특수문자가 포함되어 URL 경로 및 인코딩 과정에서 문제가 발생할 수 있다.

  
  

  그리고 만약 입력값이 매우 많아진다면 Base62는 긴 문자열을 반환하지 않을까?
  int의 최대값(약 21억)을 표현하면 -> 62^5 < int 최대값 < 62^6
  Base62 기준으로 최대 6글자면 int 범위의 모든 값을 표현할 수 있으므로 이 걱정은 안해도 될 것 같다.

  ---

2. 단축 URL을 원본 URL로 리다이렉트

• 단축 URL을 원본 URL로 되돌리는 과정은 자바의 HashMap 조회 방식과 매우 비슷하다.

  
  

  HashMap이 key를 통해 value를 빠르게 찾듯이, 단축 URL 서비스 역시 단축 URL 코드를 key, 원본 URL을 value로 저장하면 쉽게 리다이렉트 할 수 있을것이다.

  
  

  즉 사용자가 단축 URL로 접근하면, 해당 코드를 key로 조회하여 원본 URL을 찾아 즉시 리다이렉트하는 방식이다.

---

클래스 설계

• Controller
  • 사용자의 입력과 서비스 호출, 출력 전체적인 흐름을 담당하는 클래스
• Service
  • ShortUrlService class : 원본 URL을 받아 단축 URL 생성, 저장, 조회까지 전체 비즈니스 흐름을 담당하는 클래스
  • Base62Converter class : 고유 숫자 ID를 Base62로 변환하여 단축 URL 코드를 생성하는 규칙 클래스(생성 규칙이 변경되더라도 이 클래스만 수정하면 된다.)
• Repository
  • ShortUrlRepository class : 단축 URL 코드와 원본 URL의 매핑 정보를 저장하고 조회하는 저장소
• View
  • InputView, OutputView class : 사용자 입력과 출력을 담당하는 클래스
• Client Class
• 패키지 구조
  

---

성능 분석(Big-O)

• 시간 복잡도 O(1)
  • HashMap을 사용하여 단축 URL 코드를 key로 저장했기 때문에,
    사용자가 단축 URL로 접근하면 key 조회만으로 원본 URL을 즉시 찾을 수 있다.
    따라서 평균 조회 시간 복잡도는 O(1)이다.
• 공간 복잡도 O(n)
  • 저장해야 하는 원본 URL의 개수가 증가할수록
    단축 URL 코드와 원본 URL의 매핑 데이터도 함께 증가한다.
    즉 저장되는 URL 개수에 비례하여 메모리 사용량이 늘어나므로 O(n)이다.

---

전략 설계

• 이번 URL 단축기는 고유 숫자 ID 기반 단축 전략으로 설계했습니다.

  
  

  원본 URL은 그대로 저장하고, 저장 순서를 나타내는 고유 숫자 ID를 생성한 뒤 이를 Base62 문자열로 변환하여 단축 URL 코드를 만든다.

  
  

  이렇게 생성된 단축 URL 코드를 key, 원본 URL을 value로 HashMap에 저장하여 빠른 조회와 리다이렉트를 가능하도록 구성했다.

---

동작 원리

• 1. 용자가 원본 URL을 입력한다.
  2. 저장 순서를 기반으로 고유 숫자 ID를 생성한다.
  3. 생성된 숫자 ID를 Base62로 변환하여 단축 URL 코드를 만든다.
  4. 단축 URL 코드를 key, 원본 URL을 value로 HashMap에 저장한다.
  5. 사용자가 단축 URL로 접근하면 BASE_URL을 제거한 뒤 key로 조회한다.
  6. 조회된 원본 URL로 리다이렉트한다.

---

회고

• 알고리즘 방식의 문제 풀이, 설계가 아직 너무 어렵다.

  
  

  수학적 사고 능력이 거의 없다. 그냥 없다.
  내가 알고리즘 문제를 어려워 하는데 가장 큰 이유는 예를 들어 별찍기 문제(브론즈4)였나? 못풀었다.
  코드 문법을 모르는것도 있겠지만 규칙을 식으로 압축하는 것이 매우 어렵다.

  
  

  이런 문제들을 멘토님과 얘기해봤고 물론 누구나 다 아는 사실이지만 많이 해봐야하는 것.
  하지만 시간만 많이 투자하면 안되고 잘해야한다.
  내가 하고 있는 것에서 뭘 더할 수 있을지 고민하면서 뭔가를 더 해야한다고 하셨다.

  
  

  막막하지만 뭐든지 해봐야겠다..
  그래서 알고리즘을 문제를 풀 때 문제를 풀기 전 바로 코드를 작성하는 것이 아니라 입력-저장-규칙-출력으로 나누고 글로 적은 뒤 문제를 풀어보겠다.
  그리고 문제를 풀기 전,후로 짧더라도 회고식으로 글을 써보겠다.

  
  

  다른 사람의 코드를 보는것도 도움이 된다고 했다.
  내 코드도 의심하면서 잘못된 코드라도 단점을 찾아내고 비교하고.. 조금이라도 늘지 않겠는가..

  
  

  어렵다.. 내가 개발자가 될 수 있을까. . .
  회고는 여기까지 하고 알고리즘 문제 풀러 가보겠습니다.