๐Ÿ†™ Python 2. prefix ๊ตฌํ•˜๋Š” ๋ฐฉ๋ฒ•

yeeun leeยท2020๋…„ 4์›” 12์ผ
0

Python Advanced

๋ชฉ๋ก ๋ณด๊ธฐ
2/2

์•Œ๊ณ ๋ฆฌ์ฆ˜ ๋ฌธ์ œ๋ฅผ ํ’€๋‹ค๊ฐ€ ์ฒ˜์Œ์œผ๋กœ ์ ‘ํ•˜๋Š” ์œ ํ˜•์„ ๋ดค๋‹ค. ์šฐ์„  prefix๋ฅผ ๊ทธ๋Œ€๋กœ ๋ฒˆ์—ญํ•˜๋ฉด ์ ‘๋‘์‚ฌ์ธ๋ฐ, ๋ฌธ์ž์—ด์„ ์—ฌ๋Ÿฌ๊ฐœ ์ฃผ๊ณ , ๊ฐ ์š”์†Œ์˜ ์•ž ๋ถ€๋ถ„๋ถ€ํ„ฐ ๋˜‘๊ฐ™์€ ๋ฌธ์ž๋ฅผ ๋ฐ˜ํ™˜ํ•˜๋Š” ๋ฌธ์ œ์˜€๋‹ค. ์—†์œผ๋ฉด ๊ทธ๋ƒฅ ๋นˆ ๋ฌธ์ž์—ด์„ returnํ•œ๋‹ค.

โญ๏ธ ๋ฌธ์ œ

strs์€ ๋‹จ์–ด๊ฐ€ ๋‹ด๊ธด ๋ฐฐ์—ด์ž…๋‹ˆ๋‹ค. ๊ณตํ†ต๋œ ์‹œ์ž‘ ๋‹จ์–ด(prefix)๋ฅผ ๋ฐ˜ํ™˜ํ•ด์ฃผ์„ธ์š”.

์˜ˆ๋ฅผ ๋“ค์–ด
strs = ['start', 'stair', 'step'] # ourput = 'st'
strs = ['start', 'wework', 'today'] # output = ''

1. ๋‚˜์˜ ์ƒ๊ฐ

๋‚ด๊ฐ€ ์ƒ๊ฐํ–ˆ๋˜ ๋ฐฉ๋ฒ•์€ ์šฐ์„  ์•„๋ž˜์™€ ๊ฐ™์•˜๋‹ค.

  1. ์ œ์ผ ์งง์€ ๋‹จ์–ด์˜ ๊ธธ์ด๋ฅผ ๊ตฌํ•˜๊ณ 
  2. ๊ทธ ๊ธธ์ด๋งŒํผ ๋ฆฌ์ŠคํŠธ์˜ ์š”์†Œ๋“ค์„ for loop๋ฅผ ์ค‘์ฒฉํ•ด์„œ ๋Œ๋ฆฐ๋‹ค.
  3. ๋นˆ ๋ฆฌ์ŠคํŠธ๋ฅผ ๋งŒ๋“ค์–ด์„œ ์š”์†Œ๊ฐ€ ๊ฐ™์„ ๊ฒฝ์šฐ ๋ฆฌ์ŠคํŠธ์— ๋„ฃ๋Š”๋‹ค.

๊ทธ๋Ÿฐ๋ฐ ์š”์†Œ์˜ ๊ฐœ์ˆ˜๋„, ๊ฐ ์š”์†Œ๋“ค์˜ ๊ธธ์ด๋„ ์ •ํ•ด์ง€์ง€ ์•Š์€ ์ƒํƒœ์—์„œ ๋น„๊ตํ•˜๋Š” ๋กœ์ง์„ ์งœ๋Š”๊ฒŒ ๋„ˆ๋ฌด ์–ด๋ ค์› ๋‹ค. nested for loop๋ฅผ ์จ๋„ ์–ด๋–ค ๋ฌธ์ž์—ด์€ ์ •๋‹ต์ด ๋‚˜์™”์ง€๋งŒ ์–ด๋–ค ๋ฌธ์ž์—ด์€ ๋˜ ๋‚˜์˜ค์ง€ ์•Š์•˜๋‹ค ๐Ÿคฏ๐Ÿคฏ๐Ÿคฏ๐Ÿคฏ๐Ÿคฏ๐Ÿคฏ๐Ÿคฏ

2. ํ•ด๊ฒฐ ๋ฐฉ๋ฒ•

