deo2kim
๋งž์™œํ‹€
deo2kim
์ „์ฒด ๋ฐฉ๋ฌธ์ž
์˜ค๋Š˜
์–ด์ œ
  • ๋ถ„๋ฅ˜ ์ „์ฒด๋ณด๊ธฐ
    • CS
      • Algorithm
      • Data Structure
      • Network
      • DB
      • OS
    • Algorithm Problem
      • Python
      • JavaScript
    • Programming language
      • Python
      • JavaScript
    • Tool
      • Jquery
      • React
    • ๊ฐœ๋ฐœ
    • Infra

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

  • ํ™ˆ
  • ํƒœ๊ทธ
  • ๋ฐฉ๋ช…๋ก

๊ณต์ง€์‚ฌํ•ญ

์ธ๊ธฐ ๊ธ€

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

์ตœ๊ทผ ๊ธ€

ํ‹ฐ์Šคํ† ๋ฆฌ

๋ฐ˜์‘ํ˜•
hELLO ยท Designed By ์ •์ƒ์šฐ.
deo2kim

๋งž์™œํ‹€

[python] ํ”„๋กœ๊ทธ๋ž˜๋จธ์Šค - ๋ฌธ์ž์—ด ์••์ถ•(2020 KAKAO BLIND RECRUITMENT)
Algorithm Problem/Python

[python] ํ”„๋กœ๊ทธ๋ž˜๋จธ์Šค - ๋ฌธ์ž์—ด ์••์ถ•(2020 KAKAO BLIND RECRUITMENT)

2020. 8. 21. 07:58
๋ฐ˜์‘ํ˜•

๐Ÿค”๋ฌธ์ œ ํ•ด๊ฒฐ

1. Lv2

2. ๋ฆฌ์ŠคํŠธ๋ฅผ ๋งŒ๋“ค์–ด ๋ฌธ์ž์—ด์„ 1๊ฐœ, 2๊ฐœ, ... , n/2๊ฐœ ๊นŒ์ง€ ์ชผ๊ฐฐ๋‹ค.

๋ฌธ์ž์—ด์ด abcabcabcabcdededededede ๋ผ๋ฉด

[['a', 'b', 'c', 'a', 'b', 'c', 'a', 'b', 'c', 'a', 'b', 'c', 'd', 'e', 'd', 'e', 'd', 'e', 'd', 'e', 'd', 'e', 'd', 'e', ''], ['ab', 'ca', 'bc', 'ab', 'ca', 'bc', 'de', 'de', 'de', 'de', 'de', 'de', ''], ['abc', 'abc', 'abc', 'abc', 'ded', 'ede', 'ded', 'ede', ''], ['abca', 'bcab', 'cabc', 'dede', 'dede', 'dede', ''], ['abcab', 'cabca', 'bcded', 'edede', 'dede', ''], ['abcabc', 'abcabc', 'dedede', 'dedede', ''], ['abcabca', 'bcabcde', 'dededed', 'ede', ''], ['abcabcab', 'cabcdede', 'dededede', ''], ['abcabcabc', 'abcdedede', 'dedede', ''], ['abcabcabca', 'bcdededede', 'dede', ''], ['abcabcabcab', 'cdedededede', 'de', ''], ['abcabcabcabc', 'dededededede', '']]

๊ฐ’์ด ์ด๋ ‡๊ฒŒ ๋“ค์–ด๊ฐˆ ๊ฒƒ์ด๋‹ค.

3. ๋ฆฌ์ŠคํŠธ์—์„œ ํ•œ์ค„์”ฉ ๊บผ๋‚ด์„œ ๊ฐ ์›์†Œ์˜ ์•ž๋’ค๋ฅผ ๋น„๊ตํ•ด์ค€๋‹ค.

4. ์•ž๋’ค๊ฐ€ ๊ฐ™์œผ๋ฉด ์นด์šดํŠธ๋ฅผ ์˜ฌ๋ ค์ฃผ๊ณ  ๋‹ฌ๋ผ์ง€๋ฉด ์นด์šดํŠธํ•œ ์ˆซ์ž์™€ ๋ฌธ์ž๋ฅผ ์ €์žฅํ•œ๋‹ค

 ex) 'a','a','b' ์ด๋ฉด 'a' == 'a' ์ด๋ฏ€๋กœ ์นด์šดํŠธ 2, ๊ทธ ๋‹ค์Œ 'b'๊ฐ€ ๋‚˜์™€์„œ ๋‹ฌ๋ผ์ง€๋ฏ€๋กœ '2a'๋ฅผ ์ €์žฅํ•œ๋‹ค.

