โœ๏ธ ์ฝ”ํ…Œ ์ค€๋น„/Two Pointer

[ํˆฌํฌ์ธํ„ฐ / Kotlin] BOJ 1806 - ๋ถ€๋ถ„ ํ•ฉ

2021. 12. 26. 20:17
๋ชฉ์ฐจ
  1. ๋ฌธ์ œ
  2. ์ž…๋ ฅ
  3. ์ถœ๋ ฅ
  4. ํ•ด๊ฒฐ ๋ฐฉ๋ฒ•
  5. ํ†ต๊ณผ

๋ฌธ์ œ

10,000 ์ดํ•˜์˜ ์ž์—ฐ์ˆ˜๋กœ ์ด๋ฃจ์–ด์ง„ ๊ธธ์ด N์งœ๋ฆฌ ์ˆ˜์—ด์ด ์ฃผ์–ด์ง„๋‹ค. ์ด ์ˆ˜์—ด์—์„œ ์—ฐ์†๋œ ์ˆ˜๋“ค์˜ ๋ถ€๋ถ„ํ•ฉ ์ค‘์— ๊ทธ ํ•ฉ์ด S ์ด์ƒ์ด ๋˜๋Š” ๊ฒƒ ์ค‘, ๊ฐ€์žฅ ์งง์€ ๊ฒƒ์˜ ๊ธธ์ด๋ฅผ ๊ตฌํ•˜๋Š” ํ”„๋กœ๊ทธ๋žจ์„ ์ž‘์„ฑํ•˜์‹œ์˜ค.

์ž…๋ ฅ

์ฒซ์งธ ์ค„์— N (10 โ‰ค N < 100,000)๊ณผ S (0 < S โ‰ค 100,000,000)๊ฐ€ ์ฃผ์–ด์ง„๋‹ค. ๋‘˜์งธ ์ค„์—๋Š” ์ˆ˜์—ด์ด ์ฃผ์–ด์ง„๋‹ค. ์ˆ˜์—ด์˜ ๊ฐ ์›์†Œ๋Š” ๊ณต๋ฐฑ์œผ๋กœ ๊ตฌ๋ถ„๋˜์–ด์ ธ ์žˆ์œผ๋ฉฐ, 10,000์ดํ•˜์˜ ์ž์—ฐ์ˆ˜์ด๋‹ค.

์ถœ๋ ฅ

์ฒซ์งธ ์ค„์— ๊ตฌํ•˜๊ณ ์ž ํ•˜๋Š” ์ตœ์†Œ์˜ ๊ธธ์ด๋ฅผ ์ถœ๋ ฅํ•œ๋‹ค. ๋งŒ์ผ ๊ทธ๋Ÿฌํ•œ ํ•ฉ์„ ๋งŒ๋“œ๋Š” ๊ฒƒ์ด ๋ถˆ๊ฐ€๋Šฅํ•˜๋‹ค๋ฉด 0์„ ์ถœ๋ ฅํ•˜๋ฉด ๋œ๋‹ค.

ํ•ด๊ฒฐ ๋ฐฉ๋ฒ•

์•ž์„  2๋ฌธ์ œ์™€ ๋‹ค๋ฅด๊ฒŒ ์ •๋ ฌ์„ ํ•  ํ•„์š”๊ฐ€ ์—†๋Š” ๋ฌธ์ œ์ด๋‹ค. ์ฃผ์–ด์ง„ ๋ฐฐ์—ด ์ž์ฒด์—์„œ์˜ ๊ฐ€์žฅ ์ž‘์€ ๊ธธ์ด์˜ ๋ถ€๋ถ„ ํ•ฉ์„ ์ฐพ์•„์•ผํ•˜๊ธฐ ๋•Œ๋ฌธ์ด๋‹ค. ์•Œ๊ณ ๋ฆฌ์ฆ˜์€ ์•„๋ž˜์™€ ๊ฐ™๋‹ค.

 

1. left, right๋ฅผ 0์œผ๋กœ ์„ค์ •ํ•˜๊ณ  right++๋ฅผ ํ•˜๋ฉด์„œ ์›์†Œ๋ฅผ ํ•˜๋‚˜์”ฉ ๋”ํ•ด์ค€๋‹ค.

