[programmers] [3์ฐจ] ์••์ถ• - Java

์‹ ์ž…์‚ฌ์› ์–ดํ”ผ์น˜๋Š” ๋ฉ”์‹œ์ง€๋ฅผ ์••์ถ•ํ•˜์—ฌ ์ „์†ก ํšจ์œจ์„ ๋†’์ด๋Š” ๋ฌด์†์‹ค ์••์ถ• ์•Œ๊ณ ๋ฆฌ์ฆ˜์ธ LZW ์••์ถ•์„ ๊ตฌํ˜„ํ•œ๋‹ค. ์ด ์•Œ๊ณ ๋ฆฌ์ฆ˜์€ ์‚ฌ์ „์— ํ˜„์žฌ ์ž…๋ ฅ๊ณผ ์ผ์น˜ํ•˜๋Š” ๊ฐ€์žฅ ๊ธด ๋ฌธ์ž์—ด์„ ์ฐพ์•„ ์‚ฌ์ „์˜ ์ƒ‰์ธ ๋ฒˆํ˜ธ๋ฅผ ์ถœ๋ ฅํ•˜๊ณ , ์ž…๋ ฅ์—์„œ ํ•ด๋‹น ๋ฌธ์ž์—ด์„ ์ œ๊ฑฐํ•œ๋‹ค. ๊ทธ๋ฆฌ๊ณ  ์ž…๋ ฅ์—์„œ ์ฒ˜๋ฆฌ๋˜์ง€ ์•Š์€ ๋‹ค์Œ ๊ธ€์ž๊ฐ€ ๋‚จ์•„์žˆ๋‹ค๋ฉด, ํ•ด๋‹น ๋‹จ์–ด๋ฅผ ์‚ฌ์ „์— ๋“ฑ๋กํ•œ๋‹ค. ์ด ๊ณผ์ •์„ ๋ฐ˜๋ณตํ•˜์—ฌ ๋ฌธ์ž์—ด์„ ์••์ถ•ํ•œ๋‹ค. ์ด ๋ฌธ์ œ๋ฅผ ํ’€๋ฉด์„œ ์ž๋ฐ”์—์„œ ๊ธฐ๋ณธ์ ์ธ ๋ฌธ์ž์—ด๋“ค์„ ๋‹ค๋ฃจ๋Š” ๋ฐฉ๋ฒ•์„ ์ˆ™์ง€ํ•  ์ˆ˜ ์žˆ๋‹ค.
DriedPollack's avatar
Apr 15, 2024
[programmers] [3์ฐจ] ์••์ถ• - Java

[3์ฐจ] ์••์ถ•

๋ฌธ์ œ ์„ค๋ช…

์‹ ์ž…์‚ฌ์› ์–ดํ”ผ์น˜๋Š” ์นด์นด์˜คํ†ก์œผ๋กœ ์ „์†ก๋˜๋Š” ๋ฉ”์‹œ์ง€๋ฅผ ์••์ถ•ํ•˜์—ฌ ์ „์†ก ํšจ์œจ์„ ๋†’์ด๋Š” ์—…๋ฌด๋ฅผ ๋งก๊ฒŒ ๋˜์—ˆ๋‹ค. ๋ฉ”์‹œ์ง€๋ฅผ ์••์ถ•ํ•˜๋”๋ผ๋„ ์ „๋‹ฌ๋˜๋Š” ์ •๋ณด๊ฐ€ ๋ฐ”๋€Œ์–ด์„œ๋Š” ์•ˆ ๋˜๋ฏ€๋กœ, ์••์ถ• ์ „์˜ ์ •๋ณด๋ฅผ ์™„๋ฒฝํ•˜๊ฒŒ ๋ณต์› ๊ฐ€๋Šฅํ•œ ๋ฌด์†์‹ค ์••์ถ• ์•Œ๊ณ ๋ฆฌ์ฆ˜์„ ๊ตฌํ˜„ํ•˜๊ธฐ๋กœ ํ–ˆ๋‹ค.
์–ดํ”ผ์น˜๋Š” ์—ฌ๋Ÿฌ ์••์ถ• ์•Œ๊ณ ๋ฆฌ์ฆ˜ ์ค‘์—์„œ ์„ฑ๋Šฅ์ด ์ข‹๊ณ  ๊ตฌํ˜„์ด ๊ฐ„๋‹จํ•œ LZW(Lempelโ€“Zivโ€“Welch) ์••์ถ•์„ ๊ตฌํ˜„ํ•˜๊ธฐ๋กœ ํ–ˆ๋‹ค. LZW ์••์ถ•์€ 1983๋…„ ๋ฐœํ‘œ๋œ ์•Œ๊ณ ๋ฆฌ์ฆ˜์œผ๋กœ, ์ด๋ฏธ์ง€ ํŒŒ์ผ ํฌ๋งท์ธ GIF ๋“ฑ ๋‹ค์–‘ํ•œ ์‘์šฉ์—์„œ ์‚ฌ์šฉ๋˜์—ˆ๋‹ค.
LZW ์••์ถ•์€ ๋‹ค์Œ ๊ณผ์ •์„ ๊ฑฐ์นœ๋‹ค.
  1. ๊ธธ์ด๊ฐ€ 1์ธ ๋ชจ๋“  ๋‹จ์–ด๋ฅผ ํฌํ•จํ•˜๋„๋ก ์‚ฌ์ „์„ ์ดˆ๊ธฐํ™”ํ•œ๋‹ค.
  1. ์‚ฌ์ „์—์„œ ํ˜„์žฌ ์ž…๋ ฅ๊ณผ ์ผ์น˜ํ•˜๋Š” ๊ฐ€์žฅ ๊ธด ๋ฌธ์ž์—ด w๋ฅผ ์ฐพ๋Š”๋‹ค.
  1. w์— ํ•ด๋‹นํ•˜๋Š” ์‚ฌ์ „์˜ ์ƒ‰์ธ ๋ฒˆํ˜ธ๋ฅผ ์ถœ๋ ฅํ•˜๊ณ , ์ž…๋ ฅ์—์„œ w๋ฅผ ์ œ๊ฑฐํ•œ๋‹ค.
  1. ์ž…๋ ฅ์—์„œ ์ฒ˜๋ฆฌ๋˜์ง€ ์•Š์€ ๋‹ค์Œ ๊ธ€์ž๊ฐ€ ๋‚จ์•„์žˆ๋‹ค๋ฉด(c), w+c์— ํ•ด๋‹นํ•˜๋Š” ๋‹จ์–ด๋ฅผ ์‚ฌ์ „์— ๋“ฑ๋กํ•œ๋‹ค.
  1. ๋‹จ๊ณ„ 2๋กœ ๋Œ์•„๊ฐ„๋‹ค.
