โ๋ฌธ์
์ฑ๋ฅ์์ฝ
์ฝ๋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์ ์ฐ๋ ๊ฒ์ด ํธํ ๊ฒ ๊ฐ๋ค.
'Coding Test > Algorithms' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
[์ํํฐ์ด] ์ฅ์ ๋ฌผ ์ธ์ ํ๋ก๊ทธ๋จ/Python - Lv.2 (0) | 2024.10.29 |
---|---|
[ํ๋ก๊ทธ๋๋จธ์ค] ์์ ์ฐพ๊ธฐ/Python - Lv.2 (0) | 2024.10.25 |
[ํ๋ก๊ทธ๋๋จธ์ค] ํ๋ฐฐ์์/Java - Lv.2 (0) | 2024.10.24 |
[ํ๋ก๊ทธ๋๋จธ์ค] ํ ์ธํ์ฌ/Java - Lv.2 (0) | 2024.10.21 |
[Baekjoon] 1904.01ํ์ผ/Java - Silver3 (0) | 2024.10.15 |