๐Ÿ’ฌ ๋ฌธ์ž์—ด ์••์ถ•

ํ”„๋กœ๊ทธ๋ž˜๋จธ์Šค Level2

[Class2] ๋ฌธ์ž์—ด ์••์ถ•

๋ฌธ์ œ ์„ค๋ช…


๋ฐ์ดํ„ฐ ์ฒ˜๋ฆฌ ์ „๋ฌธ๊ฐ€๊ฐ€ ๋˜๊ณ  ์‹ถ์€ โ€œ์–ดํ”ผ์น˜โ€๋Š” ๋ฌธ์ž์—ด์„ ์••์ถ•ํ•˜๋Š” ๋ฐฉ๋ฒ•์— ๋Œ€ํ•ด ๊ณต๋ถ€๋ฅผ ํ•˜๊ณ  ์žˆ์Šต๋‹ˆ๋‹ค. ์ตœ๊ทผ์— ๋Œ€๋Ÿ‰์˜ ๋ฐ์ดํ„ฐ ์ฒ˜๋ฆฌ๋ฅผ ์œ„ํ•œ ๊ฐ„๋‹จํ•œ ๋น„์†์‹ค ์••์ถ• ๋ฐฉ๋ฒ•์— ๋Œ€ํ•ด ๊ณต๋ถ€๋ฅผ ํ•˜๊ณ  ์žˆ๋Š”๋ฐ, ๋ฌธ์ž์—ด์—์„œ ๊ฐ™์€ ๊ฐ’์ด ์—ฐ์†ํ•ด์„œ ๋‚˜ํƒ€๋‚˜๋Š” ๊ฒƒ์„ ๊ทธ ๋ฌธ์ž์˜ ๊ฐœ์ˆ˜์™€ ๋ฐ˜๋ณต๋˜๋Š” ๊ฐ’์œผ๋กœ ํ‘œํ˜„ํ•˜์—ฌ ๋” ์งง์€ ๋ฌธ์ž์—ด๋กœ ์ค„์—ฌ์„œ ํ‘œํ˜„ํ•˜๋Š” ์•Œ๊ณ ๋ฆฌ์ฆ˜์„ ๊ณต๋ถ€ํ•˜๊ณ  ์žˆ์Šต๋‹ˆ๋‹ค. ๊ฐ„๋‹จํ•œ ์˜ˆ๋กœ โ€œaabbacccโ€์˜ ๊ฒฝ์šฐ โ€œ2a2ba3cโ€(๋ฌธ์ž๊ฐ€ ๋ฐ˜๋ณต๋˜์ง€ ์•Š์•„ ํ•œ๋ฒˆ๋งŒ ๋‚˜ํƒ€๋‚œ ๊ฒฝ์šฐ 1์€ ์ƒ๋žตํ•จ)์™€ ๊ฐ™์ด ํ‘œํ˜„ํ•  ์ˆ˜ ์žˆ๋Š”๋ฐ, ์ด๋Ÿฌํ•œ ๋ฐฉ์‹์€ ๋ฐ˜๋ณต๋˜๋Š” ๋ฌธ์ž๊ฐ€ ์ ์€ ๊ฒฝ์šฐ ์••์ถ•๋ฅ ์ด ๋‚ฎ๋‹ค๋Š” ๋‹จ์ ์ด ์žˆ์Šต๋‹ˆ๋‹ค. ์˜ˆ๋ฅผ ๋“ค๋ฉด, โ€œabcabcdedeโ€์™€ ๊ฐ™์€ ๋ฌธ์ž์—ด์€ ์ „ํ˜€ ์••์ถ•๋˜์ง€ ์•Š์Šต๋‹ˆ๋‹ค. โ€œ์–ดํ”ผ์น˜โ€๋Š” ์ด๋Ÿฌํ•œ ๋‹จ์ ์„ ํ•ด๊ฒฐํ•˜๊ธฐ ์œ„ํ•ด ๋ฌธ์ž์—ด์„ 1๊ฐœ ์ด์ƒ์˜ ๋‹จ์œ„๋กœ ์ž˜๋ผ์„œ ์••์ถ•ํ•˜์—ฌ ๋” ์งง์€ ๋ฌธ์ž์—ด๋กœ ํ‘œํ˜„ํ•  ์ˆ˜ ์žˆ๋Š”์ง€ ๋ฐฉ๋ฒ•์„ ์ฐพ์•„๋ณด๋ ค๊ณ  ํ•ฉ๋‹ˆ๋‹ค.

