๊ธ€ ์ž‘์„ฑ์ž: ํƒ์‹œ ์šด์ „์‚ฌ
๋ฐ˜์‘ํ˜•

๐Ÿ˜Ž ์ž๋™์™„์„ฑ - [3์ฐจ] 2018 ์นด์นด์˜ค ๋ธ”๋ผ์ธ๋“œ ์ฑ„์šฉ

๋ฌธ์ œ ์„ค๋ช…

ํฌํ„ธ ๋‹ค์Œ์—์„œ ๊ฒ€์ƒ‰์–ด ์ž๋™์™„์„ฑ ๊ธฐ๋Šฅ์„ ๋„ฃ๊ณ  ์‹ถ์€ ๋ผ์ด์–ธ์€ ํ•œ ๋ฒˆ ์ž…๋ ฅ๋œ ๋ฌธ์ž์—ด์„ ํ•™์Šตํ•ด์„œ ๋‹ค์Œ ์ž…๋ ฅ ๋•Œ ํ™œ์šฉํ•˜๊ณ  ์‹ถ์–ด ์กŒ๋‹ค. ์˜ˆ๋ฅผ ๋“ค์–ด, go ๊ฐ€ ํ•œ ๋ฒˆ ์ž…๋ ฅ๋˜์—ˆ๋‹ค๋ฉด, ๋‹ค์Œ ์‚ฌ์šฉ์ž๋Š” g ๋งŒ ์ž…๋ ฅํ•ด๋„ go๋ฅผ ์ถ”์ฒœํ•ด์ฃผ๋ฏ€๋กœ o๋ฅผ ์ž…๋ ฅํ•  ํ•„์š”๊ฐ€ ์—†์–ด์ง„๋‹ค! ๋‹จ, ํ•™์Šต์— ์‚ฌ์šฉ๋œ ๋‹จ์–ด๋“ค ์ค‘ ์•ž๋ถ€๋ถ„์ด ๊ฐ™์€ ๊ฒฝ์šฐ์—๋Š” ์–ด์ฉ” ์ˆ˜ ์—†์ด ๋‹ค๋ฅธ ๋ฌธ์ž๊ฐ€ ๋‚˜์˜ฌ ๋•Œ๊นŒ์ง€ ์ž…๋ ฅ์„ ํ•ด์•ผ ํ•œ๋‹ค.

ํšจ๊ณผ๊ฐ€ ์–ผ๋งˆ๋‚˜ ์ข‹์„์ง€ ์•Œ๊ณ  ์‹ถ์€ ๋ผ์ด์–ธ์€ ํ•™์Šต๋œ ๋‹จ์–ด๋“ค์„ ์ฐพ์„ ๋•Œ ๋ช‡ ๊ธ€์ž๋ฅผ ์ž…๋ ฅํ•ด์•ผ ํ•˜๋Š”์ง€ ๊ถ๊ธˆํ•ด์กŒ๋‹ค.

์˜ˆ๋ฅผ ๋“ค์–ด, ํ•™์Šต๋œ ๋‹จ์–ด๋“ค์ด ์•„๋ž˜์™€ ๊ฐ™์„ ๋•Œ

  • go
  • gone
  • guild

go๋ฅผ ์ฐพ์„ ๋•Œ go๋ฅผ ๋ชจ๋‘ ์ž…๋ ฅํ•ด์•ผ ํ•œ๋‹ค.

gone์„ ์ฐพ์„ ๋•Œ gon ๊นŒ์ง€ ์ž…๋ ฅํ•ด์•ผ ํ•œ๋‹ค. (gon์ด ์ž…๋ ฅ๋˜๊ธฐ ์ „๊นŒ์ง€๋Š” go ์ธ์ง€ gone์ธ์ง€ ํ™•์‹ ํ•  ์ˆ˜ ์—†๋‹ค.)

guild๋ฅผ ์ฐพ์„ ๋•Œ๋Š” gu ๊นŒ์ง€๋งŒ ์ž…๋ ฅํ•˜๋ฉด guild๊ฐ€ ์™„์„ฑ๋œ๋‹ค.

์ด ๊ฒฝ์šฐ ์ด ์ž…๋ ฅํ•ด์•ผ ํ•  ๋ฌธ์ž์˜ ์ˆ˜๋Š” 7์ด๋‹ค.


๋ผ์ด์–ธ์„ ๋„์™€ ์œ„์™€ ๊ฐ™์ด ๋ฌธ์ž์—ด์ด ์ž…๋ ฅ์œผ๋กœ ์ฃผ์–ด์ง€๋ฉด ํ•™์Šต์„ ์‹œํ‚จ ํ›„, ํ•™์Šต๋œ ๋‹จ์–ด๋“ค์„ ์ˆœ์„œ๋Œ€๋กœ ์ฐพ์„ ๋•Œ ๋ช‡ ๊ฐœ์˜ ๋ฌธ์ž๋ฅผ ์ž…๋ ฅํ•˜๋ฉด ๋˜๋Š”์ง€ ๊ณ„์‚ฐํ•˜๋Š” ํ”„๋กœ๊ทธ๋žจ์„ ๋งŒ๋“ค์–ด๋ณด์ž.

