1047: 몇 가지 음악을 듣고 있을까

Link : judge.koreatech.ac.kr/problem.php?id=1047

---

1. 문제

• 평소 음악을 즐겨듣는 한기인은 닥치는 대로 음악을 모아 두었습니다(물룬 굿 다운로더 입니다 훗훗). 어느날 음악을 듣는데 자꾸 같은 음악이 여러번 반복되는걸 알게 되었습니다.
  닥치는 대로 음악을 받다보니 같은 음악도 여러개 받아 두었던 거죠. 기인이는 가지고 있는 음악이 몇가지 인지 알고 싶어했습니다. 이번에 정리하고 다음부터는 같은 음악은 최대한 받지 않기 위해서이기도 하지요.
  문제를 간단히 하기 위해 음악은 숫자로 주어지고, 같은 숫자는 같은 음악을 의미합니다. 한기인이 가지고 있는 음악이 주어졌을때, 중복을 제거하면 총 몇가지의 음악을 가지고 있는지 알려주세요.

 

---

2. 문제의 조건

• 1 <= N <= 100,000 (음악 총 갯수)
• 0 <= i <= 50,000 (음악 번호)

 

---

3. 문제 접근

• 시간 복잡도
  
  시간제한 1초에 N이 10만이니 O(N^1.6)이내의 시간안에 풀면 될 것이라고 생각했습니다.

 

• 아이디어
  
  "중복 제거" 라는 말을 듣고 정렬 후 겹치는 것을 stack으로 삭제하는 것을 처음에 떠올렸습니다.
  하지만 dict을 떠올리게 되면서 "중복을 무시 할 수도 있겠다" 라는 생각을 하였습니다.
  
  즉, 시간 복잡도 O(N)에 해결이 가능합니다!

 

---

4. 풀이 방법

• 들어온 데이터를 dict에 추가한다.
• dict의 길이를 출력한다.

 

---

5. 소스코드

• cjw-git.tistory.com/41

 

---

 

cjw.git@gmail.com