티스토리 뷰

IT & Programming

[LeetCode] Encode and Decode TinyURL

시부야에 사는 사람 2017.06.16 15:02

아 정말 오랜만이다. 요즘 어디 소개할만한 곳을 잘 가지 않아서 블로그 포스팅을 좀 소홀히 했다. 사실 어딘가 이곳저곳 가긴 했는데.. 와이프 사진만 엄청 찍느라 개인정보 보호 차원.. 사실 애독자 안구 보호 차원에서 올리지 못하고 있었다. 얼마전에 같이 맥주를 마시러 가서, 이곳을 오랜만에 블로그에 올려야겠다!!!! 라고 생각 해서 사진을 찍었으니, 하루만 기다려 주시면 새로운 포스팅이 올라와 있는 것을 보게 될 것이다.


오늘 겨우 잠깐 문제를 풀어 보았다. 회사에서 빡치는 일이 종종 있어서 아무래도 이직을 위해 존나 열심히 살야겠다고 다짐에 다짐을 하는데 실천은 아무래도 쉽지 않군요. 


오늘의 문제는 Encode and Decode TinyURL 이다.

요즘은 인터넷에 다량의 거지같은 웹 사이트/페이지들이 판을 치고 있는 세상이다. 뭐 의미도 알 수 없는 주소, 긴 이름의 사이트 ex1, ex2, ex3 ... 게다가 웹 사이트도 다단계로 되어 있어 어느 한 페이지에 들어가려면 옛날과는 다르게 존나 긴 주소를 치고 들어가야 한다. 이거이거 너무 길다 이거지.. 메신저로 친구들한테 공유해 주고 싶은데 이상한 웹페이지 하나 메신저로 보냈더니 화면 반이상을 차지한다거나... 하는 상황. 

그래서 예를 들자면 유튜브 같이, 공유할 때 주소를 짧게 해주는 것을 만들어 보자는 것이 이 문제의 취지이다.

자 그럼 문제를 풀어보자.

위에가 내가 작성한 소스코드이고, 내가 푼 방식은 이렇다. 좀 무식하게 푼 거 같은데.. 

longUrl 에서 shortUrl 로 변환후에는 6자리 문자의 주소를 가지게 했다. 또한 사용될 수 있는 문자도 '0-9', 'a-z', 'A-Z' 와 같이 총 62개로 했다. 그러므로 토탈 62^6(560억)개의 주소를 변환할 수 있다. 이정도면 충분하겠지? 

이것의 목적은, 긴 주소를 encode 해서 짧은 주소를 내놓는 것은 물론이고, 다른 사람이 encode 된 짧은 주소를 입력했을 때에는 decode 를 통해 긴 주소를 반환해서 제대로 된 사이트로 안내할 수 있는 것이다. 그렇기에 Encode, Decode 작업에 사용될 맵핑테이블은 필요하다고 생각 되었고, 나는 Hashmap 을 이용했다. 

6자리의 짧은 주소를 만들기 위해 랜덤으로 문자를 조합하다가는 언젠가는 긴 주소를 기존에 사용된 짧은 주소로 변환하는 상황이 발생할 수 있고, 그 처리가 귀찮기 때문에 주소를 encode, 저장할 때마다 인덱스를 1씩 증가시키도록 했다 (숫자가 너무 크니 BigInteger). 그 인덱스를 10진수 에서 16진수 등으로 바꾸는 방법을 이용해, 62진법이라는 것으로 변환시켜 짧은 주소를 갖도록 했다. 

내가 생각한 62진법....

0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ


런타임 사진

내 알고리즘의 퍼포먼스는 매우 좋지 않다. 반성해야 한다.

의심되는 곳.

1. 해쉬맵으로 맵핑테이블을 가지고 있다.

2. 인덱스를 유지하고, 62진법으로 변환 한다.

어떻게 푸는 것이 더 빠를까.. 다른 사람들은 어떤식으로 풀었는지 찾아보아야겠다.

댓글
댓글쓰기 폼