์ฝ๋ฉํ ์คํธ ์ฐ์ต - ํฐ์ผ๋ชฌ
๋น์ ์ ํฐ์ผ๋ชฌ์ ์ก๊ธฐ ์ํ ์ค๋ ์ฌํ ๋์, ํ ๋ฐ์ฌ๋์ ์ฐ๊ตฌ์ค์ ๋์ฐฉํ์ต๋๋ค. ํ ๋ฐ์ฌ๋์ ๋น์ ์๊ฒ ์์ ์ ์ฐ๊ตฌ์ค์ ์๋ ์ด N ๋ง๋ฆฌ์ ํฐ์ผ๋ชฌ ์ค์์ N/2๋ง๋ฆฌ๋ฅผ ๊ฐ์ ธ๊ฐ๋ ์ข๋ค๊ณ ํ์ต๋๋ค.
programmers.co.kr
๐ ๋ฌธ์ ์ค๋ช
๋น์ ์ ํฐ์ผ๋ชฌ์ ์ก๊ธฐ ์ํ ์ค๋ ์ฌํ ๋์, ํ ๋ฐ์ฌ๋์ ์ฐ๊ตฌ์ค์ ๋์ฐฉํ์ต๋๋ค. ํ ๋ฐ์ฌ๋์ ๋น์ ์๊ฒ ์์ ์ ์ฐ๊ตฌ์ค์ ์๋ ์ด N ๋ง๋ฆฌ์ ํฐ์ผ๋ชฌ ์ค์์ N/2๋ง๋ฆฌ๋ฅผ ๊ฐ์ ธ๊ฐ๋ ์ข๋ค๊ณ ํ์ต๋๋ค.
ํ ๋ฐ์ฌ๋ ์ฐ๊ตฌ์ค์ ํฐ์ผ๋ชฌ์ ์ข
๋ฅ์ ๋ฐ๋ผ ๋ฒํธ๋ฅผ ๋ถ์ฌ ๊ตฌ๋ถํฉ๋๋ค. ๋ฐ๋ผ์ ๊ฐ์ ์ข
๋ฅ์ ํฐ์ผ๋ชฌ์ ๊ฐ์ ๋ฒํธ๋ฅผ ๊ฐ์ง๊ณ ์์ต๋๋ค. ์๋ฅผ ๋ค์ด ์ฐ๊ตฌ์ค์ ์ด 4๋ง๋ฆฌ์ ํฐ์ผ๋ชฌ์ด ์๊ณ , ๊ฐ ํฐ์ผ๋ชฌ์ ์ข
๋ฅ ๋ฒํธ๊ฐ [3๋ฒ, 1๋ฒ, 2๋ฒ, 3๋ฒ]์ด๋ผ๋ฉด ์ด๋ 3๋ฒ ํฐ์ผ๋ชฌ ๋ ๋ง๋ฆฌ, 1๋ฒ ํฐ์ผ๋ชฌ ํ ๋ง๋ฆฌ, 2๋ฒ ํฐ์ผ๋ชฌ ํ ๋ง๋ฆฌ๊ฐ ์์์ ๋ํ๋
๋๋ค. ์ด๋, 4๋ง๋ฆฌ์ ํฐ์ผ๋ชฌ ์ค 2๋ง๋ฆฌ๋ฅผ ๊ณ ๋ฅด๋ ๋ฐฉ๋ฒ์ ๋ค์๊ณผ ๊ฐ์ด 6๊ฐ์ง๊ฐ ์์ต๋๋ค.
- ์ฒซ ๋ฒ์งธ(3๋ฒ), ๋ ๋ฒ์งธ(1๋ฒ) ํฐ์ผ๋ชฌ์ ์ ํ
- ์ฒซ ๋ฒ์งธ(3๋ฒ), ์ธ ๋ฒ์งธ(2๋ฒ) ํฐ์ผ๋ชฌ์ ์ ํ
- ์ฒซ ๋ฒ์งธ(3๋ฒ), ๋ค ๋ฒ์งธ(3๋ฒ) ํฐ์ผ๋ชฌ์ ์ ํ
- ๋ ๋ฒ์งธ(1๋ฒ), ์ธ ๋ฒ์งธ(2๋ฒ) ํฐ์ผ๋ชฌ์ ์ ํ
- ๋ ๋ฒ์งธ(1๋ฒ), ๋ค ๋ฒ์งธ(3๋ฒ) ํฐ์ผ๋ชฌ์ ์ ํ
- ์ธ ๋ฒ์งธ(2๋ฒ), ๋ค ๋ฒ์งธ(3๋ฒ) ํฐ์ผ๋ชฌ์ ์ ํ
์ด๋, ์ฒซ ๋ฒ์งธ(3๋ฒ) ํฐ์ผ๋ชฌ๊ณผ ๋ค ๋ฒ์งธ(3๋ฒ) ํฐ์ผ๋ชฌ์ ์ ํํ๋ ๋ฐฉ๋ฒ์ ํ ์ข
๋ฅ(3๋ฒ ํฐ์ผ๋ชฌ ๋ ๋ง๋ฆฌ)์ ํฐ์ผ๋ชฌ๋ง ๊ฐ์ง ์ ์์ง๋ง, ๋ค๋ฅธ ๋ฐฉ๋ฒ๋ค์ ๋ชจ๋ ๋ ์ข
๋ฅ์ ํฐ์ผ๋ชฌ์ ๊ฐ์ง ์ ์์ต๋๋ค. ๋ฐ๋ผ์ ์ ์์์์ ๊ฐ์ง ์ ์๋ ํฐ์ผ๋ชฌ ์ข
๋ฅ ์์ ์ต๋๊ฐ์ 2๊ฐ ๋ฉ๋๋ค.
๋น์ ์ ์ต๋ํ ๋ค์ํ ์ข
๋ฅ์ ํฐ์ผ๋ชฌ์ ๊ฐ์ง๊ธธ ์ํ๊ธฐ ๋๋ฌธ์, ์ต๋ํ ๋ง์ ์ข
๋ฅ์ ํฐ์ผ๋ชฌ์ ํฌํจํด์ N/2๋ง๋ฆฌ๋ฅผ ์ ํํ๋ ค ํฉ๋๋ค. N๋ง๋ฆฌ ํฐ์ผ๋ชฌ์ ์ข
๋ฅ ๋ฒํธ๊ฐ ๋ด๊ธด ๋ฐฐ์ด nums๊ฐ ๋งค๊ฐ๋ณ์๋ก ์ฃผ์ด์ง ๋, N/2๋ง๋ฆฌ์ ํฐ์ผ๋ชฌ์ ์ ํํ๋ ๋ฐฉ๋ฒ ์ค, ๊ฐ์ฅ ๋ง์ ์ข
๋ฅ์ ํฐ์ผ๋ชฌ์ ์ ํํ๋ ๋ฐฉ๋ฒ์ ์ฐพ์, ๊ทธ๋์ ํฐ์ผ๋ชฌ ์ข
๋ฅ ๋ฒํธ์ ๊ฐ์๋ฅผ return ํ๋๋ก solution ํจ์๋ฅผ ์์ฑํด์ฃผ์ธ์.
๐ฅ ์ ํ์ฌํญ
- nums๋ ํฐ์ผ๋ชฌ์ ์ข ๋ฅ ๋ฒํธ๊ฐ ๋ด๊ธด 1์ฐจ์ ๋ฐฐ์ด์ ๋๋ค.
- nums์ ๊ธธ์ด(N)๋ 1 ์ด์ 10,000 ์ดํ์ ์์ฐ์์ด๋ฉฐ, ํญ์ ์ง์๋ก ์ฃผ์ด์ง๋๋ค.
- ํฐ์ผ๋ชฌ์ ์ข ๋ฅ ๋ฒํธ๋ 1 ์ด์ 200,000 ์ดํ์ ์์ฐ์๋ก ๋ํ๋ ๋๋ค.
- ๊ฐ์ฅ ๋ง์ ์ข ๋ฅ์ ํฐ์ผ๋ชฌ์ ์ ํํ๋ ๋ฐฉ๋ฒ์ด ์ฌ๋ฌ ๊ฐ์ง์ธ ๊ฒฝ์ฐ์๋, ์ ํํ ์ ์๋ ํฐ์ผ๋ชฌ ์ข ๋ฅ ๊ฐ์์ ์ต๋๊ฐ ํ๋๋ง return ํ๋ฉด ๋ฉ๋๋ค.
๐ ์ ์ถ๋ ฅ ์
nums | result |
[3,1,2,3] | 2 |
[3,3,3,2,2,4] | 3 |
[3,3,3,2,2,2] | 2 |
์ ์ถ๋ ฅ ์ ์ค๋ช
์
์ถ๋ ฅ ์ #1
๋ฌธ์ ์ ์์์ ๊ฐ์ต๋๋ค.
์
์ถ๋ ฅ ์ #2
6๋ง๋ฆฌ์ ํฐ์ผ๋ชฌ์ด ์์ผ๋ฏ๋ก, 3๋ง๋ฆฌ์ ํฐ์ผ๋ชฌ์ ๊ณจ๋ผ์ผ ํฉ๋๋ค.
๊ฐ์ฅ ๋ง์ ์ข
๋ฅ์ ํฐ์ผ๋ชฌ์ ๊ณ ๋ฅด๊ธฐ ์ํด์๋ 3๋ฒ ํฐ์ผ๋ชฌ ํ ๋ง๋ฆฌ, 2๋ฒ ํฐ์ผ๋ชฌ ํ ๋ง๋ฆฌ, 4๋ฒ ํฐ์ผ๋ชฌ ํ ๋ง๋ฆฌ๋ฅผ ๊ณ ๋ฅด๋ฉด ๋๋ฉฐ, ๋ฐ๋ผ์ 3์ return ํฉ๋๋ค.
์
์ถ๋ ฅ ์ #3
6๋ง๋ฆฌ์ ํฐ์ผ๋ชฌ์ด ์์ผ๋ฏ๋ก, 3๋ง๋ฆฌ์ ํฐ์ผ๋ชฌ์ ๊ณจ๋ผ์ผ ํฉ๋๋ค.
๊ฐ์ฅ ๋ง์ ์ข
๋ฅ์ ํฐ์ผ๋ชฌ์ ๊ณ ๋ฅด๊ธฐ ์ํด์๋ 3๋ฒ ํฐ์ผ๋ชฌ ํ ๋ง๋ฆฌ์ 2๋ฒ ํฐ์ผ๋ชฌ ๋ ๋ง๋ฆฌ๋ฅผ ๊ณ ๋ฅด๊ฑฐ๋, ํน์ 3๋ฒ ํฐ์ผ๋ชฌ ๋ ๋ง๋ฆฌ์ 3๋ฒ ํฐ์ผ๋ชฌ ํ ๋ง๋ฆฌ๋ฅผ ๊ณ ๋ฅด๋ฉด ๋ฉ๋๋ค. ๋ฐ๋ผ์ ์ต๋ ๊ณ ๋ฅผ ์ ์๋ ํฐ์ผ๋ชฌ ์ข
๋ฅ์ ์๋ 2์
๋๋ค.
๐คจ ๊ณ ๋ฏผ
- ๋ฌธ์ ์๊ตฌ ์ฌํญ ํ์
- ์ฌ์ฉํ ๋ฐ์ดํฐ ๊ฐ์ฒด ์๊ฐ (HashMap ์ฌ์ฉ!? try !)
- ์ ํ ๊ฐ๋ฅํ ํฌ์ผ๋ชฌ์ ์ด๋ป๊ฒ ๋ฐฐ์ด์์ ์ฒ๋ฆฌํ ์ ์์๊น?
๐ป ์ฝ๋ฉ
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
|
import java.util.HashMap;
class Solution {
public int solution(int[] nums) {
int answer = 0;
// STEP 001. ํด์ฌ๋งต ๋ฐ์ดํฐ ๊ฐ์ฒด ์์ฑ
HashMap<Integer,Integer> hsm = new HashMap<Integer, Integer>();
// STEP 002. ์ ํํ ์ ์๋ ๊ฐ์๋ฅผ ๋ด๋ canPickCnt ๋ณ์ ์ ์ธ
int canPickCnt = nums.length / 2;
// STEP 003. ๊ฑด์๋ฅผ ํฌํจํ์ฌ ํ์ธ์ ํ๊ธฐ์ํด getOrDefault ๋ฉ์๋ ์ฌ์ฉํ์ฌ hsm์ put
for(Integer num : nums) hsm.put(num, hsm.getOrDefault(num, 0)+1);
// ํด์ฌ๋งต ๋๋ฒ๊น
// System.out.println(" ํด์ฌ๋งต ๋ฐ์ดํฐ ํ์ธ : " + hsm.toString());
// STEP 004. ์ ํํ ์ ์๋ ๊ฑด์์ ๋งต์ ๋ด๊ฒจ์๋ ์ฌ์ด์ฆ๋ฅผ ๋น๊ตํ๋ค.
// STEP 004-1. ์ ํ๊ฐ๋ฅํ ๊ฑด์๊ฐ ํด์ฌ๋งต์ ๋ด๊ธด ์ฌ์ด์ฆ๋ณด๋ค ์๊ฑฐ๋ ๊ฐ์๊ฒฝ์ฐ
// STEP 004-2. ์ ํ๊ฐ๋ฅํ ๊ฑด์๋ฅผ ๋ต์์ง ์ธํ
ํ๋ค. (nums len : 6, canPickCnt : 3, hsm size : 3, answer = 3)
// STEP 004-3. ๋ง์ฝ ํด์ฌ๋งต์ ์ฌ์ด์ฆ๊ฐ ์ ํ๊ฐ๋ฅํ ๊ฑด์๋ณด๋ค ํฐ ๊ฒฝ์ฐ์๋
// STEP 004-4. ํด์ฌ๋งต์ ์ฌ์ด์ฆ๋ฅผ ๋ต์์ง ์ธํ
ํ๋ค. (nums len : 6, canPickCnt : 3, hsm size : 2, answer = 2)
if(canPickCnt <= hsm.size()) answer = canPickCnt;
else answer = hsm.size();
return answer;
}
}
|
cs |
๐ ์ฑ์
โฑ ์์์๊ฐ ๋ฐ ํ๊ธฐ
์ฝ 3์๊ฐ ์์ ๋ต์์ง ์ธํ ์ ์ํด ํฌ๊ธฐ ๋น๊ตํ ์๊ฐ ํ๋๋ฐ ๊น์ง ์๊ฐ์ด ๊ฝค ๋ง์ด ๊ฑธ๋ ธ๋ค.
์ด๋ ค์ด ๋ฌธ์ ๋ ์๋์์ง๋ง ํจ์จ์ฑ์ ์๊ฐํ์ง ๋ชปํ๊ณ ์๋ฃํ์ ์ ํํ๊ณ , ๋ถํ์ํ๊ฒ ๋ฉ์๋ ์ฌ์ฉ์ ํ ๊ฒ ๊ฐ๋ค.