2. ๋งŒ์•ฝ ๋ถ€๋ถ„ ํ•ฉ์ด ์ฃผ์–ด์ง„ s๋ณด๋‹ค ํฌ๊ฑฐ๋‚˜ ๊ฐ™์€ ๊ฒฝ์šฐ left์˜ ์›์†Œ๋ฅผ ๋ถ€๋ถ„ ํ•ฉ์—์„œ ๋นผ์ค€๋‹ค.

3. right == n ์ธ ๊ฒฝ์šฐ ๋ฐ˜๋ณต๋ฌธ์„ ์ข…๋ฃŒํ•œ๋‹ค.

4. n == 100000 ์ธ ๊ฒฝ์šฐ ๋ถ€๋ถ„ ํ•ฉ์„ ์ฐพ์ง€ ๋ชปํ–ˆ์œผ๋ฏ€๋กœ 0์„ ์ถœ๋ ฅํ•˜๊ณ  ๊ทธ๋ ‡์ง€ ์•Š์€ ๊ฒฝ์šฐ ์ตœ์†Œ ๊ธธ์ด๋ฅผ ์ถœ๋ ฅํ•œ๋‹ค.

 

์ค‘์š”ํ•œ ์ ์€ if๋ฌธ์˜ ์šฐ์„ ์ˆœ์œ„ ๋ผ๊ณ  ์ƒ๊ฐํ•œ๋‹ค. 4๋ฒˆ์˜ ๋„์ „ ๋์— ์„ฑ๊ณตํ–ˆ๋‹ค. ์ข€ ๋” ๋ถ„๋ฐœํ•ด์•ผ๊ฒ ๋‹ค.

ํ†ต๊ณผ

์ €์ž‘์žํ‘œ์‹œ ๋น„์˜๋ฆฌ ๋ณ€๊ฒฝ๊ธˆ์ง€ (์ƒˆ์ฐฝ์—ด๋ฆผ)

'โœ๏ธ ์ฝ”ํ…Œ ์ค€๋น„ > Two Pointer' ์นดํ…Œ๊ณ ๋ฆฌ์˜ ๋‹ค๋ฅธ ๊ธ€

[ํˆฌํฌ์ธํ„ฐ / Kotlin] BOJ 1644 - ์†Œ์ˆ˜์˜ ์—ฐ์†ํ•ฉ  (0) 2021.12.27
[ํˆฌํฌ์ธํ„ฐ / Kotlin] BOJ 2470 - ๋‘ ์šฉ์•ก  (0) 2021.12.25
[ํˆฌํฌ์ธํ„ฐ / Kotlin] BOJ 3273 - ๋‘ ์ˆ˜์˜ ํ•ฉ  (0) 2021.12.25
  1. ๋ฌธ์ œ
  2. ์ž…๋ ฅ
  3. ์ถœ๋ ฅ
  4. ํ•ด๊ฒฐ ๋ฐฉ๋ฒ•
  5. ํ†ต๊ณผ
'โœ๏ธ ์ฝ”ํ…Œ ์ค€๋น„/Two Pointer' ์นดํ…Œ๊ณ ๋ฆฌ์˜ ๋‹ค๋ฅธ ๊ธ€
  • [ํˆฌํฌ์ธํ„ฐ / Kotlin] BOJ 1644 - ์†Œ์ˆ˜์˜ ์—ฐ์†ํ•ฉ
  • [ํˆฌํฌ์ธํ„ฐ / Kotlin] BOJ 2470 - ๋‘ ์šฉ์•ก
  • [ํˆฌํฌ์ธํ„ฐ / Kotlin] BOJ 3273 - ๋‘ ์ˆ˜์˜ ํ•ฉ
