백준 C++ 10989번 수 정렬하기 3 ( 카운팅 정렬 )

며칠째 드라마에 빠져사는 나..

허구인데.. 재미를 위한 흥미요소가 굉장히 많은데도

나는 늘 과몰입하는 거 같다.

 

늘 로맨스를 보며

남주 같은 사람을 만나 오래오래 함께 하고 싶다는 생각으로

.. 하루를 마무리한다.

 

정말 가능할까?

 

나 자신의 값어치가 올라가면... 가능하려나..?

 

아니면 내 허황된 꿈일까

아니면 정말 가능할수도...

---

 

오늘 문제도 이상하다.

 

 

 

정답률 24 퍼...

 

글자수.. 가 천만 개인데..

흠..

많은 거 같지 않은데 아닌가?

그냥 오름차순으로 하면 안 되나??

근데 수가 10000보다 작거나 작은 자연수더라..

이러면 0이 엄청 많아지긴 한다.

 

흠..

일단 그래도 식은 짜봤다.

 

값을 넣어주고..

sort 해주고... 출력해주면 되는 거 아니오!!!!!

 

 

뭐냐말이오!!!!!!!

 

괜히 정답비율이 24 퍼가 아니지...

 

예전에 그 정렬을

기준을 잡아서 오른쪽 왼쪽으로 빼주는 게 있었는데..

이게 뭔가 시간복잡도? 공간복잡도? 이런 게 적었던 거 같은데..

 

기억이 애매하게 난다.

 

sort는 O(N) 개였던 거 같은데..

걘 뭔가 더 짧았던 거 같다.

 

내 친구 인지 씨를 찾아갔다.

 

인지 씨는 내가 이렇게 개떡같이 말해도 찰떡처럼 말해주었다.

퀵 정렬이라고 하던데

이것도 어차피 오류가 난다고 이야기해 주었다.

 

이것은 애초에 천만 개의 글자를 넣기엔

메모리가 넘쳐난다는 사실을 말해주었다.

 

그리고 문제에 좋은 힌트가 있다며 알려주었다.

 

입력되는 범위가 10000 보다 작거나 같은 자연수

 

그래서 글자를 하나하나 세는 게 아니라 글자의 개수를 저장할 것!

 

 

아직도 문법을 제대로 모르는 초짜..

 

ㅋㅋㅋㅋㅋ

물어보니

저렇게 쓰면 벡터 주머니를 10001개를 만든다로 해석한다고 한다..

 

그래서 만약에 벡터 하나를 10001개로 선언하려면

vector <int> v(10001, 0)으로 해줘야 한다고 한다.

 

 

하지만.. 최대크기가 이렇게 주어진 경우

vector보단 그냥 array로 하는 것을 추천한다.

 

조금 가볍고, 빠른 기본 배열이라고 한다.

 

알았어요...

다시 배열로 해볼게오...

 

 

배열로 해봤어..

이중 for문이 마음에 걸리긴 하는데..

 

 

 

아니 출력 초과는 누구시오!!!!!!

 

마음에 걸리는 건 거기가 아니었소

다시 보니까 i < n이면 안될 거 같군..

그럼 arr.size()로 하고 싶은데

왜 안될까...?

 

아니 배열은. size가 안된다고 한다..

벡터만 최신식이라 되는 거였고..

 

그리고 10001이라고 해놓고 뭐 하러 사이즈를 찾냐...

라고 한다..

 

킄..

긁적..

그렇게 제출했더니 성공했다!

 

생각을 달리해야 한다는 것을 알았다.

 

 

---

 

근래 문제를 풀며 알았다.

이제는 뭔가 그냥 구현하는 게 아니다.

뭔가.. 뭔가가 더해진다.

수학적 계산.. 그리고 머리 쓰기... 패턴 파악 등등..

복잡해진다.

 

잘 해내자. 할 수 있어.

넌 할 수 있어.

잘할 거야.

 

\(0^◇^0)/