๋ณธ๋ฌธ ๋ฐ”๋กœ๊ฐ€๊ธฐ
Coding Test/Algorithms

[ํ”„๋กœ๊ทธ๋ž˜๋จธ์Šค] [3์ฐจ] ์••์ถ•/Python - Lv.2

by The Future Engineer, Lucy 2024. 10. 24.
728x90
๋ฐ˜์‘ํ˜•

โ“๋ฌธ์ œ

 

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

SW๊ฐœ๋ฐœ์ž๋ฅผ ์œ„ํ•œ ํ‰๊ฐ€, ๊ต์œก, ์ฑ„์šฉ๊นŒ์ง€ Total Solution์„ ์ œ๊ณตํ•˜๋Š” ๊ฐœ๋ฐœ์ž ์„ฑ์žฅ์„ ์œ„ํ•œ ๋ฒ ์ด์Šค์บ ํ”„

programmers.co.kr

์„ฑ๋Šฅ์š”์•ฝ

์ฝ”๋“œ1 โžก๏ธ ๋ฉ”๋ชจ๋ฆฌ: 10 MB, ์‹œ๊ฐ„: 0.58 ms
์ฝ”๋“œ2 โžก๏ธ ๋ฉ”๋ชจ๋ฆฌ: 10.2 MB, ์‹œ๊ฐ„: 0.62 ms

๋ฌธ์ œ ์„ค๋ช…

๊ธธ์ด๊ฐ€ 1์ธ ๋ชจ๋“  ๋‹จ์–ด๋ฅผ ํฌํ•จํ•˜๋„๋ก ์‚ฌ์ „์„ ์ดˆ๊ธฐํ™”ํ•œ๋‹ค.
์‚ฌ์ „์—์„œ ํ˜„์žฌ ์ž…๋ ฅ๊ณผ ์ผ์น˜ํ•˜๋Š” ๊ฐ€์žฅ ๊ธด ๋ฌธ์ž์—ด w๋ฅผ ์ฐพ๋Š”๋‹ค.
w์— ํ•ด๋‹นํ•˜๋Š” ์‚ฌ์ „์˜ ์ƒ‰์ธ ๋ฒˆํ˜ธ๋ฅผ ์ถœ๋ ฅํ•˜๊ณ , ์ž…๋ ฅ์—์„œ w๋ฅผ ์ œ๊ฑฐํ•œ๋‹ค.
์ž…๋ ฅ์—์„œ ์ฒ˜๋ฆฌ๋˜์ง€ ์•Š์€ ๋‹ค์Œ ๊ธ€์ž๊ฐ€ ๋‚จ์•„์žˆ๋‹ค๋ฉด(c), w+c์— ํ•ด๋‹นํ•˜๋Š” ๋‹จ์–ด๋ฅผ ์‚ฌ์ „์— ๋“ฑ๋กํ•œ๋‹ค.


์••์ถ• ์•Œ๊ณ ๋ฆฌ์ฆ˜์ด ์˜๋ฌธ ๋Œ€๋ฌธ์ž๋งŒ ์ฒ˜๋ฆฌํ•œ๋‹ค๊ณ  ํ•  ๋•Œ, ์‚ฌ์ „์€ ๋‹ค์Œ๊ณผ ๊ฐ™์ด ์ดˆ๊ธฐํ™”๋œ๋‹ค.

์ƒ‰์ธ๋ฒˆํ˜ธ 1 2 3 ... 24 25 26
๋‹จ์–ด A B C ... X Y Z

 

์˜ˆ๋ฅผ ๋“ค์–ด ์ž…๋ ฅ์œผ๋กœ KAKAO๊ฐ€ ๋“ค์–ด์˜จ๋‹ค๊ณ  ํ•˜์ž.

ํ˜„์žฌ ์‚ฌ์ „์—๋Š” KAKAO์˜ ์ฒซ ๊ธ€์ž K๋Š” ๋“ฑ๋ก๋˜์–ด ์žˆ์œผ๋‚˜, ๋‘ ๋ฒˆ์งธ ๊ธ€์ž๊นŒ์ง€์ธ KA๋Š” ์—†์œผ๋ฏ€๋กœ, ์ฒซ ๊ธ€์ž K์— ํ•ด๋‹นํ•˜๋Š” ์ƒ‰์ธ ๋ฒˆํ˜ธ 11์„ ์ถœ๋ ฅํ•˜๊ณ , ๋‹ค์Œ ๊ธ€์ž์ธ A๋ฅผ ํฌํ•จํ•œ KA๋ฅผ ์‚ฌ์ „์— 27 ๋ฒˆ์งธ๋กœ ๋“ฑ๋กํ•œ๋‹ค.
๋‘ ๋ฒˆ์งธ ๊ธ€์ž A๋Š” ์‚ฌ์ „์— ์žˆ์œผ๋‚˜, ์„ธ ๋ฒˆ์งธ ๊ธ€์ž๊นŒ์ง€์ธ AK๋Š” ์‚ฌ์ „์— ์—†์œผ๋ฏ€๋กœ, A์˜ ์ƒ‰์ธ ๋ฒˆํ˜ธ 1์„ ์ถœ๋ ฅํ•˜๊ณ , AK๋ฅผ ์‚ฌ์ „์— 28 ๋ฒˆ์งธ๋กœ ๋“ฑ๋กํ•œ๋‹ค.
์„ธ ๋ฒˆ์งธ ๊ธ€์ž์—์„œ ์‹œ์ž‘ํ•˜๋Š” KA๊ฐ€ ์‚ฌ์ „์— ์žˆ์œผ๋ฏ€๋กœ, KA์— ํ•ด๋‹นํ•˜๋Š” ์ƒ‰์ธ ๋ฒˆํ˜ธ 27์„ ์ถœ๋ ฅํ•˜๊ณ , ๋‹ค์Œ ๊ธ€์ž O๋ฅผ ํฌํ•จํ•œ KAO๋ฅผ 29 ๋ฒˆ์งธ๋กœ ๋“ฑ๋กํ•œ๋‹ค.
๋งˆ์ง€๋ง‰์œผ๋กœ ์ฒ˜๋ฆฌ๋˜์ง€ ์•Š์€ ๊ธ€์ž O์— ํ•ด๋‹นํ•˜๋Š” ์ƒ‰์ธ ๋ฒˆํ˜ธ 15๋ฅผ ์ถœ๋ ฅํ•œ๋‹ค.

