[programmers] ๋ง์น ํ•˜๊ธฐ - Java

ํŽ˜์ธํŠธ๋ฅผ ๋‹ค์‹œ ์น ํ•ด์•ผ ํ•˜๋Š” ๊ตฌ์—ญ์˜ ์ˆ˜๋ฅผ ์ตœ์†Œํ™”ํ•˜๋Š” ๋ฌธ์ œ์—์„œ, ๋กค๋Ÿฌ์˜ ๊ธธ์ด์™€ ๋‹ค์‹œ ์น ํ•ด์•ผ ํ•˜๋Š” ๊ตฌ์—ญ๋“ค์˜ ๋ฒˆํ˜ธ๊ฐ€ ์ฃผ์–ด์ง‘๋‹ˆ๋‹ค. ๋กค๋Ÿฌ๋Š” ๋ฒฝ์—์„œ ๋ฒ—์–ด๋‚˜์ง€ ์•Š๊ณ , ๊ตฌ์—ญ์˜ ์ผ๋ถ€๋ถ„๋งŒ ์น ํ•  ์ˆ˜ ์—†์Šต๋‹ˆ๋‹ค. ๊ฐ ๊ตฌ์—ญ์„ ํ•œ ๋ฒˆ์”ฉ ์น ํ•˜๋ฉด์„œ ํ•„์š”ํ•œ ์„น์…˜์˜ ์ˆ˜๋ฅผ ๊ณ„์‚ฐํ•˜๊ณ , ๊ฐ ์„น์…˜์˜ ์‹œ์ž‘๊ณผ ๋์„ ๊ฐฑ์‹ ํ•˜๋Š” ๋ฐฉ์‹์œผ๋กœ ๋ฌธ์ œ๋ฅผ ํ•ด๊ฒฐํ•ฉ๋‹ˆ๋‹ค.
DriedPollack's avatar
Mar 27, 2024
[programmers] ๋ง์น ํ•˜๊ธฐ - Java

๋ง์น ํ•˜๊ธฐ

๋ฌธ์ œ ์„ค๋ช…

์–ด๋Š ํ•™๊ต์— ํŽ˜์ธํŠธ๊ฐ€ ์น ํ•ด์ง„ ๊ธธ์ด๊ฐ€ n๋ฏธํ„ฐ์ธ ๋ฒฝ์ด ์žˆ์Šต๋‹ˆ๋‹ค. ๋ฒฝ์— ๋™์•„๋ฆฌ ยท ํ•™ํšŒ ํ™๋ณด๋‚˜ ํšŒ์‚ฌ ์ฑ„์šฉ ๊ณต๊ณ  ํฌ์Šคํ„ฐ ๋“ฑ์„ ๊ฒŒ์‹œํ•˜๊ธฐ ์œ„ํ•ด ํ…Œ์ดํ”„๋กœ ๋ถ™์˜€๋‹ค๊ฐ€ ์ฒ ๊ฑฐํ•  ๋•Œ ๋–ผ๋Š” ์ผ์ด ๋งŽ๊ณ  ๊ทธ ๊ณผ์ •์—์„œ ํŽ˜์ธํŠธ๊ฐ€ ๋ฒ—๊ฒจ์ง€๊ณค ํ•ฉ๋‹ˆ๋‹ค. ํŽ˜์ธํŠธ๊ฐ€ ๋ฒ—๊ฒจ์ง„ ๋ฒฝ์ด ๋ณด๊ธฐ ํ‰ํ•ด์ ธ ํ•™๊ต๋Š” ๋ฒฝ์— ํŽ˜์ธํŠธ๋ฅผ ๋ง์น ํ•˜๊ธฐ๋กœ ํ–ˆ์Šต๋‹ˆ๋‹ค.
๋„“์€ ๋ฒฝ ์ „์ฒด์— ํŽ˜์ธํŠธ๋ฅผ ์ƒˆ๋กœ ์น ํ•˜๋Š” ๋Œ€์‹ , ๊ตฌ์—ญ์„ ๋‚˜๋ˆ„์–ด ์ผ๋ถ€๋งŒ ํŽ˜์ธํŠธ๋ฅผ ์ƒˆ๋กœ ์น  ํ•จ์œผ๋กœ์จ ์˜ˆ์‚ฐ์„ ์•„๋ผ๋ ค ํ•ฉ๋‹ˆ๋‹ค. ์ด๋ฅผ ์œ„ํ•ด ๋ฒฝ์„ 1๋ฏธํ„ฐ ๊ธธ์ด์˜ ๊ตฌ์—ญ n๊ฐœ๋กœ ๋‚˜๋ˆ„๊ณ , ๊ฐ ๊ตฌ์—ญ์— ์™ผ์ชฝ๋ถ€ํ„ฐ ์ˆœ์„œ๋Œ€๋กœ 1๋ฒˆ๋ถ€ํ„ฐ n๋ฒˆ๊นŒ์ง€ ๋ฒˆํ˜ธ๋ฅผ ๋ถ™์˜€์Šต๋‹ˆ๋‹ค. ๊ทธ๋ฆฌ๊ณ  ํŽ˜์ธํŠธ๋ฅผ ๋‹ค์‹œ ์น ํ•ด์•ผ ํ•  ๊ตฌ์—ญ๋“ค์„ ์ •ํ–ˆ์Šต๋‹ˆ๋‹ค.
๋ฒฝ์— ํŽ˜์ธํŠธ๋ฅผ ์น ํ•˜๋Š” ๋กค๋Ÿฌ์˜ ๊ธธ์ด๋Š” m๋ฏธํ„ฐ์ด๊ณ , ๋กค๋Ÿฌ๋กœ ๋ฒฝ์— ํŽ˜์ธํŠธ๋ฅผ ํ•œ ๋ฒˆ ์น ํ•˜๋Š” ๊ทœ์น™์€ ๋‹ค์Œ๊ณผ ๊ฐ™์Šต๋‹ˆ๋‹ค.
  • ๋กค๋Ÿฌ๊ฐ€ ๋ฒฝ์—์„œ ๋ฒ—์–ด๋‚˜๋ฉด ์•ˆ ๋ฉ๋‹ˆ๋‹ค.
  • ๊ตฌ์—ญ์˜ ์ผ๋ถ€๋ถ„๋งŒ ํฌํ•จ๋˜๋„๋ก ์น ํ•˜๋ฉด ์•ˆ ๋ฉ๋‹ˆ๋‹ค.