์ž…๋ ฅ ํ˜•์‹

ํ•™์Šต๊ณผ ๊ฒ€์ƒ‰์— ์‚ฌ์šฉ๋  ์ค‘๋ณต ์—†๋Š” ๋‹จ์–ด N๊ฐœ๊ฐ€ ์ฃผ์–ด์ง„๋‹ค. 

๋ชจ๋“  ๋‹จ์–ด๋Š” ์•ŒํŒŒ๋ฒณ ์†Œ๋ฌธ์ž๋กœ ๊ตฌ์„ฑ๋˜๋ฉฐ ๋‹จ์–ด์˜ ์ˆ˜ N๊ณผ ๋‹จ์–ด๋“ค์˜ ๊ธธ์ด์˜ ์ดํ•ฉ L์˜ ๋ฒ”์œ„๋Š” ๋‹ค์Œ๊ณผ ๊ฐ™๋‹ค.


2 <= N <= 100,000

2 <= L <= 1,000,000

์ถœ๋ ฅ ํ˜•์‹

๋‹จ์–ด๋ฅผ ์ฐพ์„ ๋•Œ ์ž…๋ ฅํ•ด์•ผ ํ•  ์ด ๋ฌธ์ž์ˆ˜๋ฅผ ๋ฆฌํ„ดํ•œ๋‹ค.

๐Ÿ˜ƒ ๋‚˜์˜ ์ฝ”๋“œ

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
def compare3(word1, target, word2):
    for i in range(1len(target)+1):
        if i == (len(target)) :
            return len(target)
        if (target[0:i] != word1[0:i]) and (target[0:i] != word2[0:i]):
            return i
        
def compare2(word1, target):
    for i in range(1len(target)+1):
        if i == (len(target)) :
            return len(target)
        if target[0:i] != word1[0:i]:
            return i  
 
def solution(words):
    answer = 0
    words.sort()
    for idx, word in enumerate(words):
        if idx == 0:
            answer += compare2(words[idx+1], words[idx])
        elif idx == (len(words)-1):
            answer += compare2(words[idx-1], words[idx])
        else:
            answer += compare3(words[idx-1], words[idx], words[idx+1])
    return answer
cs


์ฒ˜์Œ ์งฐ์„ ๋•Œ ์‹œ๊ฐ„ ์ดˆ๊ณผ๋กœ ๊ณ„์† ํ†ต๊ณผ๋ฅผ ๋ชปํ–ˆ๋Š”๋ฐ, ์ฒ˜์Œ ํ•ด๊ฒฐ๋ฒ•์€ ๋‹ค์Œ๊ณผ ๊ฐ™๋‹ค.


์ฒซ ๋‹จ์–ด๋ถ€ํ„ฐ ๋งˆ์ง€๋ง‰ ๋‹จ์–ด๊นŒ์ง€ ๋ฌธ์ž์—ด์„ ์ž๋ฅด๋ฉด์„œ ๋‹ค์‹œ ์ „์ฒด ๋‹จ์–ด์™€ ๋น„๊ตํ•˜๋Š” ์‹์ด๋‹ค. ์ด๋ ‡๊ฒŒํ•˜๋ฉด ์‹œ๊ฐ„๋ณต์žก๋„๋Š” O(n^2)์ด ๋œ๋‹ค. O(n^2)์˜ ๋ณต์žก๋„์—์„œ ์‹œ๊ฐ„ ์ดˆ๊ณผ๊ฐ€ ๋–ด์œผ๋‹ˆ ์ด ์‹œ๊ฐ„ ๋ณต์žก๋„๋ฅผ ์ค„์—ฌ์•ผํ–ˆ๋‹ค.


