01-09 18:44
Recent Posts
Recent Comments
Tags
- ICT๋ฉํ ๋ง
- ICT
- Java
- ์จ์ผ๋ํ
- ์๋ฐ
- ์๋์ด๋ ธ
- ํ์ด์๊ณต๋ชจ์
- DATABASE
- TSQL
- API๋ง์ผํ๋ ์ด์ค
- SQL
- ์ด๋ธ์
- Naver Cloud
- python
- ํ๋ก๋ณด๋ ธ
- ์กํ๊ณ
- ๋ฐ์ดํฐ๋ฒ ์ด์ค
- ์คํฝ๋ ํ
- ํ์ด์
- Spring
- ํ์ด์ฌ
- appetizer
- linux
- RaspberryPi
- mysql
- API MarketPlace ๊ธ๋ก๋ฒ ์ํฌํฐ์ฆ
- JOBํ๊ณ
- DB
- ict๊ณต๋ชจ์
- ์คํฝ์ค๋น
- Today
- Total
miinsun
[Algorithm]์๊ณ ๋ฆฌ์ฆ ์๋ฐ_32 ๋งค์ถ์ก์ ์ข ๋ฅ ๋ณธ๋ฌธ
๐ฌ ๋ฌธ์ ์ค๋ช
ํ์์ ์๋น ๋ ์ ๊ณผ์ ์ ์ด์ํฉ๋๋ค. ํ์์๋น ๋ ํ์์๊ฒ N์ผ ๋์์ ๋งค์ถ๊ธฐ๋ก์ ์ฃผ๊ณ ์ฐ์๋ K์ผ ๋์์ ๋งค์ถ์ก์ ์ข ๋ฅ๋ฅผ ๊ฐ ๊ตฌ๊ฐ๋ณ๋ก ๊ตฌํ๋ผ๊ณ ํ์ต๋๋ค.
๋ง์ฝ N=7์ด๊ณ 7์ผ ๊ฐ์ ๋งค์ถ๊ธฐ๋ก์ด ์๋์ ๊ฐ๊ณ , ์ด๋ K=4์ด๋ฉด
20 12 20 10 23 17 10
๊ฐ ์ฐ์ 4์ผ๊ฐ์ ๊ตฌ๊ฐ์ ๋งค์ถ์ข ๋ฅ๋
์ฒซ ๋ฒ์งธ ๊ตฌ๊ฐ์ [20, 12, 20, 10]๋ ๋งค์ถ์ก์ ์ข ๋ฅ๊ฐ 20, 12, 10์ผ๋ก 3์ด๋ค.
๋ ๋ฒ์งธ ๊ตฌ๊ฐ์ [12, 20, 10, 23]๋ ๋งค์ถ์ก์ ์ข ๋ฅ๊ฐ 4์ด๋ค.
์ธ ๋ฒ์งธ ๊ตฌ๊ฐ์ [20, 10, 23, 17]๋ ๋งค์ถ์ก์ ์ข ๋ฅ๊ฐ 4์ด๋ค.
๋ค ๋ฒ์งธ ๊ตฌ๊ฐ์ [10, 23, 17, 10]๋ ๋งค์ถ์ก์ ์ข ๋ฅ๊ฐ 3์ด๋ค.
N์ผ๊ฐ์ ๋งค์ถ๊ธฐ๋ก๊ณผ ์ฐ์๊ตฌ๊ฐ์ ๊ธธ์ด K๊ฐ ์ฃผ์ด์ง๋ฉด ์ฒซ ๋ฒ์งธ ๊ตฌ๊ฐ๋ถํฐ ๊ฐ ๊ตฌ๊ฐ๋ณ ๋งค์ถ์ก์ ์ข ๋ฅ๋ฅผ ์ถ๋ ฅํ๋ ํ๋ก๊ทธ๋จ์ ์์ฑํ์ธ์.
๐จ ์ ์ถ๋ ฅ ์
์ ๋ ฅ - ์ฒซ ์ค์ N(5<=N<=100,000)๊ณผ K(2<=K<=N)๊ฐ ์ฃผ์ด์ง๋๋ค.
๋ ๋ฒ์งธ ์ค์ N๊ฐ์ ์ซ์์ด์ด ์ฃผ์ด์ง๋๋ค. ๊ฐ ์ซ์๋ 500์ดํ์ ์์ด ์๋ ์ ์์ ๋๋ค.
7 4
20 12 20 10 23 17 10
์ถ๋ ฅ - ์ฒซ ์ค์ ๊ฐ ๊ตฌ๊ฐ์ ๋งค์ถ์ก ์ข ๋ฅ๋ฅผ ์์๋๋ก ์ถ๋ ฅํฉ๋๋ค.
3 4 4 3
๐ป Solution.java
import java.util.*;
public class Main {
public ArrayList<Integer> solution(int n, int k, int[] arr) {
ArrayList<Integer> answer = new ArrayList<>();
HashMap<Integer, Integer> HM = new HashMap<>();
for(int i = 0; i < k - 1; i++) {
HM.put(arr[i], HM.getOrDefault(arr[i], 0) + 1);
}
int lt = 0;
for(int rt = k - 1; rt < n; rt++) {
HM.put(arr[rt], HM.getOrDefault(arr[rt], 0) + 1);
answer.add(HM.size());
HM.put(arr[lt], HM.get(arr[lt]) - 1);
if(HM.get(arr[lt]) == 0)
HM.remove(arr[lt]);
lt++;
}
return answer;
}
public static void main(String[] args){
Main main = new Main();
Scanner sc =new Scanner(System.in);
int n = sc.nextInt();
int k = sc.nextInt();
int[] arr = new int [n];
for(int i = 0; i < n; i++) {
arr[i] = sc.nextInt();
}
for(int x : main.solution(n, k, arr)) System.out.print(x + " ");
sc.close();
return ;
}
}
'Algorithm > Java' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
[Algorithm]์๊ณ ๋ฆฌ์ฆ ์๋ฐ_34 K๋ฒ์งธ ํฐ ์ (0) | 2022.01.05 |
---|---|
[Algorithm]์๊ณ ๋ฆฌ์ฆ ์๋ฐ_33 ๋ชจ๋ ์๋๊ทธ๋จ ์ฐพ๊ธฐ (0) | 2022.01.05 |
[Algorithm]์๊ณ ๋ฆฌ์ฆ ์๋ฐ_31 ์๋๊ทธ๋จ(ํด์ฌ) (0) | 2022.01.05 |
[Algorithm]์๊ณ ๋ฆฌ์ฆ ์๋ฐ_30 ํ๊ธ ํ์ฅ(ํด์ฌ) (0) | 2022.01.04 |
[Algorithm]์๊ณ ๋ฆฌ์ฆ ์๋ฐ_29 ์ต๋ ๊ธธ์ด ์ฐ์ ๋ถ๋ถ ์์ด (0) | 2022.01.04 |
Comments