์˜ˆ๋ฅผ ๋“ค์–ด, โ€œababcdcdababcdcdโ€์˜ ๊ฒฝ์šฐ ๋ฌธ์ž๋ฅผ 1๊ฐœ ๋‹จ์œ„๋กœ ์ž๋ฅด๋ฉด ์ „ํ˜€ ์••์ถ•๋˜์ง€ ์•Š์ง€๋งŒ, 2๊ฐœ ๋‹จ์œ„๋กœ ์ž˜๋ผ์„œ ์••์ถ•ํ•œ๋‹ค๋ฉด โ€œ2ab2cd2ab2cdโ€๋กœ ํ‘œํ˜„ํ•  ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค. ๋‹ค๋ฅธ ๋ฐฉ๋ฒ•์œผ๋กœ 8๊ฐœ ๋‹จ์œ„๋กœ ์ž˜๋ผ์„œ ์••์ถ•ํ•œ๋‹ค๋ฉด โ€œ2ababcdcdโ€๋กœ ํ‘œํ˜„ํ•  ์ˆ˜ ์žˆ์œผ๋ฉฐ, ์ด๋•Œ๊ฐ€ ๊ฐ€์žฅ ์งง๊ฒŒ ์••์ถ•ํ•˜์—ฌ ํ‘œํ˜„ํ•  ์ˆ˜ ์žˆ๋Š” ๋ฐฉ๋ฒ•์ž…๋‹ˆ๋‹ค.

๋‹ค๋ฅธ ์˜ˆ๋กœ, โ€œabcabcdedeโ€์™€ ๊ฐ™์€ ๊ฒฝ์šฐ, ๋ฌธ์ž๋ฅผ 2๊ฐœ ๋‹จ์œ„๋กœ ์ž˜๋ผ์„œ ์••์ถ•ํ•˜๋ฉด โ€œabcabc2deโ€๊ฐ€ ๋˜์ง€๋งŒ, 3๊ฐœ ๋‹จ์œ„๋กœ ์ž๋ฅธ๋‹ค๋ฉด โ€œ2abcdedeโ€๊ฐ€ ๋˜์–ด 3๊ฐœ ๋‹จ์œ„๊ฐ€ ๊ฐ€์žฅ ์งง์€ ์••์ถ• ๋ฐฉ๋ฒ•์ด ๋ฉ๋‹ˆ๋‹ค. ์ด๋•Œ 3๊ฐœ ๋‹จ์œ„๋กœ ์ž๋ฅด๊ณ  ๋งˆ์ง€๋ง‰์— ๋‚จ๋Š” ๋ฌธ์ž์—ด์€ ๊ทธ๋Œ€๋กœ ๋ถ™์—ฌ์ฃผ๋ฉด ๋ฉ๋‹ˆ๋‹ค.

์••์ถ•ํ•  ๋ฌธ์ž์—ด s๊ฐ€ ๋งค๊ฐœ๋ณ€์ˆ˜๋กœ ์ฃผ์–ด์งˆ ๋•Œ, ์œ„์— ์„ค๋ช…ํ•œ ๋ฐฉ๋ฒ•์œผ๋กœ 1๊ฐœ ์ด์ƒ ๋‹จ์œ„๋กœ ๋ฌธ์ž์—ด์„ ์ž˜๋ผ ์••์ถ•ํ•˜์—ฌ ํ‘œํ˜„ํ•œ ๋ฌธ์ž์—ด ์ค‘ ๊ฐ€์žฅ ์งง์€ ๊ฒƒ์˜ ๊ธธ์ด๋ฅผ return ํ•˜๋„๋ก solution ํ•จ์ˆ˜๋ฅผ ์™„์„ฑํ•ด์ฃผ์„ธ์š”.