์ฆ‰, ๋กค๋Ÿฌ์˜ ์ขŒ์šฐ์ธก ๋์„ ๊ตฌ์—ญ์˜ ๊ฒฝ๊ณ„์„  ํ˜น์€ ๋ฒฝ์˜ ์ขŒ์šฐ์ธก ๋๋ถ€๋ถ„์— ๋งž์ถ˜ ํ›„ ๋กค๋Ÿฌ๋ฅผ ์œ„์•„๋ž˜๋กœ ์›€์ง์ด๋ฉด์„œ ๋ฒฝ์„ ์น ํ•ฉ๋‹ˆ๋‹ค. ํ˜„์žฌ ํŽ˜์ธํŠธ๋ฅผ ์น ํ•˜๋Š” ๊ตฌ์—ญ๋“ค์„ ์™„์ „ํžˆ ์น ํ•œ ํ›„ ๋ฒฝ์—์„œ ๋กค๋Ÿฌ๋ฅผ ๋–ผ๋ฉฐ, ์ด๋ฅผ ๋ฒฝ์„ ํ•œ ๋ฒˆ ์น ํ–ˆ๋‹ค๊ณ  ์ •์˜ํ•ฉ๋‹ˆ๋‹ค.
ํ•œ ๊ตฌ์—ญ์— ํŽ˜์ธํŠธ๋ฅผ ์—ฌ๋Ÿฌ ๋ฒˆ ์น ํ•ด๋„ ๋˜๊ณ  ๋‹ค์‹œ ์น ํ•ด์•ผ ํ•  ๊ตฌ์—ญ์ด ์•„๋‹Œ ๊ณณ์— ํŽ˜์ธํŠธ๋ฅผ ์น ํ•ด๋„ ๋˜์ง€๋งŒ ๋‹ค์‹œ ์น ํ•˜๊ธฐ๋กœ ์ •ํ•œ ๊ตฌ์—ญ์€ ์ ์–ด๋„ ํ•œ ๋ฒˆ ํŽ˜์ธํŠธ์น ์„ ํ•ด์•ผ ํ•ฉ๋‹ˆ๋‹ค. ์˜ˆ์‚ฐ์„ ์•„๋ผ๊ธฐ ์œ„ํ•ด ๋‹ค์‹œ ์น ํ•  ๊ตฌ์—ญ์„ ์ •ํ–ˆ๋“ฏ ๋งˆ์ฐฌ๊ฐ€์ง€๋กœ ๋กค๋Ÿฌ๋กœ ํŽ˜์ธํŠธ์น ์„ ํ•˜๋Š” ํšŸ์ˆ˜๋ฅผ ์ตœ์†Œํ™”ํ•˜๋ ค๊ณ  ํ•ฉ๋‹ˆ๋‹ค.
์ •์ˆ˜ nm๊ณผ ๋‹ค์‹œ ํŽ˜์ธํŠธ๋ฅผ ์น ํ•˜๊ธฐ๋กœ ์ •ํ•œ ๊ตฌ์—ญ๋“ค์˜ ๋ฒˆํ˜ธ๊ฐ€ ๋‹ด๊ธด ์ •์ˆ˜ ๋ฐฐ์—ด section์ด ๋งค๊ฐœ๋ณ€์ˆ˜๋กœ ์ฃผ์–ด์งˆ ๋•Œ ๋กค๋Ÿฌ๋กœ ํŽ˜์ธํŠธ์น ํ•ด์•ผ ํ•˜๋Š” ์ตœ์†Œ ํšŸ์ˆ˜๋ฅผ return ํ•˜๋Š” solution ํ•จ์ˆ˜๋ฅผ ์ž‘์„ฑํ•ด ์ฃผ์„ธ์š”.

