Skip to content

Latest commit

ย 

History

History
69 lines (60 loc) ยท 2.92 KB

File metadata and controls

69 lines (60 loc) ยท 2.92 KB

๋ฌธ์ œ๋ช…

๋ฌธ์ œ ๋งํฌ : [๋ฌธ์ œ๋งํฌ]

๋ฌธ์ œ ๋‚ด์šฉ
์–ด๋–ค ์‹๋‹น์—์„œ ๋‘ฅ๊ทผ ํ…Œ์ด๋ธ”์— N๋ช…์˜ ์‚ฌ๋žŒ์ด ์ฐจ๋ก€๋Œ€๋กœ 1,2,..N๋ฒˆ์งธ ์ž๋ฆฌ์— ์•‰์•„์žˆ๋‹ค. ๊ฐ ์‚ฌ๋žŒ๋“ค์€ ์Œ์‹์„ ๋จน๋Š” ์†๋„๊ฐ€ ๋‹ค๋ฅด๊ฑฐ๋‚˜ ๊ฐ™์„ ์ˆ˜ ์žˆ์œผ๋ฉฐ,
์Œ์‹์„ ๋‹ค ๋จน์—ˆ์–ด๋„ ๋งˆ์ฃผํ•˜๊ฒŒ ์•‰์€ ์‚ฌ๋žŒ์ด ๋‚˜์ด๊ฐ€ ๋” ๋งŽ์„ ๊ฒฝ์šฐ ๊ทธ ์‚ฌ๋žŒ์ด ๋‹ค ๋จน์„ ๋•Œ๊นŒ์ง€ ์•‰์•„์„œ ๊ธฐ๋‹ค๋ ค์•ผํ•œ๋‹ค. ์ด๋•Œ, K๋ฒˆ์งธ ์Œ์‹์„ ๋จน๋Š” ์†๋‹˜์ด
๋ช‡๋ฒˆ์งธ๋กœ ์ผ์–ด๋‚˜๋Š”์ง€๋ฅผ return ํ•˜๋Š” solution ํ•จ์ˆ˜๋ฅผ ์™„์„ฑํ•ด ์ฃผ์„ธ์š”.

์ œํ•œ์กฐ๊ฑด
๋ฐฐ์—ด p์˜ ํฌ๊ธฐ : 1,000,000 ์ดํ•˜์˜ ์ž์—ฐ์ˆ˜ ๋ฐฐ์—ด p์˜ ์›์†Œ์˜ ํฌ๊ธฐ : 1๋ณด๋‹ค ํฌ๊ฑฐ๋‚˜ ๊ฐ™๊ณ  ๋ณด๋‹ค 60๋ณด๋‹ค ์ž‘๊ฑฐ๋‚˜ ๊ฐ™์€ ์ •์ˆ˜

์ž…์ถœ๋ ฅ ์˜ˆ
input 7 output 12

์˜ˆ์‹œ1

๋‚ด๊ฐ€ ํ‘ผ ์ฝ”๋“œ
๋‘ฅ๊ทผ ํ…Œ์ด๋ธ”์— ์•‰์•„ ์žˆ๋Š” ์†๋‹˜๋“ค ์ค‘์—์„œ K๋ฒˆ์งธ ์Œ์‹์„ ๋จน๋Š” ์†๋‹˜์„ ์•Œ์•„๋‚ด๊ธฐ ์œ„ํ•ด ์›ํ˜•ํ๋กœ ๊ตฌํ˜„ํ–ˆ๋‹ค. ๊ทธ๋ฆฌ๊ณ  ์Œ์‹์„ ๋‹ค ๋จน์€ ์†๋‹˜๋“ค์€ ํ•ด์‹œ์— ์ €์žฅํ–ˆ๋Š”๋ฐ, ํ•ด์‹œ๋ฅผ ์‚ฌ์šฉํ–ˆ๊ธฐ ๋•Œ๋ฌธ์— ๋” ๋น ๋ฅด๊ฒŒ ๋‹ค ๋จน์€ ์†๋‹˜์„ ์•Œ์•„๋‚ผ ์ˆ˜ ์žˆ๋‹ค. ์–ด์ฉŒ๊ณ  ์ €์ฉŒ๊ณ . ์ „์ฒด์ ์ธ ์‹œ๊ฐ„ ๋ณต์žก๋„๋Š” ์ด ๋ถ€๋ถ„์„ ์ด๋ ‡๊ฒŒ ์ €๋ ‡๊ฒŒ ๊ณ„์‚ฐํ•˜๋ฉด O(NlogN)์ด ๋‚˜์˜จ๋‹ค. ์ด๋Ÿฐ์‹์œผ๋กœ ์ ‘๊ทผํ•ด์„œ ํ’€์—ˆ๋Š”๋ฐ ํ‹€๋ ธ๋‹ค.

๋‚ด๊ฐ€ ํ‘ผ ์ฝ”๋“œ

์ฝ”๋“œ ํ’€์ด ๋ฆฌ๋ทฐ
์ฃผ์–ด์ง„ ํ…Œ์ŠคํŠธ ์ผ€์ด์Šค์˜ ๊ฒฝ์šฐ๋Š” ์ž˜ ํ†ต๊ณผํ•˜๋Š”๋ฐ ๋‚˜๋จธ์ง€ ์ผ€์ด์Šค์—์„œ ํ‹€๋ฆฐ๋‹ค. ์˜ˆ๋ฅผ๋“ค์–ด 9์ผ ๋•Œ๋Š” 11์ด ๋‚˜์˜ค๋Š”๋ฐ ์™œ 11์ด ๋‚˜์˜ค๋Š”์ง€ ๋ชจ๋ฅด๊ฒ ๋‹ค ใ… ใ… 