์ œํ•œ์‚ฌํ•ญ


  • s์˜ ๊ธธ์ด๋Š” 1 ์ด์ƒ 1,000 ์ดํ•˜์ž…๋‹ˆ๋‹ค.
  • s๋Š” ์•ŒํŒŒ๋ฒณ ์†Œ๋ฌธ์ž๋กœ๋งŒ ์ด๋ฃจ์–ด์ ธ ์žˆ์Šต๋‹ˆ๋‹ค.

์ž…์ถœ๋ ฅ ์˜ˆ


|s|result| |โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€“|โ€”โ€”| |โ€aabbacccโ€|7| |โ€ababcdcdababcdcdโ€|9| |โ€abcabcdedeโ€|8| |โ€abcabcabcabcdedededededeโ€|14| |โ€xababcdcdababcdcdโ€|17|

์ž…์ถœ๋ ฅ ์˜ˆ์— ๋Œ€ํ•œ ์„ค๋ช…

์ž…์ถœ๋ ฅ ์˜ˆ #1

๋ฌธ์ž์—ด์„ 1๊ฐœ ๋‹จ์œ„๋กœ ์ž˜๋ผ ์••์ถ•ํ–ˆ์„ ๋•Œ ๊ฐ€์žฅ ์งง์Šต๋‹ˆ๋‹ค.

์ž…์ถœ๋ ฅ ์˜ˆ #2

๋ฌธ์ž์—ด์„ 8๊ฐœ ๋‹จ์œ„๋กœ ์ž˜๋ผ ์••์ถ•ํ–ˆ์„ ๋•Œ ๊ฐ€์žฅ ์งง์Šต๋‹ˆ๋‹ค.

์ž…์ถœ๋ ฅ ์˜ˆ #3

๋ฌธ์ž์—ด์„ 3๊ฐœ ๋‹จ์œ„๋กœ ์ž˜๋ผ ์••์ถ•ํ–ˆ์„ ๋•Œ ๊ฐ€์žฅ ์งง์Šต๋‹ˆ๋‹ค.

์ž…์ถœ๋ ฅ ์˜ˆ #4

๋ฌธ์ž์—ด์„ 2๊ฐœ ๋‹จ์œ„๋กœ ์ž๋ฅด๋ฉด "abcabcabcabc6de" ๊ฐ€ ๋ฉ๋‹ˆ๋‹ค.
๋ฌธ์ž์—ด์„ 3๊ฐœ ๋‹จ์œ„๋กœ ์ž๋ฅด๋ฉด "4abcdededededede" ๊ฐ€ ๋ฉ๋‹ˆ๋‹ค.
๋ฌธ์ž์—ด์„ 4๊ฐœ ๋‹จ์œ„๋กœ ์ž๋ฅด๋ฉด "abcabcabcabc3dede" ๊ฐ€ ๋ฉ๋‹ˆ๋‹ค.
๋ฌธ์ž์—ด์„ 6๊ฐœ ๋‹จ์œ„๋กœ ์ž๋ฅผ ๊ฒฝ์šฐ "2abcabc2dedede"๊ฐ€ ๋˜๋ฉฐ, ์ด๋•Œ์˜ ๊ธธ์ด๊ฐ€ 14๋กœ ๊ฐ€์žฅ ์งง์Šต๋‹ˆ๋‹ค.

์ž…์ถœ๋ ฅ ์˜ˆ #5

๋ฌธ์ž์—ด์€ ์ œ์ผ ์•ž๋ถ€ํ„ฐ ์ •ํ•ด์ง„ ๊ธธ์ด๋งŒํผ ์ž˜๋ผ์•ผ ํ•ฉ๋‹ˆ๋‹ค.
๋”ฐ๋ผ์„œ ์ฃผ์–ด์ง„ ๋ฌธ์ž์—ด์„ x / ababcdcd / ababcdcd ๋กœ ์ž๋ฅด๋Š” ๊ฒƒ์€ ๋ถˆ๊ฐ€๋Šฅ ํ•ฉ๋‹ˆ๋‹ค.
์ด ๊ฒฝ์šฐ ์–ด๋–ป๊ฒŒ ๋ฌธ์ž์—ด์„ ์ž˜๋ผ๋„ ์••์ถ•๋˜์ง€ ์•Š์œผ๋ฏ€๋กœ ๊ฐ€์žฅ ์งง์€ ๊ธธ์ด๋Š” 17์ด ๋ฉ๋‹ˆ๋‹ค.