์ œํ•œ์‚ฌํ•ญ

  • 1 โ‰ค m โ‰ค n โ‰ค 100,000
  • 1 โ‰ค section์˜ ๊ธธ์ด โ‰ค n
    • 1 โ‰ค section์˜ ์›์†Œ โ‰ค n
    • section์˜ ์›์†Œ๋Š” ํŽ˜์ธํŠธ๋ฅผ ๋‹ค์‹œ ์น ํ•ด์•ผ ํ•˜๋Š” ๊ตฌ์—ญ์˜ ๋ฒˆํ˜ธ์ž…๋‹ˆ๋‹ค.
    • section์—์„œ ๊ฐ™์€ ์›์†Œ๊ฐ€ ๋‘ ๋ฒˆ ์ด์ƒ ๋‚˜ํƒ€๋‚˜์ง€ ์•Š์Šต๋‹ˆ๋‹ค.
    • section์˜ ์›์†Œ๋Š” ์˜ค๋ฆ„์ฐจ์ˆœ์œผ๋กœ ์ •๋ ฌ๋˜์–ด ์žˆ์Šต๋‹ˆ๋‹ค.

์ž…์ถœ๋ ฅ ์˜ˆ

n
m
section
result
8
4
[2, 3, 6]
2
5
4
[1, 3]
1
4
1
[1, 2, 3, 4]
4

์ž…์ถœ๋ ฅ ์˜ˆ ์„ค๋ช…

์ž…์ถœ๋ ฅ ์˜ˆ #1
  • ์˜ˆ์ œ 1๋ฒˆ์€ 2, 3, 6๋ฒˆ ์˜์—ญ์— ํŽ˜์ธํŠธ๋ฅผ ๋‹ค์‹œ ์น ํ•ด์•ผ ํ•ฉ๋‹ˆ๋‹ค. ๋กค๋Ÿฌ์˜ ๊ธธ์ด๊ฐ€ 4๋ฏธํ„ฐ์ด๋ฏ€๋กœ ํ•œ ๋ฒˆ์˜ ํŽ˜์ธํŠธ์น ์— ์—ฐ์†๋œ 4๊ฐœ์˜ ๊ตฌ์—ญ์„ ์น ํ•  ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค. ์ฒ˜์Œ์— 3, 4, 5, 6๋ฒˆ ์˜์—ญ์— ํŽ˜์ธํŠธ์น ์„ ํ•˜๋ฉด ์น ํ•ด์•ผ ํ•  ๊ณณ์œผ๋กœ 2๋ฒˆ ๊ตฌ์—ญ๋งŒ ๋‚จ๊ณ  1, 2, 3, 4๋ฒˆ ๊ตฌ์—ญ์— ํŽ˜์ธํŠธ์น ์„ ํ•˜๋ฉด 2๋ฒˆ ๋งŒ์— ๋‹ค์‹œ ์น ํ•ด์•ผ ํ•  ๊ณณ์— ๋ชจ๋‘ ํŽ˜์ธํŠธ์น ์„ ํ•  ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค.
    • notion image
      2๋ฒˆ๋ณด๋‹ค ์ ์€ ํšŸ์ˆ˜๋กœ 2, 3, 6๋ฒˆ ์˜์—ญ์— ํŽ˜์ธํŠธ๋ฅผ ๋ง์น ํ•˜๋Š” ๋ฐฉ๋ฒ•์€ ์—†์Šต๋‹ˆ๋‹ค. ๋”ฐ๋ผ์„œ ์ตœ์†Œ ํšŸ์ˆ˜์ธ 2๋ฅผ return ํ•ฉ๋‹ˆ๋‹ค.