์••์ถ• ์•Œ๊ณ ๋ฆฌ์ฆ˜์ด ์˜๋ฌธ ๋Œ€๋ฌธ์ž๋งŒ ์ฒ˜๋ฆฌํ•œ๋‹ค๊ณ  ํ•  ๋•Œ, ์‚ฌ์ „์€ ๋‹ค์Œ๊ณผ ๊ฐ™์ด ์ดˆ๊ธฐํ™”๋œ๋‹ค. ์‚ฌ์ „์˜ ์ƒ‰์ธ ๋ฒˆํ˜ธ๋Š” ์ •์ˆ˜๊ฐ’์œผ๋กœ ์ฃผ์–ด์ง€๋ฉฐ, 1๋ถ€ํ„ฐ ์‹œ์ž‘ํ•œ๋‹ค๊ณ  ํ•˜์ž.
์ƒ‰์ธ ๋ฒˆํ˜ธ
1
2
3
...
24
25
26
๋‹จ์–ด
A
B
C
...
X
Y
Z
์˜ˆ๋ฅผ ๋“ค์–ด ์ž…๋ ฅ์œผ๋กœ KAKAO๊ฐ€ ๋“ค์–ด์˜จ๋‹ค๊ณ  ํ•˜์ž.
  1. ํ˜„์žฌ ์‚ฌ์ „์—๋Š” KAKAO์˜ ์ฒซ ๊ธ€์ž K๋Š” ๋“ฑ๋ก๋˜์–ด ์žˆ์œผ๋‚˜, ๋‘ ๋ฒˆ์งธ ๊ธ€์ž๊นŒ์ง€์ธ KA๋Š” ์—†์œผ๋ฏ€๋กœ, ์ฒซ ๊ธ€์ž K์— ํ•ด๋‹นํ•˜๋Š” ์ƒ‰์ธ ๋ฒˆํ˜ธ 11์„ ์ถœ๋ ฅํ•˜๊ณ , ๋‹ค์Œ ๊ธ€์ž์ธ A๋ฅผ ํฌํ•จํ•œ KA๋ฅผ ์‚ฌ์ „์— 27 ๋ฒˆ์งธ๋กœ ๋“ฑ๋กํ•œ๋‹ค.
  1. ๋‘ ๋ฒˆ์งธ ๊ธ€์ž A๋Š” ์‚ฌ์ „์— ์žˆ์œผ๋‚˜, ์„ธ ๋ฒˆ์งธ ๊ธ€์ž๊นŒ์ง€์ธ AK๋Š” ์‚ฌ์ „์— ์—†์œผ๋ฏ€๋กœ, A์˜ ์ƒ‰์ธ ๋ฒˆํ˜ธ 1์„ ์ถœ๋ ฅํ•˜๊ณ , AK๋ฅผ ์‚ฌ์ „์— 28 ๋ฒˆ์งธ๋กœ ๋“ฑ๋กํ•œ๋‹ค.
  1. ์„ธ ๋ฒˆ์งธ ๊ธ€์ž์—์„œ ์‹œ์ž‘ํ•˜๋Š” KA๊ฐ€ ์‚ฌ์ „์— ์žˆ์œผ๋ฏ€๋กœ, KA์— ํ•ด๋‹นํ•˜๋Š” ์ƒ‰์ธ ๋ฒˆํ˜ธ 27์„ ์ถœ๋ ฅํ•˜๊ณ , ๋‹ค์Œ ๊ธ€์ž O๋ฅผ ํฌํ•จํ•œ KAO๋ฅผ 29 ๋ฒˆ์งธ๋กœ ๋“ฑ๋กํ•œ๋‹ค.
  1. ๋งˆ์ง€๋ง‰์œผ๋กœ ์ฒ˜๋ฆฌ๋˜์ง€ ์•Š์€ ๊ธ€์ž 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

More articles

See more posts

๐Ÿ‘จ๐Ÿปโ€๐Ÿ’ปDriedPollack's Blog