# ๐Ÿ“– ๊ฐ€์ ธ๋‹ค ์“ฐ๊ธฐ

์ฒ˜์Œ์—๋Š” ์Šคํƒ์„ ๋– ์˜ฌ๋ ธ๋‹ค. ์™œ๋ƒํ•˜๋ฉด ๋ฌธ์ž์—ด์—์„œ ํŠน์ • ๋ฌธ์ž์—ด์„ ๊ฒ€์ƒ‰ํ•˜๋Š” ๋ฌธ์ œ์ด๊ธฐ ๋•Œ๋ฌธ์ด๋‹ค. 

๊ทธ๋Ÿฌ๋‚˜ ์‹œ๊ฐ„๋ณต์žก๋„๋ฅผ ๊ตฌํ•ด๋ณด๊ณ  ๋ธŒ๋ฃจํŠธ ํฌ์Šค๋กœ ํ’€์–ด์•ผ๊ฒ ๋‹ค๊ณ  ์ƒ๊ฐํ–ˆ๋‹ค. 

+ ์ž…๋ ฅ ๋ฐ์ดํ„ฐ ๊ฐœ์ˆ˜: 1000 ๐Ÿ‘‰๐Ÿป O(N^2*logN)๊นŒ์ง€ ๊ฐ€๋Šฅ
+ ๋ธŒ๋ฃจํŠธ ํฌ์Šค๋กœ ์˜ˆ์ƒ๋˜๋Š” ์‹œ๊ฐ„ ๋ณต์žก๋„ ๐Ÿ‘‰๐Ÿป O(N^2)

# ๐Ÿ“ ๊ณผ์ • ์„ค๊ณ„/๊ด€๋ฆฌ