์ตœ์†Œ 4-5์‹œ๊ฐ„ ๊ณ ๋ฏผํ–ˆ๋Š”๋ฐ ๋‹ต์ด ์•ˆ ๋‚˜์™€์„œ ๊ตฌ๊ธ€ ์ฑˆ์Šค๋ฅผ ์“ด ๊ฒฐ๊ณผ ๐Ÿ˜ƒ... ๊ฒฐ๊ตญ ์ •๋ ฌ์„ ํ•˜๊ณ  ๋งˆ์ง€๋ง‰ ์š”์†Œ์™€ ๊ธธ์ด๊ฐ€ ๊ฐ€์žฅ ์งง์€ ์š”์†Œ๋งŒ ๋น„๊ตํ•ด์ฃผ๋ฉด ๋˜๋Š” ๊ฑฐ์˜€๋‹ค.

์ฒ˜์Œ์—๋Š” ๋งˆ์ง€๋ง‰ ์š”์†Œ๋ž‘ ๋น„๊ตํ•˜๋ฉด ๋‚˜๋จธ์ง€๋Š”..? ๋‹ค๋ฅธ ์š”์†Œ๋Š” ๊ณ ๋ คํ•˜์ง€ ์•Š์œผ๋ฉด ์–ด๋–กํ•ด? ์‹ถ์—ˆ๋Š”๋ฐ
์‚ฌ์‹ค sort๋กœ ์ •๋ ฌ์„ ํ•˜๊ฒŒ ๋˜๋ฉด ์ŠคํŽ ๋ง์„ ์ˆœ์„œ๋Œ€๋กœ ์ •๋ ฌํ•ด์ฃผ๊ธฐ ๋•Œ๋ฌธ์— ๋งŒ์•ฝ ๋‹ค๋ฅธ ๊ฒƒ์ด ํ•˜๋‚˜๋ผ๋„ ์žˆ๋‹ค๋ฉด, ๋งˆ์ง€๋ง‰ ์š”์†Œ๋งŒ ๋น„๊ตํ•ด์ฃผ๋ฉด ๋˜๋Š” ๊ฒƒ์ด์—ˆ๋‹ค. ๋‹ค๋ฅธ ์š”์†Œ๊ฐ€ ๋” ๋งŽ์•„๋„ ์–ด์ฐจํ”ผ ๋งˆ์ง€๋ง‰๊บผ๋งŒ ๋น„๊ตํ•ด์ฃผ๋ฉด ๋˜๋Š”๊ฑฐ๋‹ค...!

์†”์งํžˆ ํ™• ์™€๋‹ฟ์ง€๋Š” ์•Š๋Š”๋ฐ ์–ด๋Š ์ •๋„๋กœ ์ดํ•ด๋Š” ๊ฐ„๋‹ค. sort method์™€ ๋” ๊ฐ€๊นŒ์›Œ์ ธ์•ผ ๊ฒ ๋‹ค๋Š” ์ƒ๊ฐ์ด ๋“ ๋‹ค.

def get_prefix(string):
  if len(string) == 0:
    return ''
    
  string.sort() # ์ •๋ ฌํ•ด์ฃผ๊ธฐ
  shortest = string[0] #๋น„๊ต ๊ธฐ์ค€์ด ๋˜๋Š” ๋ฌธ์ž์—ด ๋ฝ‘๊ธฐ
  prefix = '' # ์—ฌ๊ธฐ๋‹ค๊ฐ€ ๋„ฃ์–ด์ค„๊ฑฐ์•ผ
  
  for i in range(len(shortest)): 
    if string[len(string)-1][i] == shortest[i]: 
      prefix += string[len(string)-1][i]
    else:
      break
      
  return prefix

- sort()

์˜ค๋ฆ„์ฐจ์ˆœ, ๋‚ด๋ฆผ์ฐจ์ˆœ์„ ์œ„ํ•ด ์‚ฌ์šฉํ•˜๋Š” list method์ด๋‹ค. ์ˆซ์ž๋Š” ์ž‘์€ ์ˆซ์ž๋ถ€ํ„ฐ, ๋ฌธ์ž์—ด์€ a๋ถ€ํ„ฐ ์ˆœ์„œ๋Œ€๋กœ ๋ฐ˜ํ™˜ํ•œ๋‹ค.

