[programmers] [3์ฐจ] ์์ถ - Java
์ ์
์ฌ์ ์ดํผ์น๋ ๋ฉ์์ง๋ฅผ ์์ถํ์ฌ ์ ์ก ํจ์จ์ ๋์ด๋ ๋ฌด์์ค ์์ถ ์๊ณ ๋ฆฌ์ฆ์ธ LZW ์์ถ์ ๊ตฌํํ๋ค. ์ด ์๊ณ ๋ฆฌ์ฆ์ ์ฌ์ ์ ํ์ฌ ์
๋ ฅ๊ณผ ์ผ์นํ๋ ๊ฐ์ฅ ๊ธด ๋ฌธ์์ด์ ์ฐพ์ ์ฌ์ ์ ์์ธ ๋ฒํธ๋ฅผ ์ถ๋ ฅํ๊ณ , ์
๋ ฅ์์ ํด๋น ๋ฌธ์์ด์ ์ ๊ฑฐํ๋ค. ๊ทธ๋ฆฌ๊ณ ์
๋ ฅ์์ ์ฒ๋ฆฌ๋์ง ์์ ๋ค์ ๊ธ์๊ฐ ๋จ์์๋ค๋ฉด, ํด๋น ๋จ์ด๋ฅผ ์ฌ์ ์ ๋ฑ๋กํ๋ค. ์ด ๊ณผ์ ์ ๋ฐ๋ณตํ์ฌ ๋ฌธ์์ด์ ์์ถํ๋ค. ์ด ๋ฌธ์ ๋ฅผ ํ๋ฉด์ ์๋ฐ์์ ๊ธฐ๋ณธ์ ์ธ ๋ฌธ์์ด๋ค์ ๋ค๋ฃจ๋ ๋ฐฉ๋ฒ์ ์์งํ ์ ์๋ค.
Apr 15, 2024
[3์ฐจ] ์์ถ
๋ฌธ์ ์ค๋ช
์ ์
์ฌ์ ์ดํผ์น๋ ์นด์นด์คํก์ผ๋ก ์ ์ก๋๋ ๋ฉ์์ง๋ฅผ ์์ถํ์ฌ ์ ์ก ํจ์จ์ ๋์ด๋ ์
๋ฌด๋ฅผ ๋งก๊ฒ ๋์๋ค. ๋ฉ์์ง๋ฅผ ์์ถํ๋๋ผ๋ ์ ๋ฌ๋๋ ์ ๋ณด๊ฐ ๋ฐ๋์ด์๋ ์ ๋๋ฏ๋ก, ์์ถ ์ ์ ์ ๋ณด๋ฅผ ์๋ฒฝํ๊ฒ ๋ณต์ ๊ฐ๋ฅํ ๋ฌด์์ค ์์ถ ์๊ณ ๋ฆฌ์ฆ์ ๊ตฌํํ๊ธฐ๋ก ํ๋ค.
์ดํผ์น๋ ์ฌ๋ฌ ์์ถ ์๊ณ ๋ฆฌ์ฆ ์ค์์ ์ฑ๋ฅ์ด ์ข๊ณ ๊ตฌํ์ด ๊ฐ๋จํ LZW(LempelโZivโWelch) ์์ถ์ ๊ตฌํํ๊ธฐ๋ก ํ๋ค. LZW ์์ถ์ 1983๋
๋ฐํ๋ ์๊ณ ๋ฆฌ์ฆ์ผ๋ก, ์ด๋ฏธ์ง ํ์ผ ํฌ๋งท์ธ GIF ๋ฑ ๋ค์ํ ์์ฉ์์ ์ฌ์ฉ๋์๋ค.
LZW ์์ถ์ ๋ค์ ๊ณผ์ ์ ๊ฑฐ์น๋ค.
- ๊ธธ์ด๊ฐ 1์ธ ๋ชจ๋ ๋จ์ด๋ฅผ ํฌํจํ๋๋ก ์ฌ์ ์ ์ด๊ธฐํํ๋ค.
- ์ฌ์ ์์ ํ์ฌ ์
๋ ฅ๊ณผ ์ผ์นํ๋ ๊ฐ์ฅ ๊ธด ๋ฌธ์์ด
w
๋ฅผ ์ฐพ๋๋ค.
w
์ ํด๋นํ๋ ์ฌ์ ์ ์์ธ ๋ฒํธ๋ฅผ ์ถ๋ ฅํ๊ณ , ์ ๋ ฅ์์w
๋ฅผ ์ ๊ฑฐํ๋ค.
- ์
๋ ฅ์์ ์ฒ๋ฆฌ๋์ง ์์ ๋ค์ ๊ธ์๊ฐ ๋จ์์๋ค๋ฉด(
c
),w+c
์ ํด๋นํ๋ ๋จ์ด๋ฅผ ์ฌ์ ์ ๋ฑ๋กํ๋ค.
- ๋จ๊ณ 2๋ก ๋์๊ฐ๋ค.
์์ถ ์๊ณ ๋ฆฌ์ฆ์ด ์๋ฌธ ๋๋ฌธ์๋ง ์ฒ๋ฆฌํ๋ค๊ณ ํ ๋, ์ฌ์ ์ ๋ค์๊ณผ ๊ฐ์ด ์ด๊ธฐํ๋๋ค. ์ฌ์ ์ ์์ธ ๋ฒํธ๋ ์ ์๊ฐ์ผ๋ก ์ฃผ์ด์ง๋ฉฐ, 1๋ถํฐ ์์ํ๋ค๊ณ ํ์.
์์ธ ๋ฒํธ | 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]๋ก ์์ถ๋๋ค.์
๋ ฅ์ผ๋ก
TOBEORNOTTOBEORTOBEORNOT
๊ฐ ๋ค์ด์ค๋ฉด ๋ค์๊ณผ ๊ฐ์ด ์์ถ์ด ์งํ๋๋ค.ํ์ฌ ์
๋ ฅ(w) | ๋ค์ ๊ธ์(c) | ์ถ๋ ฅ | ์ฌ์ ์ถ๊ฐ(w+c) |
T | O | 20 | 27: TO |
O | B | 15 | 28: OB |
B | E | 2 | 29: BE |
E | O | 5 | 30: EO |
O | R | 15 | 31: OR |
R | N | 18 | 32: RN |
N | O | 14 | 33: NO |
O | T | 15 | 34: OT |
T | T | 20 | 35: TT |
TO | B | 27 | 36: TOB |
BE | O | 29 | 37: BEO |
OR | T | 31 | 38: ORT |
TOB | E | 36 | 39: TOBE |
EO | R | 30 | 40: EOR |
RN | O | 32 | 41: RNO |
OT | ใ
ค | 34 | ใ
ค |
์ ๋ ฅ ํ์
์
๋ ฅ์ผ๋ก ์๋ฌธ ๋๋ฌธ์๋ก๋ง ์ด๋ค์ง ๋ฌธ์์ด
msg
๊ฐ ์ฃผ์ด์ง๋ค. msg
์ ๊ธธ์ด๋ 1 ๊ธ์ ์ด์, 1000 ๊ธ์ ์ดํ์ด๋ค.์ถ๋ ฅ ํ์
์ฃผ์ด์ง ๋ฌธ์์ด์ ์์ถํ ํ์ ์ฌ์ ์์ธ ๋ฒํธ๋ฅผ ๋ฐฐ์ด๋ก ์ถ๋ ฅํ๋ผ.
์ ์ถ๋ ฅ ์์
msg | 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] |
solution.java
import java.util.*; class Solution { public List<Integer> solution(String msg) { Map<String, Integer> dictionary = new HashMap<>(); List<Integer> result = new ArrayList<>(); // ๊ธธ์ด๊ฐ 1์ธ ๋ชจ๋ ๋จ์ด๋ก ์ฌ์ ์ด๊ธฐํ for (int i = 0; i < 26; i++) { dictionary.put(Character.toString((char)('A' + i)), i + 1); } int index = 27; // ์ฌ์ ์ ์ถ๊ฐ๋ ๋ค์ ๋จ์ด์ ์ธ๋ฑ์ค ์ ์ธ String w = ""; // ํ์ฌ ๋จ์ด ์ ์ธ for (char c : msg.toCharArray()) { String wc = w + c; // ํ์ธํ ๋ค์ ๋จ์ด // ํ์ธํ ๋ค์ ๋จ์ด๊ฐ ์ฌ์ ์ ์กด์ฌํ๋ค๋ฉด, ๋จ์ด๋ฅผ ์์ฑ if (dictionary.containsKey(wc)) { w = wc; } else { // ํ์ฌ ๋จ์ด w์ ์ธ๋ฑ์ค๋ฅผ ์ถ๋ ฅ result.add(dictionary.get(w)); // ํ์ธํ ๋ค์ ๋จ์ด๋ฅผ ์ฌ์ ์ ์ถ๊ฐ dictionary.put(wc, index++); // ํ์ฌ ๋ฌธ์ c๋ก ์ ๋จ์ด๋ฅผ ์์ w = Character.toString(c); } } // ๋ง์ง๋ง ๋จ์ด์ ์ธ๋ฑ์ค ์ถ๋ ฅ result.add(dictionary.get(w)); return result; } }
ํต์ฌ ํค์๋
์ปฌ๋ ์ ์ด๊ธฐํ:
- ํค๋ ๋ฌธ์์ด์ด๊ณ ๊ฐ์ ์ฌ์ ์ธ๋ฑ์ค ๋ฒํธ๋ฅผ ๋ํ๋ด๋ ์ ์๋ฅผ ๊ฐ์ง๋ ์ฌ์
HashMap
์ ์ ์ธํ๋ค.
- ์์ถ๋ ๋ฉ์์ง๋ฅผ ๋ฆฌํดํ
ArrayList
๋ฅผ ์ ์ธํ๋ค.
๋จ์ผ ๋ฌธ์๋ฅผ ์ฌ์ฉํ ์ฌ์ ์ด๊ธฐํ:
-
A
์์Z
๊น์ง์ ๋จ์ผ ๋ฌธ์๋ก ์ฌ์ ์ ์ด๊ธฐํํ๋ค.
๋จ์ด ์์ฑ ๋ฐ ์์ถ:
- ์
๋ ฅ ๋ฉ์์ง
msg
์ ๊ฐ ๋ฌธ์c
๋ฅผ ๋ฐ๋ณตํ๋ค. - ์ด์ ๋จ์ด
w
๋ฅผ ํ์ฌ ๋ฌธ์c
์ ์ฐ๊ฒฐํ์ฌ ๊ตฌ์ฑํ ํ์ฌ ๋จ์ดwc
๊ฐ ์ฌ์ ์ ์กด์ฌํ๋์ง ํ์ธํ๋ค. wc
๊ฐ ์กด์ฌํ๋ ๊ฒฝ์ฐ ์๊ณ ๋ฆฌ์ฆ์ ๊ณ์ํด์w
๋ผ๋ ๋จ์ด๋ฅผ ๋ง๋ ๋ค.wc
๊ฐ ์ฌ์ ์ ์์ผ๋ฉด ํ์ฌ ๋จ์ดw
์ ์ธ๋ฑ์ค๋ฅผ ๊ฒฐ๊ณผ ๋ชฉ๋ก์ ์ถ๊ฐํ๊ณ , ์ฌ์ฉ ๊ฐ๋ฅํ ๋ค์ ์์ธindex
๊ฐ ์๋ ์ฌ์ ์wc
๋ฅผ ์ถ๊ฐํ๊ณw
๋ฅผ ํ์ฌ ๋ฌธ์c
๋ก ์ ๋ฐ์ดํธํ๋ค.
๊ฒฐ๋ก !
ํด๋น ๋ฌธ์ ๋ฅผ ํ๋ฉด์ ์๋ฐ์์ ๊ธฐ๋ณธ์ ์ธ ๋ฌธ์์ด๋ค์ ๋ค๋ฃจ๋ ๋ฐฉ๋ฒ์ ์์งํ ์ ์์๋ค.
Share article