๊ทธ๋ž˜์„œ ๋‘๋ฒˆ์งธ ์‹œํ–‰ ์ „์ฒด ๋‹จ์–ด์™€ ๋น„๊ตํ•˜๋Š” ์‹œํ–‰์„ ์ „์ฒด๋ฅผ ์‚ฌ์ „์‹์œผ๋กœ ์ •๋ ฌํ•˜์—ฌ ์ขŒ, ์šฐ๋งŒ ํ™•์ธํ•˜๋Š” ๋ฐฉ์‹์œผ๋กœ ๋ฐ”๊ฟจ๋‹ค. ์ด๋ ‡๊ฒŒ ํ•˜๋ฉด, ์ •๋ ฌํ•˜๋Š” ๋ฐ ๋“œ๋Š” ์‹œ๊ฐ„ ๋ณต์žก๋„์ธ O(nlogn)๊ฐ€ ์ „์ฒด ์‹œ๊ฐ„ ๋ณต์žก๋„๊ฐ€ ๋œ๋‹ค ( ์ „์ฒด ๋‹จ์–ด๋ฅผ ํ™•์ธ ํ•˜๋Š” ์‹œํ–‰์€ O(n)์œผ๋กœ O(nlogn)๋ณด๋‹ค ์ž‘๊ธฐ ๋•Œ๋ฌธ์— ๋ฌด์‹œ ) ์ด๋Ÿฐ ์‹์œผ๋กœ ๋ฐฉ๋ฒ•๋งŒ ์ •ํ•ด์ ธ์žˆ๋‹ค๋ฉด ๊ฒฐ๊ณผ๋ฅผ ๊ตฌํ•˜๋Š” ๊ณผ์ •์€ ํฌ๊ฒŒ ์–ด๋ ต์ง€ ์•Š๋‹ค.


ํ•ด๋‹น ๋ฌธ์ œ๋Š” [3์ฐจ] ์นด์นด์˜ค ๋ธ”๋ผ์ธ๋“œ ์ฑ„์šฉ ์ฝ”๋”ฉ ํ…Œ์ŠคํŠธ์—์„œ ๊ฐ€์žฅ ์–ด๋ ค์› ๋˜ ๋ฌธ์ œ๋ผ๊ณ  ํ•œ๋‹ค. ๋‚˜์™€ ๊ฐ™์ด ์‹œ๊ฐ„ ์ดˆ๊ณผ์œผ๋กœ ๋ฉ˜๋ถ•์ด ์™€์„œ ๊ทธ๋Ÿฐ ๊ฑฐ๋ผ๊ณ  ์ƒ๊ฐํ•œ๋‹ค. 3์ฐจ๊นŒ์ง€ ๊ฐ„ ์‚ฌ๋žŒ๋“ค์ด 34.07%์˜ ์ •๋‹ต๋ฅ ์„ ๋ณด์˜€์œผ๋‹ˆ ์–ผ๋งˆ๋‚˜ ๊นŒ๋‹ค๋กœ์› ๋Š” ์ง€ ์ƒ์ƒ์ด ๊ฐ„๋‹ค.


์œ„์— ๋‚˜์˜ ๋ฐฉ์‹๊ณผ ๋‹ค๋ฅด๊ฒŒ ๋ฌธ์ œ ์ž์ฒด์—์„œ ์›ํ–ˆ๋˜ ๊ฒƒ์€ ํŠธ๋ผ์ด(Tri)๋ผ๋Š” ์ž๋ฃŒ๊ตฌ์กฐ์˜ ์‚ฌ์šฉํ•˜์—ฌ, ์ž…๋ ฅ์œผ๋กœ ์ฃผ์–ด์ง„ ๋‹จ์–ด๋กœ ํŠธ๋ผ์ด๋ฅผ ๊ตฌ์„ฑํ•˜์—ฌ, ๊ฐ™์€ ์ ‘๋‘์–ด(Prefix)๋ฅผ ๊ฐ–๋Š” ๋‹จ์–ด๊ฐ€ ์–ผ๋งˆ๋‚˜ ์žˆ๋Š” ์ง€๋ฅผ ํšจ๊ณผ์ ์œผ๋กœ ์ฐพ๋Š” ๊ฒƒ์ด๋‹ค.


๐Ÿ‘€ ๋ˆˆ์—ฌ๊ฒจ ๋ณผ๋งŒํ•œ ํ’€์ด

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class Trie():
    def __init__(self):
        self.next = dict()
        self.value = 0
 
def solution(words):
    answer = 0
    tree = Trie()
    for word in words:
        subtree = tree
        for idx, val in enumerate(word):
            subtree.value += 1
            if val not in subtree.next:
                subtree.next[val] = Trie()
            subtree = subtree.next[val]
            if (idx == len(word) - 1):
                subtree.value += 1
 
    for word in words:
        subtree = tree
        counts = 0
        for idx, val in enumerate(word):
            if (subtree.value == 1):
                answer += counts
                break
            elif idx == len(word) - 1:
                answer += counts + 1
                break
            else:
                subtree = subtree.next[val]
                counts += 1
 
 
    return answer
 
cs


์œ„์— ์–ธ๊ธ‰ํ•œ ํŠธ๋ผ์ด ์ž๋ฃŒ๊ตฌ์กฐ๋ฅผ ์‚ฌ์šฉํ•œ ํ’€์ด์ด๋‹ค.



๋ฐ˜์‘ํ˜•