5. ๊ธธ์ด๊ฐ€ ์ตœ์†Œ์ธ ๊ฒฝ์šฐ๋ฅผ ์ฐพ์•„์„œ ์ถœ๋ ฅํ•œ๋‹ค.

 

๐Ÿ’จ 

 

๐Ÿ’ป์†Œ์Šค ์ฝ”๋“œ

def solution(s):
    if len(s) == 1:
        return 1
    result = []
    for i in range(1, (len(s) // 2) + 1):
        tmp = []
        for j in range(0, len(s), i):
            tmp.append(s[j:j + i])
        tmp.append('')
        result.append(tmp)

    # print(result)
    minNum = 1001
    for i in result:
        cnt = 1
        answer = ''
        for j in range(len(i)-1):
            if i[j] == i[j+1]:

                cnt += 1
            else:
                if cnt == 1:
                    answer += i[j]
                else:
                    answer += str(cnt) + i[j]
                cnt = 1
            if len(answer) > minNum:
                break
        if len(answer) < minNum:
            minNum = len(answer)

    return minNum

 

๐Ÿ“•๋ฌธ์ œ ํ™•์ธ

์ถœ์ฒ˜: ํ”„๋กœ๊ทธ๋ž˜๋จธ์Šค

๋งํฌ: https://programmers.co.kr/learn/courses/30/lessons/60057

 

์ฝ”๋”ฉํ…Œ์ŠคํŠธ ์—ฐ์Šต - ๋ฌธ์ž์—ด ์••์ถ•

๋ฐ์ดํ„ฐ ์ฒ˜๋ฆฌ ์ „๋ฌธ๊ฐ€๊ฐ€ ๋˜๊ณ  ์‹ถ์€ ์–ดํ”ผ์น˜๋Š” ๋ฌธ์ž์—ด์„ ์••์ถ•ํ•˜๋Š” ๋ฐฉ๋ฒ•์— ๋Œ€ํ•ด ๊ณต๋ถ€๋ฅผ ํ•˜๊ณ  ์žˆ์Šต๋‹ˆ๋‹ค. ์ตœ๊ทผ์— ๋Œ€๋Ÿ‰์˜ ๋ฐ์ดํ„ฐ ์ฒ˜๋ฆฌ๋ฅผ ์œ„ํ•œ ๊ฐ„๋‹จํ•œ ๋น„์†์‹ค ์••์ถ• ๋ฐฉ๋ฒ•์— ๋Œ€ํ•ด ๊ณต๋ถ€๋ฅผ ํ•˜๊ณ  ์žˆ๋Š”๋ฐ, ๋ฌธ์ž

programmers.co.kr

๋ฌธ์ œ ์„ค๋ช…

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

์ž…์ถœ๋ ฅ ์˜ˆ

sresult

"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์ด ๋ฉ๋‹ˆ๋‹ค.

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

'Algorithm Problem > Python' ์นดํ…Œ๊ณ ๋ฆฌ์˜ ๋‹ค๋ฅธ ๊ธ€

[html] ๊ณต๋ฐฑ ๋ฌธ์ž, ๋„์–ด์“ฐ๊ธฐ  (2) 2020.08.22
[python] ํ”„๋กœ๊ทธ๋ž˜๋จธ์Šค - ๊ธฐ๋‘ฅ๊ณผ ๋ณด ์„ค์น˜(2020 KAKAO BLIND RECRUITMENT)  (1) 2020.08.22
[python] SWEA - 1389. ์ผ€๋นˆ ๋ฒ ์ด์ปจ์˜ 6๋‹จ๊ณ„ ๋ฒ•์น™  (0) 2020.08.20
[python] ๋ฐฑ์ค€ - 1074. Z  (0) 2020.08.19
[python] ๋ฐฑ์ค€ - 11048. ์ด๋™ํ•˜๊ธฐ  (0) 2020.08.18
    'Algorithm Problem/Python' ์นดํ…Œ๊ณ ๋ฆฌ์˜ ๋‹ค๋ฅธ ๊ธ€
    • [html] ๊ณต๋ฐฑ ๋ฌธ์ž, ๋„์–ด์“ฐ๊ธฐ
    • [python] ํ”„๋กœ๊ทธ๋ž˜๋จธ์Šค - ๊ธฐ๋‘ฅ๊ณผ ๋ณด ์„ค์น˜(2020 KAKAO BLIND RECRUITMENT)
    • [python] SWEA - 1389. ์ผ€๋นˆ ๋ฒ ์ด์ปจ์˜ 6๋‹จ๊ณ„ ๋ฒ•์น™
    • [python] ๋ฐฑ์ค€ - 1074. Z
    deo2kim
    deo2kim
    ์ฝ”๋”ฉ ๊ธฐ๋กํ•˜๊ธฐ

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