kodo_o
kodo_o
iOS ๊ฟ€์žผ!
kodo_o
๐ŸŽ๐Ÿ
kodo_o
์ „์ฒด
์˜ค๋Š˜
์–ด์ œ
  • ๋ถ„๋ฅ˜ ์ „์ฒด๋ณด๊ธฐ (149)
    • ๐Ÿ”จ ํ”„๋กœ์ ํŠธ (0)
      • TP 1 (0)
      • WhiteHCCTV (0)
      • FootPrint (0)
    • ๐Ÿ’ป ๊ฐœ๋ฐœ (63)
      • iOS (30)
      • Android (6)
      • Kotlin (4)
      • Flutter (9)
      • Node.js (5)
      • Architecture (1)
      • ์˜ค๋Š˜์˜ ์‚ฝ์งˆ (7)
      • ์—๋Ÿฌ์™€์˜ ๋™์นจ (1)
    • โœ๏ธ ์•Œ๊ณ ๋ฆฌ์ฆ˜ (6)
      • Graph (6)
      • String (0)
      • Sort (0)
    • โœ๏ธ ์ฝ”ํ…Œ ์ค€๋น„ (44)
      • Math (1)
      • Implementation (3)
      • String (3)
      • Brute Force (5)
      • Back Tracking (7)
      • Greedy (0)
      • Dynamic Programming (13)
      • Binary Search (1)
      • DFS, BFS (5)
      • Shortest Path (2)
      • Two Pointer (4)
      • MST (0)
    • ๐Ÿ“š CS (6)
      • Operating System (6)
    • โ›น๏ธ ๋ผ์ดํ”„ (30)
      • 2020 ๊ฒจ์šธ๋ฐฉํ•™ ๋ชจ๊ฐ์ฝ”(๊ฐœ์ธ) (12)
      • 2021 ์—ฌ๋ฆ„๋ฐฉํ•™ ๋ชจ๊ฐ์ฝ”(๊ฐœ์ธ) (6)
      • ์ฝ”๋”ฉ ํ…Œ์ŠคํŠธ (1)
      • ํšŒ๊ณ  (10)

๋ธ”๋กœ๊ทธ ๋ฉ”๋‰ด

  • ํ™ˆ
  • ๊นƒํ—ˆ๋ธŒ

์ธ๊ธฐ ๊ธ€

์ตœ๊ทผ ๊ธ€

์ตœ๊ทผ ๋Œ“๊ธ€

hELLO ยท Designed By ์ •์ƒ์šฐ.
kodo_o
[ํˆฌํฌ์ธํ„ฐ / Kotlin] BOJ 1806 - ๋ถ€๋ถ„ ํ•ฉ
์ƒ๋‹จ์œผ๋กœ

ํ‹ฐ์Šคํ† ๋ฆฌํˆด๋ฐ”

๋‹จ์ถ•ํ‚ค

๋‚ด ๋ธ”๋กœ๊ทธ

๋‚ด ๋ธ”๋กœ๊ทธ - ๊ด€๋ฆฌ์ž ํ™ˆ ์ „ํ™˜
Q
Q
์ƒˆ ๊ธ€ ์“ฐ๊ธฐ
W
W

๋ธ”๋กœ๊ทธ ๊ฒŒ์‹œ๊ธ€

๊ธ€ ์ˆ˜์ • (๊ถŒํ•œ ์žˆ๋Š” ๊ฒฝ์šฐ)
E
E
๋Œ“๊ธ€ ์˜์—ญ์œผ๋กœ ์ด๋™
C
C

๋ชจ๋“  ์˜์—ญ

์ด ํŽ˜์ด์ง€์˜ URL ๋ณต์‚ฌ
S
S
๋งจ ์œ„๋กœ ์ด๋™
T
T
ํ‹ฐ์Šคํ† ๋ฆฌ ํ™ˆ ์ด๋™
H
H
๋‹จ์ถ•ํ‚ค ์•ˆ๋‚ด
Shift + /
โ‡ง + /

* ๋‹จ์ถ•ํ‚ค๋Š” ํ•œ๊ธ€/์˜๋ฌธ ๋Œ€์†Œ๋ฌธ์ž๋กœ ์ด์šฉ ๊ฐ€๋Šฅํ•˜๋ฉฐ, ํ‹ฐ์Šคํ† ๋ฆฌ ๊ธฐ๋ณธ ๋„๋ฉ”์ธ์—์„œ๋งŒ ๋™์ž‘ํ•ฉ๋‹ˆ๋‹ค.