[programmers] ์ฒด์ก๋ณต - Java
์ฒด์ก๋ณต ๋๋ ๋ฌธ์ ๋ฅผ ํด๊ฒฐํ๊ธฐ ์ํ ์๋ฐ ์๋ฃจ์
์ ์ค๋ช
ํฉ๋๋ค. ํ์ ์, ๋๋๋นํ ํ์ ๋ฒํธ, ์ฌ๋ฒ ์ฒด์ก๋ณต์ ๊ฐ์ง ํ์ ๋ฒํธ๋ฅผ ์
๋ ฅ๋ฐ์ ์ต๋ํ ๋ง์ ํ์์ด ์ฒด์ก์์
์ ๋ค์ ์ ์๋๋ก ์ฒด์ก๋ณต์ ๋น๋ ค์ฃผ๋ ๋ฐฉ๋ฒ์ ๊ตฌํํฉ๋๋ค. ํ์๋ฒ์ ์ฌ์ฉํ์ฌ ์ธ์ ํ์์ ์ฌ๋ฒ ์ฒด์ก๋ณต์ ํ์ฉํ๋ ๋ฐฉ์์ผ๋ก ๋ฌธ์ ๋ฅผ ํด๊ฒฐํฉ๋๋ค.
Nov 13, 2024
์ฒด์ก๋ณต
๋ฌธ์ ์ค๋ช
์ ์ฌ์๊ฐ์ ๋๋์ด ๋ค์ด, ์ผ๋ถ ํ์์ด ์ฒด์ก๋ณต์ ๋๋๋นํ์ต๋๋ค. ๋คํํ ์ฌ๋ฒ ์ฒด์ก๋ณต์ด ์๋ ํ์์ด ์ด๋ค์๊ฒ ์ฒด์ก๋ณต์ ๋น๋ ค์ฃผ๋ ค ํฉ๋๋ค. ํ์๋ค์ ๋ฒํธ๋ ์ฒด๊ฒฉ ์์ผ๋ก ๋งค๊ฒจ์ ธ ์์ด, ๋ฐ๋ก ์๋ฒํธ์ ํ์์ด๋ ๋ฐ๋ก ๋ท๋ฒํธ์ ํ์์๊ฒ๋ง ์ฒด์ก๋ณต์ ๋น๋ ค์ค ์ ์์ต๋๋ค. ์๋ฅผ ๋ค์ด, 4๋ฒ ํ์์ 3๋ฒ ํ์์ด๋ 5๋ฒ ํ์์๊ฒ๋ง ์ฒด์ก๋ณต์ ๋น๋ ค์ค ์ ์์ต๋๋ค. ์ฒด์ก๋ณต์ด ์์ผ๋ฉด ์์
์ ๋ค์ ์ ์๊ธฐ ๋๋ฌธ์ ์ฒด์ก๋ณต์ ์ ์ ํ ๋น๋ ค ์ต๋ํ ๋ง์ ํ์์ด ์ฒด์ก์์
์ ๋ค์ด์ผ ํฉ๋๋ค.
์ ์ฒด ํ์์ ์ n, ์ฒด์ก๋ณต์ ๋๋๋นํ ํ์๋ค์ ๋ฒํธ๊ฐ ๋ด๊ธด ๋ฐฐ์ด lost, ์ฌ๋ฒ์ ์ฒด์ก๋ณต์ ๊ฐ์ ธ์จ ํ์๋ค์ ๋ฒํธ๊ฐ ๋ด๊ธด ๋ฐฐ์ด reserve๊ฐ ๋งค๊ฐ๋ณ์๋ก ์ฃผ์ด์ง ๋, ์ฒด์ก์์
์ ๋ค์ ์ ์๋ ํ์์ ์ต๋๊ฐ์ return ํ๋๋ก solution ํจ์๋ฅผ ์์ฑํด์ฃผ์ธ์.
์ ํ์ฌํญ
- ์ ์ฒด ํ์์ ์๋ 2๋ช ์ด์ 30๋ช ์ดํ์ ๋๋ค.
- ์ฒด์ก๋ณต์ ๋๋๋นํ ํ์์ ์๋ 1๋ช ์ด์ n๋ช ์ดํ์ด๊ณ ์ค๋ณต๋๋ ๋ฒํธ๋ ์์ต๋๋ค.
- ์ฌ๋ฒ์ ์ฒด์ก๋ณต์ ๊ฐ์ ธ์จ ํ์์ ์๋ 1๋ช ์ด์ n๋ช ์ดํ์ด๊ณ ์ค๋ณต๋๋ ๋ฒํธ๋ ์์ต๋๋ค.
- ์ฌ๋ฒ ์ฒด์ก๋ณต์ด ์๋ ํ์๋ง ๋ค๋ฅธ ํ์์๊ฒ ์ฒด์ก๋ณต์ ๋น๋ ค์ค ์ ์์ต๋๋ค.
- ์ฌ๋ฒ ์ฒด์ก๋ณต์ ๊ฐ์ ธ์จ ํ์์ด ์ฒด์ก๋ณต์ ๋๋๋นํ์ ์ ์์ต๋๋ค. ์ด๋ ์ด ํ์์ ์ฒด์ก๋ณต์ ํ๋๋ง ๋๋๋นํ๋ค๊ณ ๊ฐ์ ํ๋ฉฐ, ๋จ์ ์ฒด์ก๋ณต์ด ํ๋์ด๊ธฐ์ ๋ค๋ฅธ ํ์์๊ฒ๋ ์ฒด์ก๋ณต์ ๋น๋ ค์ค ์ ์์ต๋๋ค.
์ ์ถ๋ ฅ ์
n | lost | reserve | return |
5 | [2, 4] | [1, 3, 5] | 5 |
5 | [2, 4] | [3] | 4 |
3 | [3] | [1] | 2 |
์ ์ถ๋ ฅ ์ ์ค๋ช
์์ #1
1๋ฒ ํ์์ด 2๋ฒ ํ์์๊ฒ ์ฒด์ก๋ณต์ ๋น๋ ค์ฃผ๊ณ , 3๋ฒ ํ์์ด๋ 5๋ฒ ํ์์ด 4๋ฒ ํ์์๊ฒ ์ฒด์ก๋ณต์ ๋น๋ ค์ฃผ๋ฉด ํ์ 5๋ช
์ด ์ฒด์ก์์
์ ๋ค์ ์ ์์ต๋๋ค.
์์ #2
3๋ฒ ํ์์ด 2๋ฒ ํ์์ด๋ 4๋ฒ ํ์์๊ฒ ์ฒด์ก๋ณต์ ๋น๋ ค์ฃผ๋ฉด ํ์ 4๋ช
์ด ์ฒด์ก์์
์ ๋ค์ ์ ์์ต๋๋ค.
solution.java
import java.util.*; class Solution { public int solution(int n, int[] lost, int[] reserve) { // uniforms ๋ฐฐ์ด์ 1๋ก ์ด๊ธฐํ int[] uniforms = new int[n + 1]; Arrays.fill(uniforms, 1); // lost, reserve ๋ฐฐ์ด๋ก uniforms ๋ฐฐ์ด ์ด๊ธฐํ for (int l : lost) { uniforms[l]--; } for (int r : reserve) { uniforms[r]++; } // ๊ฐ๋ฅํ ๊ฒฝ์ฐ ๊ต๋ณต ๋น๋ ค์ฃผ๊ธฐ for (int i = 1; i <= n; i++) { if (uniforms[i] == 0) { // ๋ง์ฝ ์ ๋ํผ์ด ์๋ ํ์์ด๋ผ๋ฉด if (i > 1 && uniforms[i - 1] == 2) { // ์ด์ ํ์ ํ์ธ uniforms[i]++; uniforms[i - 1]--; } else if (i < n && uniforms[i + 1] == 2) { // ๋ค์ ํ์ ํ์ธ uniforms[i]++; uniforms[i + 1]--; } } } // ์ ๋ํผ์ ํ๋ ์ด์ ์์งํ ํ์ ์นด์ดํธ int count = 0; for (int i = 1; i <= n; i++) { if (uniforms[i] > 0) { count++; } } return count; } }
ํต์ฌ ํค์๋
- ๋ฐฐ์ด์ 1๋ก ์ด๊ธฐํํ ํ, ์์ด๋ฒ๋ฆฐ ์์์ ์๋น๋ฅผ ๊ฐ์ ธ์จ ์ฌ๋๋ค์ ์ํํ๋ฉฐ ์ด๊ธฐํ ํ๋ค.
- ๋ฐฐ์ด์ ์ฒ์๋ถํฐ ์ํํ๋ฉฐ ๊ฐ์ด 0์ธ ์ธ๋ฑ์ค์ ์ ๋ค๋ก ๊ฐ์ ์กฐํํ๊ณ , ๋ง์ฝ 2๋ผ๋ฉด ํด๋น ์ธ๋ฑ์ค์ ๊ฐ์ -1, +1ํ๋ฉฐ ์กฐ์ ํ๋ค.
๊ฒฐ๋ก !
- ํ์๋ฒ์ด๋ ํด๋น ์๊ฐ์ ์ต์ ์ธ ๋ต์ ์ ํํ์ฌ ๊ฒฐ๊ณผ๋ฅผ ๋์ถํ๋ ์๊ณ ๋ฆฌ์ฆ์ด๋ค.
- ํด๋น ๋ฌธ์ ์ ๊ฒฝ์ฐ ๋ฐฐ์ด์ ํตํด ์ด์ ์์์ ๋ค์ ์์์ ๊ฒฐ๊ด๊ฐ์ ์ ๊ทผํ๊ณ , ํด๋น ์์์ ๊ฒฐ๊ด๋ฅผ ๋์ถํด๋ผ ์ ์์๋ค.
Share article