ํ˜„์žฌ ์ž…๋ ฅ(w) ๋‹ค์Œ ๊ธ€์ž(c) ์ถœ๋ ฅ ์‚ฌ์ „ ์ถ”๊ฐ€(w+c)
K A 11 27:KA
A K 1 28:AK
KA O 27 29:KAO
O   15  

 

์ด ๊ณผ์ •์„ ๊ฑฐ์ณ ๋‹ค์„ฏ ๊ธ€์ž์˜ ๋ฌธ์žฅ KAKAO๊ฐ€ 4๊ฐœ์˜ ์ƒ‰์ธ ๋ฒˆํ˜ธ [11, 1, 27, 15]๋กœ ์••์ถ•๋œ๋‹ค.

์ž…๋ ฅ ํ˜•์‹

์ž…๋ ฅ์œผ๋กœ ์˜๋ฌธ ๋Œ€๋ฌธ์ž๋กœ๋งŒ ์ด๋ค„์ง„ ๋ฌธ์ž์—ด msg๊ฐ€ ์ฃผ์–ด์ง„๋‹ค. msg์˜ ๊ธธ์ด๋Š” 1 ๊ธ€์ž ์ด์ƒ, 1000 ๊ธ€์ž ์ดํ•˜์ด๋‹ค.

์ถœ๋ ฅ ํ˜•์‹

์ฃผ์–ด์ง„ ๋ฌธ์ž์—ด์„ ์••์ถ•ํ•œ ํ›„์˜ ์‚ฌ์ „ ์ƒ‰์ธ ๋ฒˆํ˜ธ๋ฅผ ๋ฐฐ์—ด๋กœ ์ถœ๋ ฅํ•˜๋ผ.

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

mgs answer
KAKAO [11, 1, 27, 15]
TOBEORNOTTOBEORTOBEORNOT [20, 15, 2, 5, 15, 18, 14, 15, 20, 27, 29, 31, 36, 30, 32, 34]
ABABABABABABABAB [1, 2, 27, 29, 28, 31, 30]

โœ๐Ÿปํ’€์ด

ํ˜„์žฌ ๊ธ€์ž์™€ ๋‹ค์Œ ๊ธ€์ž๋ฅผ ํ•ฉํ•ด์„œ ์—†๋Š” ๊ธ€์ž๋ผ๋ฉด ์ด๋ฅผ ์‚ฌ์ „์— ์ถ”๊ฐ€ํ•˜๊ณ 
์žˆ๋Š” ๊ธ€์ž๋ผ๋ฉด ์ด์ „์— ์ž…๋ ฅํ•œ ๊ธ€์ž๋ฅผ ์ง€์šฐ๊ณ  ํ˜„์žฌ ๊ธ€์ž๋ฅผ ์ถœ๋ ฅํ•œ๋‹ค.

๐Ÿ’ป์ฝ”๋“œ

# ์‚ฌ์ „ ๋…ธ๊ฐ€๋‹ค
def solution(msg):
    dic = {"A" : 1, "B" : 2, "C" : 3, "D" : 4, "E" : 5, "F": 6, "G" : 7, "H" : 8, "I" : 9,
    "J" : 10, "K" : 11, "L": 12, "M": 13, "N" : 14, "O" : 15, "P" : 16, "Q" : 17, "R" : 18,
    "S" : 19, "T" : 20, "U" : 21, "V" : 22, "W" : 23, "X" : 24, "Y" : 25, "Z" : 26}

    answer = []

    j = 1
    w = msg[0]
    answer.append(dic[w])
    msg += " "
    for i in range(1, len(msg) - 1):
        tmp = w + msg[i]
        if tmp in dic:
            w = tmp
            if len(answer) != 0:
                answer.pop()
        else:
            dic[tmp] = 26 + j
            j += 1
            w = msg[i]
        answer.append(dic[w])

    return answer
# zip์„ ์‚ฌ์šฉํ•˜์—ฌ ์‚ฌ์ „ ๋งŒ๋“ค๊ธฐ
def solution(msg):
    dic = dict(zip("ABCDEFGHIJKLMNOPQRSTUVWXYZ", range(1, 27)))

    answer = []

    j = 1
    w = msg[0]
    answer.append(dic[w])
    msg += " "
    for i in range(1, len(msg) - 1):
        tmp = w + msg[i]
        if tmp in dic:
            w = tmp
            if len(answer) != 0:
                answer.pop()
        else:
            dic[tmp] = 26 + j
            j += 1
            w = msg[i]
        answer.append(dic[w])

    return answer

๐Ÿ“ํ›„๊ธฐ

์—„์ฒญ ํฐ ์ฐจ์ด๊ฐ€ ์žˆ๋‹ค๊ณ  ๋Š๋ผ์ง€ ์•Š์œผ๋ฏ€๋กœ zip์„ ์“ฐ๋Š” ๊ฒƒ์ด ํŽธํ•œ ๊ฒƒ ๊ฐ™๋‹ค.

728x90
๋ฐ˜์‘ํ˜•