์ž…์ถœ๋ ฅ ์˜ˆ #2
  • ์˜ˆ์ œ 2๋ฒˆ์€ 1, 3๋ฒˆ ์˜์—ญ์— ํŽ˜์ธํŠธ๋ฅผ ๋‹ค์‹œ ์น ํ•ด์•ผ ํ•ฉ๋‹ˆ๋‹ค. ๋กค๋Ÿฌ์˜ ๊ธธ์ด๊ฐ€ 4๋ฏธํ„ฐ์ด๋ฏ€๋กœ ํ•œ ๋ฒˆ์˜ ํŽ˜์ธํŠธ์น ์— ์—ฐ์†๋œ 4๊ฐœ์˜ ๊ตฌ์—ญ์„ ์น ํ•  ์ˆ˜ ์žˆ๊ณ  1, 2, 3, 4๋ฒˆ ์˜์—ญ์— ํŽ˜์ธํŠธ์น ์„ ํ•˜๋ฉด ํ•œ ๋ฒˆ์— 1, 3๋ฒˆ ์˜์—ญ์„ ๋ชจ๋‘ ์น ํ•  ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค.
    • notion image
      ๋”ฐ๋ผ์„œ ์ตœ์†Œ ํšŸ์ˆ˜์ธ 1์„ return ํ•ฉ๋‹ˆ๋‹ค.
์ž…์ถœ๋ ฅ ์˜ˆ #3
  • ์˜ˆ์ œ 3๋ฒˆ์€ ๋ชจ๋“  ๊ตฌ์—ญ์— ํŽ˜์ธํŠธ์น ์„ ํ•ด์•ผ ํ•ฉ๋‹ˆ๋‹ค. ๋กค๋Ÿฌ์˜ ๊ธธ์ด๊ฐ€ 1๋ฏธํ„ฐ์ด๋ฏ€๋กœ ํ•œ ๋ฒˆ์— ํ•œ ๊ตฌ์—ญ๋ฐ–์— ์น ํ•  ์ˆ˜ ์—†์Šต๋‹ˆ๋‹ค. ๊ตฌ์—ญ์ด 4๊ฐœ์ด๋ฏ€๋กœ ๊ฐ ๊ตฌ์—ญ์„ ํ•œ ๋ฒˆ์”ฉ๋งŒ ์น ํ•˜๋Š” 4๋ฒˆ์ด ์ตœ์†Œ ํšŸ์ˆ˜๊ฐ€ ๋ฉ๋‹ˆ๋‹ค.
    • notion image
      ๋”ฐ๋ผ์„œ 4๋ฅผ return ํ•ฉ๋‹ˆ๋‹ค.

solution.java

import java.util.*; class Solution { public int solution(int n, int m, int[] section) { int start = section[0]; int end = section[0] + (m-1); int ans = 1; for(int i : section){ if(i>=start && i<=end) continue; else{ start = i; end = i + (m-1); ans++; } } return ans; } }
 