์ฝ”๋“œ ๋ฆฌ๋ทฐ(์ฝ”๋“œ ๋ฆฌ๋ทฐ๋ฅผ ํ†ตํ•ด ํ•ด๊ฒฐํ–ˆ์„ ์‹œ)
์–ด์ฉŒ๊ณ  ์ €์ฉŒ๊ณ ํ•œ ์ผ€์ด์Šค์—์„œ ์˜ˆ์™ธ์ฒ˜๋ฆฌ๋ฅผ ํ•˜์ง€ ์•Š์•„์„œ ๋ฐ˜๋ก€๊ฐ€ ์กด์žฌํ–ˆ๋‹ค. flag๋ฅผ ์จ์„œ ํ•ด๋‹น ๋ถ€๋ถ„์„ ์ฒดํฌํ•˜๊ณ  ์ƒํƒœ๋ฅผ True๋กœ ๋ฐ”๊ฟ”์ค€๋‹ค.

์ˆ˜์ •ํ•œ ์ฝ”๋“œ

์˜ˆ์‹œ2

๋‚ด๊ฐ€ ํ‘ผ ์ฝ”๋“œ
๋ฌธ์ œ์—์„œ ์ด๋Ÿฌ์ด๋Ÿฌํ•œ ๋ถ€๋ถ„์€ ๋ธŒ๋ฃจํŠธํฌ์‹ฑ์„ ํ†ตํ•ด ๊ตฌํ˜„์„ ํ–ˆ๋Š”๋ฐ ์ด ์กฐ๊ฑด์€ ์–ด๋–ป๊ฒŒ ๊ตฌํ˜„ํ•ด์•ผํ• ์ง€ ๋ชฐ๋ผ์„œ ํ•˜๋ฃจ์ข…์ผ ๋„์ ์˜€๋‹ค. ๋„ˆ๋ฌด ์–ด๋ ต๋‹ค.

๋‚ด๊ฐ€ ํ‘ผ ์ฝ”๋“œ

์ฝ”๋“œ ํ’€์ด ๋ฆฌ๋ทฐ
๋‹ค๋ฅธ ์‚ฌ๋žŒ ํ’€์ด๋ฅผ ์ฐพ์•„๋ดค๋Š”๋ฐ, ์ด๋Ÿฐ์‹์œผ๋กœ ์ ‘๊ทผํ•˜๋”๋ผ. ๊ทธ๋ž˜์„œ ์ผ๋‹จ ํ•ด๋‹น ๊ฐœ๋…์— ๋งž์ถฐ์„œ ๋‹ค์‹œ ๋ฌธ์ œ๋ฅผ ์ ‘๊ทผํ•ด๋ณด๊ณ  ๋„์ ์—ฌ๋ดค์œผ๋‚˜ ๋ง‰ํ˜”๋‹ค.

๋ง‰ํžŒ ๊ฒƒ

  1. ์ˆœ์ฐจ์ ์œผ๋กœ ์ง„ํ–‰๋˜๋Š”๊ฒŒ ์•„๋‹ˆ๋ผ index๋ฅผ ์™”๋‹ค๊ฐ”๋‹คํ•ด์•ผํ•˜๋Š”๋ฐ ์–ด๋–ป๊ฒŒ ์ถ”์ ํ• ์ง€ ๋ชฐ๋ผ์„œ for๋ฌธ์œผ๋กœ ์‚ฝ์งˆ
  2. ์‚ฝ์งˆ์‹œ๊ฐ„์ด ๊ธธ์–ด์ง€๋‹ค๋ณด๋‹ˆ ๊ณ„์† ์˜คํƒ€๋‚ด๊ณ  ์‚ฝ์งˆ

์ฝ”๋“œ ๋ฆฌ๋ทฐ
index๋ฅผ ์ถ”์ ํ•  ์ˆ˜ ์žˆ๋„๋ก ์ž„์˜์˜ ๋ฐฐ์—ด(arr)์„ ๋งŒ๋“ค์–ด์„œ bfs๋ฅผ ์‚ฌ์šฉํ–ˆ๋‹ค.

์ˆ˜์ •ํ•œ ์ฝ”๋“œ

์•Œ๊ฒŒ๋œ ๊ฒƒ

ใ…ใ…๋ชจ๋“ˆ์˜ ใ…‡ใ…‡๋ฉ”์„œ๋“œ
์ˆซ์ž์™€ ๋ฌธ์ž์—ด์ด ์žˆ์„ ๋•Œ ์ด๋Ÿฌ์ด๋Ÿฌํ•œ ๊ธฐ๋Šฅ์„ ํ•ด์„œ ์ด๊ฑธ ๋ฐ˜ํ™˜ํ•ด์คŒ.

>>> s = "1234 test"
>>> s.ใ…‡ใ…‡()
๊ฒฐ๊ณผ1

๊ธฐ์กด์—๋Š” ์ด๋Ÿฐ์ €๋Ÿฌํ•œ ๋ฐฉ๋ฒ•์œผ๋กœ ์ž‘์„ฑํ•ด์•ผํ–ˆ์ง€๋งŒ,

~~~๋Œ€์ถฉ ๊ทธ๋Ÿฐ ์ฝ”๋“œ
๊ฒฐ๊ณผ2

์ˆซ์ž๊ฐ€ ๋“ค์–ด์˜ฌ ๊ฒฝ์šฐ ๊ฐ’์ด ์ด๋ ‡๊ฒŒ ๋ณ€ํ™˜๋˜๊ธฐ ๋•Œ๋ฌธ์— ์•ˆ๋œ๋‹ค.