์ฃผ์˜ํ•  ์ ์€ sort์˜ ๋ฐ˜๋Œ€๋ฅผ reverse ํ•จ์ˆ˜๋กœ ์ƒ๊ฐํ•˜๋ฉด ์•ˆ ๋œ๋‹ค. reverse ํ•จ์ˆ˜๋Š” ๊ทธ๋ƒฅ ๋ฆฌ์ŠคํŠธ๋ฅผ ๊ฑฐ๊พธ๋กœ ๋ฐ˜ํ™˜ํ•˜๋Š”๊ฑฐ๋‹ค. ๋‚ด๋ฆผ์ฐจ์ˆœ์„ ์œ„ํ•ด์„œ๋Š” reverse๋ฅผ sort์˜ ์˜ต์…˜ ๊ฐ’์œผ๋กœ ๋„ฃ์–ด์•ผ ํ•œ๋‹ค.

a = [ 100, 4, 80, 11, 40 ]
# sort ํ•จ์ˆ˜: ๊ธฐ๋ณธ ๊ฐ’์ด ์˜ค๋ฆ„์ฐจ์ˆœ ์ •๋ ฌ
a.sort()
print(a)  # output = [4, 11, 40, 80, 100]

# sort ํ•จ์ˆ˜์— reverse ์ ์šฉ: ํ•ด๋‹น ์˜ต์…˜์œผ๋กœ ๋‚ด๋ฆผ์ฐจ์ˆœ์œผ๋กœ ํ™•์ธ ๊ฐ€๋Šฅ
a.sort(reverse=True)
print(a)  # output = [100, 80, 40, 11, 4]

# reverse ํ•จ์ˆ˜: ์ธ๋ฑ์Šค๋ฅผ ๋ฐ˜๋Œ€๋กœ ์ ์šฉํ•ด ๋ฐ˜ํ™˜ํ•œ๋‹ค.
a.reverse()
print(a) # output = [40, 11, 80, 4, 100]

์ˆซ์ž๋กœ ์ดํ•ดํ•˜๋ฉด ์‰ฌ์šด๋ฐ, ๋ฌธ์ž์—ด์€ ๋ญ”๊ฐ€ ๋‚ด๋ฆผ, ์˜ค๋ฆ„์ฐจ์ˆœ์— ๋Œ€ํ•ด์„œ ์ง๊ด€์ ์œผ๋กœ ์ƒ๊ฐํ•˜๊ธฐ ํž˜๋“ค๋‹ค. ์ฐธ๊ณ ๋ฅผ ์œ„ํ•ด ๋ฌธ์ž์—ด๋„ ์˜ˆ๋กœ ๋„ฃ์–ด๋ดค๋‹ค.

strs = ['start', 'stair', 'step']
strs.sort()
print(strs) # output = ['stair', 'start', 'step'] 

'''st๊นŒ์ง€๋Š” ๋˜‘๊ฐ™๊ณ , ์„ธ ๋ฒˆ์งธ ๊ธ€์ž๋ถ€ํ„ฐ a,e๋กœ ๋‹ฌ๋ผ์ง„๋‹ค. 
์˜ค๋ฆ„์ฐจ์ˆœ์ด๊ธฐ ๋•Œ๋ฌธ์— a๊ฐ€ ์˜ค๋Š” ๋ฌธ์ž์—ด๋ถ€ํ„ฐ ์•ž์œผ๋กœ ์™”์œผ๋ฉฐ, ๋งˆ์ง€๋ง‰ ๋ฌธ์ž๊ฐ€ e์ด๋ฏ€๋กœ
์ฒซ ๊ธ€์ž์™€ ๋งˆ์ง€๋ง‰ ๊ธ€์ž๋งŒ ๋น„๊ตํ•ด์ฃผ๋ฉด ๋œ๋‹ค.'''

- sotred

sort๊ฐ€ list์˜ method๋ผ๋ฉด, sorted๋Š” ๋ฆฌ์ŠคํŠธ๋ฅผ ์ธ์ž๋กœ ๋„ฃ๋Š” ํ•จ์ˆ˜๋‹ค. ๋งˆ์ฐฌ๊ฐ€์ง€๋กœ ๋ฆฌ์ŠคํŠธ๋ฅผ ์ˆœ์„œ๋Œ€๋กœ ์ •๋ ฌํ•ด์ค€ ๋’ค ๊ฒฐ๊ณผ๊ฐ’์„ ๋ฐ˜ํ™˜ํ•˜๊ณ , itertableํ•œ ๊ฐ์ฒด์— ๋ชจ๋‘ ์ ์šฉ ๊ฐ€๋Šฅํ•˜๋‹ค.