![แ„‹แ…งแ†ซแ„‰แ…ณแ†ธแ„Œแ…กแ†ผ-63](https://user-images.githubusercontent.com/88064555/181485252-1849708b-fcbe-4cd6-86f2-df371ecad727.jpg)


์ž…๋ ฅ: aabbaccc๊ฐ€ ๋“ค์–ด์™”์„ ๋•Œ๋ฅผ ์˜ˆ์‹œ๋กœ ์ง„ํ–‰ํ•ด๋ณด๊ฒ ๋‹ค.

๋จผ์ € 1๋ถ€ํ„ฐ ์ ˆ๋ฐ˜๊นŒ์ง€ ๋ฌธ์ž์—ด์„ ๋‚˜๋ˆ„๋Š” ๋ชจ๋“  ๊ฒฝ์šฐ๋ฅผ ๊ตฌํ•œ๋‹ค. ์ด ๋•Œ, ์ ˆ๋ฐ˜๊นŒ์ง€ ํƒ์ƒ‰ํ•˜๋Š” ์ด์œ ๋Š” ์–ด์ฐจํ”ผ ์ ˆ๋ฐ˜์„ ๋„˜์–ด๊ฐ€๋Š” ์ˆœ๊ฐ„ ๋ฌธ์ž์—ด ์••์ถ•์ด ๋˜์ง€ ์•Š๊ธฐ ๋•Œ๋ฌธ์ด๋‹ค.

(๊ทธ๋Ÿฐ๋ฐ ์ตœ์ข…์ ์ธ ์ฝ”๋“œ๋Š” ๋ถˆํ•„์š”ํ•˜๋”๋ผ๋„ 1๋ถ€ํ„ฐ ์ „์ฒด๋ฅผ ๋‚˜๋ˆ„์–ด ํ’€์—ˆ๋‹ค. ๊ทธ ์ด์œ ๋Š” ๋ฌธ์ž์—ด ๊ธธ์ด๊ฐ€ 1์ผ๋•Œ๋Š” ์ ˆ๋ฐ˜์œผ๋กœ ์ชผ๊ฐœ์ง€์ง€ ์•Š๊ธฐ ๋•Œ๋ฌธ์— ์—๋Ÿฌ๊ฐ€ ๋ฐœ์ƒํ•œ๋‹ค.)

๊ทธ๋ ‡๊ฒŒ ํ•˜์—ฌ ๊ฐ๊ฐ์˜ ์••์ถ•๋œ ๋ฌธ์ž์—ด ๊ธธ์ด๋ฅผ ๋น„๊ตํ•˜์—ฌ ์ตœ์†Œ๊ฐ’์„ ๋ฐ˜ํ™˜ํ•ด์ฃผ๋ฉด ์ •๋‹ต์ด๋‹ค.


![แ„‹แ…งแ†ซแ„‰แ…ณแ†ธแ„Œแ…กแ†ผ-64](https://user-images.githubusercontent.com/88064555/181485322-650d8dfd-34c9-4417-a68c-71ee0562023a.jpg)

![แ„‹แ…งแ†ซแ„‰แ…ณแ†ธแ„Œแ…กแ†ผ-65](https://user-images.githubusercontent.com/88064555/181485372-19362a11-703d-498d-940d-781786b7da2a.jpg)


์ด์ œ๋ถ€ํ„ฐ๋Š” ๋‚˜๋ˆ„์–ด์ง„ ๊ฐ ๋ฌธ์ž์—ด์— ๋Œ€ํ•˜์—ฌ ์–ด๋–ป๊ฒŒ ์••์ถ•์ด ์ง„ํ–‰๋˜๋Š”์ง€๋ฅผ ์„ค๋ช…ํ•ด๋ณด๋„๋ก ํ•˜๊ฒ ๋‹ค.

๊ฐ€์žฅ ์ฒซ ๋ฒˆ์งธ ์ธ๋ฑ์Šค๋ถ€ํ„ฐ ์‹œ์ž‘ํ•˜์—ฌ ๋‹ค์Œ ์ธ๋ฑ์Šค๋ฅผ ๋น„๊ตํ•ด๋ณด์•„ ๊ฐ™์€ ๊ฐ’์ด ๋‚˜์˜ค๋ฉด count๋ฅผ ์ฆ๊ฐ€์‹œํ‚ค๋ฉฐ ๊ณ„์† ํƒ์ƒ‰ํ•œ๋‹ค.

๋งŒ์•ฝ count๊ฐ€ 1์ด๋ผ๋ฉด ๊ทธ๋Œ€๋กœ ์••์ถ• ๋ฌธ์ž์—ด์— ๋ถ™์—ฌ์ฃผ๊ณ  2 ์ด์ƒ์ด๋ผ๋ฉด count์™€ ํ•จ๊ป˜ ๊ฐ™์ด ๋ถ™์—ฌ์ค€๋‹ค.

๊ทธ๋ ‡๊ฒŒ ๋ฌธ์ž์—ด ๋๊นŒ์ง€ ํƒ์ƒ‰์„ ๋งˆ์น˜๋ฉด ์ตœ์ข…์ ์ธ ์••์ถ• ๋ฌธ์ž์—ด์ด ์ƒ์„ฑ๋˜๊ณ  ์ด๋ฅผ ์ •๋‹ต ํ›„๋ณด๊ตฐ ๋ฆฌ์ŠคํŠธ์— ๋„ฃ์–ด์ค€๋‹ค.

๋งˆ์ง€๋ง‰์— ์ •๋‹ต ํ›„๋ณด๊ตฐ ๋ฆฌ์ŠคํŠธ์—์„œ ์ตœ์†Œ๊ฐ’์„ ์„ ํƒํ•ด์ฃผ๋ฉด ๊ทธ๊ฒƒ์ด ๊ณง ์ •๋‹ต !!!

# ๐Ÿ‘จ๐Ÿปโ€๐Ÿ’ป CODE

```python
def solution(s):
    candidates = []

    # ๋ฌธ์ž์—ด ๋ถ„๋ฆฌ
    for a in range(1,len(s)+1):
        i=0
        arr = []
        while i+a<len(s):
            arr.append(s[i:i+a])
            i += a
        arr.append(s[i:])

        answer = ""
        i=0
        while 0<=i<len(arr):
            count = 1
            if i != len(arr)-1:
                while arr[i] == arr[i+1]:
                    count += 1
                    i += 1

                    if i == len(arr)-1:
                        break
            
            if count == 1:
                answer += arr[i]
            else:
                answer += str(count) + arr[i]
            
            i += 1

        candidates.append(len(answer))

    return min(candidates)

ยฉ 2022. All rights reserved.

Powered by Hydejack v9.1.6