[programmers] ์ฒด์œก๋ณต - Java

์ฒด์œก๋ณต ๋„๋‚œ ๋ฌธ์ œ๋ฅผ ํ•ด๊ฒฐํ•˜๊ธฐ ์œ„ํ•œ ์ž๋ฐ” ์†”๋ฃจ์…˜์„ ์„ค๋ช…ํ•ฉ๋‹ˆ๋‹ค. ํ•™์ƒ ์ˆ˜, ๋„๋‚œ๋‹นํ•œ ํ•™์ƒ ๋ฒˆํ˜ธ, ์—ฌ๋ฒŒ ์ฒด์œก๋ณต์„ ๊ฐ€์ง„ ํ•™์ƒ ๋ฒˆํ˜ธ๋ฅผ ์ž…๋ ฅ๋ฐ›์•„ ์ตœ๋Œ€ํ•œ ๋งŽ์€ ํ•™์ƒ์ด ์ฒด์œก์ˆ˜์—…์„ ๋“ค์„ ์ˆ˜ ์žˆ๋„๋ก ์ฒด์œก๋ณต์„ ๋นŒ๋ ค์ฃผ๋Š” ๋ฐฉ๋ฒ•์„ ๊ตฌํ˜„ํ•ฉ๋‹ˆ๋‹ค. ํƒ์š•๋ฒ•์„ ์‚ฌ์šฉํ•˜์—ฌ ์ธ์ ‘ ํ•™์ƒ์˜ ์—ฌ๋ฒŒ ์ฒด์œก๋ณต์„ ํ™œ์šฉํ•˜๋Š” ๋ฐฉ์‹์œผ๋กœ ๋ฌธ์ œ๋ฅผ ํ•ด๊ฒฐํ•ฉ๋‹ˆ๋‹ค.
DriedPollack's avatar
Nov 13, 2024
[programmers] ์ฒด์œก๋ณต - Java

์ฒด์œก๋ณต

๋ฌธ์ œ ์„ค๋ช…

์ ์‹ฌ์‹œ๊ฐ„์— ๋„๋‘‘์ด ๋“ค์–ด, ์ผ๋ถ€ ํ•™์ƒ์ด ์ฒด์œก๋ณต์„ ๋„๋‚œ๋‹นํ–ˆ์Šต๋‹ˆ๋‹ค. ๋‹คํ–‰ํžˆ ์—ฌ๋ฒŒ ์ฒด์œก๋ณต์ด ์žˆ๋Š” ํ•™์ƒ์ด ์ด๋“ค์—๊ฒŒ ์ฒด์œก๋ณต์„ ๋นŒ๋ ค์ฃผ๋ ค ํ•ฉ๋‹ˆ๋‹ค. ํ•™์ƒ๋“ค์˜ ๋ฒˆํ˜ธ๋Š” ์ฒด๊ฒฉ ์ˆœ์œผ๋กœ ๋งค๊ฒจ์ ธ ์žˆ์–ด, ๋ฐ”๋กœ ์•ž๋ฒˆํ˜ธ์˜ ํ•™์ƒ์ด๋‚˜ ๋ฐ”๋กœ ๋’ท๋ฒˆํ˜ธ์˜ ํ•™์ƒ์—๊ฒŒ๋งŒ ์ฒด์œก๋ณต์„ ๋นŒ๋ ค์ค„ ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค. ์˜ˆ๋ฅผ ๋“ค์–ด, 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

More articles

See more posts

๐Ÿ‘จ๐Ÿปโ€๐Ÿ’ปDriedPollack's Blog