๊ทธ๋ž˜์„œ ๋ฐฐ์› ๋˜ ์ž๋ฃŒ๊ตฌ์กฐ๋“ค๋กœ ๋ชจ๋‘ ์ ์šฉ์„ ํ•ด๋ดค๋‹ค. ํŠน์ง•์ ์ธ ๋ถ€๋ถ„์€ ๋‹ค์Œ๊ณผ ๊ฐ™๋‹ค.

  • tuple, set๋ฅผ sorted ํ•จ์ˆ˜์— ๋„ฃ์œผ๋ฉด ๋ฆฌ์ŠคํŠธ๋กœ ๋ฐ˜ํ™˜๋œ๋‹ค. ํ˜ธ์˜ค... ๐Ÿค”
  • dictionary๋ฅผ sorted ํ•จ์ˆ˜์— ๋„ฃ์œผ๋ฉด ํ‚ค๊ฐ’๋งŒ ์ •๋ ฌํ•ด์„œ ๋ฐ˜ํ™˜ํ•œ๋‹ค. value๊ฐ’์„ ๋ฐ›์œผ๋ ค๋ฉด ์ธ์ž๋กœ list_name.values()๋ฅผ ๋„ฃ์–ด์ฃผ๋ฉด ๋œ๋‹ค.
# list ์˜ค๋ฆ„ ์ฐจ์ˆœ์œผ๋กœ ๋ฐ”๊ฟ”์„œ ๋‹ค๋ฅธ ๋ณ€์ˆ˜์— assign ํ•˜๊ธฐ 
a = [ 100, 4, 80, 11, 40 ]
b = sorted(a) 
print(b) # output = [4, 11, 40, 80, 100]

# tuple
a = ('abc', 'bdkf', 'aaccc')
b = sorted(a)
print(b) # output = ['aaccc', 'abc', 'bdkf']

# set 
a = {'abc', 'bdkf', 'aaccc'}
b = sorted(a)
print(b) # output = ['aaccc', 'abc', 'bdkf']

# dictionary
a = {5:'abc', 3:'fsdb', 1:'aaacc'}
# ๊ธฐ๋ณธ return์€ key๊ฐ’
b = sorted(a)
print(b) # output = [1, 3, 5]

# values method๋กœ value๊ฐ’ ์ •๋ ฌํ•ด์„œ ๋ฆฌํ„ด ๊ฐ€๋Šฅ
b = sorted(a.values())
print(b) # output = ['aaacc', 'abc', 'fsdb']

โ—๏ธ์ฐธ๊ณ  ๋งํฌ

์•„๋ž˜ ๋งํฌ๊ฐ€ prefix, ๊ทธ๋ฆฌ๊ณ  ๋ฆฌ์ŠคํŠธ ์ •๋ ฌ ๊ด€๋ จํ•ด์„œ ๋งค์šฐ ์ž˜ ์ •๋ฆฌํ•ด๋†“์•˜๋‹ค. ์‚ฌ์‹ค ๋ฆฌ์ŠคํŠธ์—์„œ ์š”์†Œ๋ฅผ ๋ฝ‘์•„์„œ ๋„ฃ์„ ์ƒ๊ฐ๋งŒ ํ–ˆ์ง€, ๋ฆฌ์ŠคํŠธ๋ฅผ ์ž˜ ์ •๋ ฌํ•ด์„œ ์‰ฝ๊ฒŒ ํ•ด๊ฒฐํ•  ๋ฐฉ๋ฒ•์€ ๋ชปํ–ˆ๋˜ ๊ฒƒ ๊ฐ™๋‹ค.

์•ž์œผ๋กœ ์œ ์‚ฌํ•œ ๋ฌธ์ œ๊ฐ€ ๋‚˜์˜ค๋ฉด ์ฐธ๊ณ ํ•  ๊ฒƒ โœ”๏ธ

  1. Finding Longest Common Prefix in a List of Strings in Python
  1. Python(ํŒŒ์ด์ฌ) ๊ธฐ๋ณธ - 15. List(๋ฆฌ์ŠคํŠธ)(5) - ๋ฆฌ์ŠคํŠธ ์ •๋ ฌ
profile
์ด์‚ฌ๊ฐ„ ๋ธ”๋กœ๊ทธ: yenilee.github.io

0๊ฐœ์˜ ๋Œ“๊ธ€