ํ•ต์‹ฌ ํ‚ค์›Œ๋“œ

  1. start ๋ณ€์ˆ˜๋ฅผ ์ฒซ ๋ฒˆ์งธ ์„น์…˜์˜ ์‹œ์ž‘ ์ธ๋ฑ์Šค๋กœ ์ดˆ๊ธฐํ™”ํ•˜๊ณ , end ๋ณ€์ˆ˜๋ฅผ ์ฒซ ๋ฒˆ์งธ ์„น์…˜์˜ ๋ ์ธ๋ฑ์Šค๋กœ ์ดˆ๊ธฐํ™”ํ•œ๋‹ค.
  1. ๋ฐฐ์—ด์„ ๋ฐ˜๋ณตํ•˜๋ฉด์„œ ๊ฐ ์›์†Œ๋ฅผ ํ™•์ธํ•œ๋‹ค.
  1. ํ˜„์žฌ ์›์†Œ๊ฐ€ ํ˜„์žฌ ์„น์…˜์— ์†ํ•˜๋Š”์ง€ ํ™•์ธํ•œ๋‹ค. ์†ํ•œ๋‹ค๋ฉด ๊ฑด๋„ˆ๋›ฐ๊ณ  ๋‹ค์Œ ์›์†Œ๋ฅผ ํ™•์ธํ•œ๋‹ค.
  1. ํ˜„์žฌ ์›์†Œ๊ฐ€ ํ˜„์žฌ ์„น์…˜์— ์†ํ•˜์ง€ ์•Š๋Š”๋‹ค๋ฉด, ์ƒˆ๋กœ์šด ์„น์…˜์„ ์‹œ์ž‘ํ•˜๊ฒŒ ๋˜๋ฏ€๋กœ start๋ฅผ ํ˜„์žฌ ์›์†Œ์˜ ์ธ๋ฑ์Šค๋กœ, end๋ฅผ start์—์„œ m-1์„ ๋”ํ•œ ๊ฐ’์œผ๋กœ ๊ฐฑ์‹ ํ•˜๊ณ , ans๋ฅผ 1 ์ฆ๊ฐ€์‹œํ‚จ๋‹ค.
 

๊ฒฐ๋ก !

ํ•ด๋‹น ๋ฌธ์ œ๋ฅผ ํ’€๋ฉด์„œ ์ฒ˜์Œ ์‹œ๋„ํ–ˆ๋˜ ๋ฐฉ์‹์€ ๋‹จ์ˆœํžˆ section์˜ ๊ฐ’๊ณผ ๊ทธ ๋‹ค์Œ ๊ฐ’์„ ๋น„๊ตํ•ด์„œ ๊ทธ ์ฐจ๊ฐ€ m๋ณด๋‹ค ์ž‘์„ ๊ฒฝ์šฐ ๋ฆฌํ„ดํ•  ๊ฐ’์„ ์ฆ๊ฐ€์‹œํ‚ค๋Š” ๋ฐฉ์‹์œผ๋กœ ๊ตฌํ˜„ํ–ˆ๋‹ค. ์ด ๊ฒฝ์šฐ ๋‹ค์‹œ ์น ํ•  ๋‘ ์—ฐ์† ์„น์…˜ ์‚ฌ์ด์˜ ๊ฑฐ๋ฆฌ๊ฐ€ m๋ณด๋‹ค ํฐ ๊ฒฝ์šฐ๋ฅผ ์˜ฌ๋ฐ”๋ฅด๊ฒŒ ์ฒ˜๋ฆฌํ•˜์ง€ ๋ชปํ–ˆ๋‹ค.
์ด๋ฅผ ํ•ด๊ฒฐํ•˜๊ธฐ ์œ„ํ•ด ์ž…๋ ฅ๋œ ๋ฐฐ์—ด์„ ์„น์…˜์œผ๋กœ ๋‚˜๋ˆŒ ๋•Œ๋งˆ๋‹ค ์ƒˆ๋กœ์šด ์„น์…˜์„ ์‹œ์ž‘ํ•˜๊ณ , ๊ฐ ์„น์…˜์˜ ์‹œ์ž‘๊ณผ ๋์„ ๊ฐฑ์‹ ํ•˜๋ฉด์„œ ํ•„์š”ํ•œ ์„น์…˜์˜ ์ˆ˜๋ฅผ ๊ณ„์‚ฐํ•˜๋Š” ๋ฐฉ์‹์„ ์‹œ๋„ํ–ˆ๋‹ค.
 
Share article

More articles

See more posts

[programmers] ๋‰ด์Šค ํด๋Ÿฌ์Šคํ„ฐ๋ง - Java

DriedPollack's avatar
March 26, 2024
[programmers] ๋‰ด์Šค ํด๋Ÿฌ์Šคํ„ฐ๋ง - Java

[์ฝ”๋“œ๋กœ ๋ฐฐ์šฐ๋Š” ์Šคํ”„๋ง ์›น ํ”„๋กœ์ ํŠธ ๊ฐœ์ •ํŒ] 6์žฅ ์ •๋ฆฌ

DriedPollack's avatar
March 26, 2024
[์ฝ”๋“œ๋กœ ๋ฐฐ์šฐ๋Š” ์Šคํ”„๋ง ์›น ํ”„๋กœ์ ํŠธ ๊ฐœ์ •ํŒ] 6์žฅ ์ •๋ฆฌ

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