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

๐Ÿ‘จโ€๐Ÿ’ป ์บ์‹œ(cache) ๋ฌธ์ œ ํ’€์–ด๋ณด๊ธฐ


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

def solution(cacheSize, cities):
    time = 0
    cache = []
    cities = [city.lower() for city in cities]
    if cacheSize != 0:
        for city in cities:
            if city in cache:
                cache.pop(cache.index(city))
                cache.append(city)
                time += 1
            else:
                if len(cache) < cacheSize:
                    cache.append(city)
                    time += 5
                else:
                    cache.pop(0)
                    cache.append(city)
                    time += 5
    else: time += len(cities) * 5
    return time

์šฐ์„  ์ด ๋ฌธ์ œ์—์„œ ์‚ฌ์šฉ ๋œ ์บ์‹œ ๊ต์ฒด ์•Œ๊ณ ๋ฆฌ์ฆ˜์ธ LRU(Least Recently Used) ์•Œ๊ณ ๋ฆฌ์ฆ˜์— ๋Œ€ํ•ด์„œ ์•Œ์•„์•ผ ํ•ฉ๋‹ˆ๋‹ค. ์บ์‹œ์˜ ์‚ฌ์ด์ฆˆ๋Š” ํ•œ์ • ๋˜์–ด์žˆ๊ธฐ ๋•Œ๋ฌธ์— ์บ์‹œ ์‚ฌ์ด์ฆˆ๊ฐ€ ๊ฝ‰ ์ฐฌ ์ƒํƒœ์—์„œ ์ƒˆ๋กœ์šด ์บ์‹œ๋ฅผ ๋„ฃ์œผ๋ ค๋ฉด ๊ธฐ์กด ์บ์‹œ์— ์žˆ๋˜ ๋ฐ์ดํ„ฐ๋ฅผ ๊ต์ฒดํ•ด์•ผํ•˜๋Š” ๋ฐ ์—ฌ๊ธฐ์„œ ์–ด๋–ค ๋ฐ์ดํ„ฐ๋ฅผ ๊ต์ฒดํ•  ๊ฒƒ์ธ๊ฐ€๊ฐ€ ์บ์‹œ ๊ต์ฒด ์•Œ๊ณ ๋ฆฌ์ฆ˜์˜ ๋ชฉ์ ์ž…๋‹ˆ๋‹ค. LRU ์•Œ๊ณ ๋ฆฌ์ฆ˜์€ ์ง์—ญํ•˜์ž๋ฉด ๊ฐ€์žฅ ์ตœ๊ทผ์— ์‚ฌ์šฉ๋˜์ง€ ์•Š์€ ๊ฒƒ ์ฆ‰, ๊ฐ€์žฅ ์˜ค๋ž˜์ „์— ์‚ฌ์šฉํ•œ ๊ฒƒ์„ ์ œ๊ฑฐํ•˜๋Š” ์•Œ๊ณ ๋ฆฌ์ฆ˜์ž…๋‹ˆ๋‹ค. ์ด ์•Œ๊ณ ๋ฆฌ์ฆ˜์˜ ๊ธฐ๋ณธ์  ๊ฐ€์„ค์€ ์˜ค๋žซ๋™์•ˆ ์‚ฌ์šฉํ•˜์ง€ ์•Š์•˜๋˜ ๋ฐ์ดํ„ฐ๋Š” ์•ž์œผ๋กœ๋„ ์‚ฌ์šฉํ•  ํ™•๋ฅ ์ด ์ ๋‹ค๋Š” ๊ฒƒ์ž…๋‹ˆ๋‹ค.

cities = [city.lower() for city in cities]

์œ„์˜ ์„ค๋ช…์— ๋”ฐ๋ผ์„œ ์ฝ”๋“œ๋ฅผ ์ž‘์„ฑํ•ด๋ณด๊ฒ ์Šต๋‹ˆ๋‹ค. ์šฐ์„  ์ž…๋ ฅ ํ˜•์‹์—์„œ ๋Œ€์†Œ๋ฌธ์ž ๊ตฌ๋ถ„์„ ํ•˜์ง€ ์•Š๋Š”๋‹ค๋ผ๋Š” ์กฐ๊ฑด์„ ์ฃผ์—ˆ์œผ๋‹ˆ ๋ฌธ์ œ๋ฅผ ๋‹จ์ˆœํ™”ํ•˜๊ธฐ ์œ„ํ•ด ์ž…๋ ฅ๋œ ๋ฐฐ์—ด ์† ๋ฌธ์ž์—ด์„ ์†Œ๋ฌธ์ž๋กœ ๋ฐ”๊ฟ”์ค๋‹ˆ๋‹ค. ๋ฆฌ์ŠคํŠธ ์ถ•์•ฝ(List Comprehension)์„ ํ†ตํ•ด ์ฝ”๋“œ๋ฅผ ์ข€ ๋” ๊ฐ„๋‹จํžˆ ํ–ˆ์Šต๋‹ˆ๋‹ค.


์ด์ œ ๋ฌธ์ œ๊ฐ€ ๋‹จ์ˆœํ™”๋˜์—ˆ์œผ๋‹ˆ ๋ฐ์ดํ„ฐ๋ฅผ ๋ฐ›์œผ๋ฉฐ ์บ์‹œ๋ฅผ ์ฑ„์›Œ๊ฐ€๋Š” ๊ณผ์ •์„ ์ง„ํ–‰ํ•ฉ๋‹ˆ๋‹ค. ํฐ ๋ถ„๊ธฐ๋Š” cacheSize์˜ ํฌ๊ธฐ๊ฐ€ 0์ธ์ง€ ์˜์ด ์•„๋‹Œ ์ง€๋กœ ๋‚˜๋ˆ•๋‹ˆ๋‹ค. 0์ธ ๊ฒฝ์šฐ ๋ชจ๋“  ๋ฐ์ดํ„ฐ๊ฐ€ cache miss๋กœ ํŒ๋ณ„๋˜์–ด ์ „์ฒด ๋„์‹œ ๋ฐ์ดํ„ฐ ๊ธธ์ด * 5๋งŒํผ ์‹คํ–‰์‹œ๊ฐ„์ด ๋Š˜์–ด๋‚ฉ๋‹ˆ๋‹ค.

if city in cache:
	cache.pop(cache.index(city))
	cache.append(city)
	time += 1

๋‹ค์Œ์€ 0์ด ์•„๋‹Œ ๊ฒฝ์šฐ์ž…๋‹ˆ๋‹ค. 0์ด ์•„๋‹Œ ๊ฒฝ์šฐ ์บ์‹œ์— ๋ฐ์ดํ„ฐ๋ฅผ ์ฑ„์›Œ๊ฐ€๋Š” ์‹œํ–‰์„ ์ง„ํ–‰ํ•˜๊ฒŒ๋ฉ๋‹ˆ๋‹ค. ๋ฐ์ดํ„ฐ๋ฅผ ๋„ฃ๋Š” ๊ฒฝ์šฐ์—๋„ ๊ฐ™์€ ๋„์‹œ ๋ฐ์ดํ„ฐ๊ฐ€ ์ด๋ฏธ ์บ์‹œ ์•ˆ์— ์žˆ๋Š” ๊ฒฝ์šฐ์™€ ๊ทธ๋ ‡์ง€ ์•Š์€ ๊ฒฝ์šฐ๋กœ ๋ถ„๊ธฐ๊ฐ€ ์ƒ๊น๋‹ˆ๋‹ค. ๊ฐ™์€ ๋„์‹œ ๋ฐ์ดํ„ฐ๊ฐ€ ์ด๋ฏธ ์บ์‹œ ์•ˆ์— ์žˆ๋Š” ๊ฒฝ์šฐ ์บ์‹œ์— ์žˆ๋Š” ๋„์‹œ ๋ฐ์ดํ„ฐ๋ฅผ ์—†์—๊ณ  ๊ฐ™์€ ๋„์‹œ ๋ฐ์ดํ„ฐ๋ฅผ cache ๋ฐฐ์—ด์˜ ๋งจ ๋’ค์— ์ถ”๊ฐ€ํ•˜๊ณ , cache hit์ด๊ธฐ ๋•Œ๋ฌธ์— ์‹คํ–‰์‹œ๊ฐ„์ธ time์— 1์„ ๋”ํ•ด์ค๋‹ˆ๋‹ค.


๊ฐ™์€ ๋„์‹œ ๋ฐ์ดํ„ฐ๊ฐ€ ์บ์‹œ ์•ˆ์— ์—†๋Š” ๊ฒฝ์šฐ์—๋Š” ์ƒˆ๋กœ์šด ๋ฐ์ดํ„ฐ๋ฅผ ์บ์‹œ์— ๋„ฃ์–ด์•ผํ•ฉ๋‹ˆ๋‹ค. ๋”ฐ๋ผ์„œ ์ด ๊ฒฝ์šฐ์—๋„ ์บ์‹œ๊ฐ€ ๊ฝ‰ ์ฐฌ ๊ฒฝ์šฐ์™€ ๊ฝ‰ ์ฐจ์ง€ ์•Š์€ ๊ฒฝ์šฐ๋กœ ๋‚˜๋ˆ ์„œ ํ™•์ธํ•ฉ๋‹ˆ๋‹ค. ์บ์‹œ๊ฐ€ ๊ฝ‰ ์ฐฌ๊ฒฝ์šฐ LRU ์•Œ๊ณ ๋ฆฌ์ฆ˜์— ๋”ฐ๋ผ ๊ฐ€์žฅ ์˜ค๋žซ๋™์•ˆ ์“ฐ์ด์ง€ ์•Š์€ cache๋ฐฐ์—ด์˜ 0๋ฒˆ index๋ฅผ popํ•ด์ค๋‹ˆ๋‹ค. ๊ทธ๋ฆฌ๊ณ  ์ƒˆ๋กœ์šด ๋ฐ์ดํ„ฐ๋ฅผ ์บ์‹œ ๋ฐฐ์—ด ๋งจ ๋’ค์— ์ถ”๊ฐ€ํ•ด์ค๋‹ˆ๋‹ค. ์บ์‹œ๊ฐ€ ๊ฝ‰ ์ฐจ์ง€ ์•Š์€ ๊ฒฝ์šฐ์—๋Š” ์บ์‹œ์˜ ๊ต์ฒด ์—†์ด ์ƒˆ๋กœ์šด ๋ฐ์ดํ„ฐ๋งŒ ์ถ”๊ฐ€ํ•ด์ค๋‹ˆ๋‹ค. ์ด ๊ฒฝ์šฐ ๊ฐ™์€ ๋„์‹œ ๋ฐ์ดํ„ฐ๊ฐ€ ์บ์‹œ ์•ˆ์— ์—†๋Š” cache miss์ด๊ธฐ ๋•Œ๋ฌธ์— ์‹คํ–‰ ์‹œ๊ฐ„ time์— 5๋ฅผ ๋”ํ•ด์ค๋‹ˆ๋‹ค.


์ด๋ ‡๊ฒŒ ๊ณ„์‚ฐ๋œ ์‹คํ–‰์‹œ๊ฐ„ time์„ ๋ฐ˜ํ™˜ํ•˜๋ฉด ๋ฌธ์ œ๋Š” ๋งˆ๋ฌด๋ฆฌ๋ฉ๋‹ˆ๋‹ค.

Written with StackEdit.


๋ฐ˜์‘ํ˜•

'Algorithm > Problem Solving' ์นดํ…Œ๊ณ ๋ฆฌ์˜ ๋‹ค๋ฅธ ๊ธ€

[ํ”„๋กœ๊ทธ๋ž˜๋จธ์Šค] ๐Ÿงฑ ํ”„๋ Œ์ฆˆ 4 ๋ธ”๋ก - [1์ฐจ] 2018 ์นด์นด์˜ค ๋ธ”๋ผ์ธ๋“œ ์ฑ„์šฉ / Python  (0) 2019.02.14
[ํ”„๋กœ๊ทธ๋ž˜๋จธ์Šค] ๐Ÿ‘ฉโ€๐Ÿ’ผ ๋‰ด์Šค ํด๋Ÿฌ์Šคํ„ฐ๋ง - [1์ฐจ] 2018 ์นด์นด์˜ค ๋ธ”๋ผ์ธ๋“œ ์ฑ„์šฉ / Python / KAKAO BLIND RECRUITMENT  (0) 2019.02.14
[ํ”„๋กœ๊ทธ๋ž˜๋จธ์Šค] ๐Ÿ‘จโ€๐Ÿ’ป ์บ์‹œ - [1์ฐจ] 2018 ์นด์นด์˜ค ๋ธ”๋ผ์ธ๋“œ ์ฑ„์šฉ / Python  (0) 2019.02.13
[ํ”„๋กœ๊ทธ๋ž˜๋จธ์Šค] ๐ŸŽฏ ๋‹คํŠธ ๊ฒŒ์ž„ - [1์ฐจ] 2018 ์นด์นด์˜ค ๋ธ”๋ผ์ธ๋“œ ์ฑ„์šฉ / Python  (1) 2019.02.12
[ํ”„๋กœ๊ทธ๋ž˜๋จธ์Šค] ๐Ÿ—บ ๋น„๋ฐ€์ง€๋„ - [1์ฐจ] 2018 ์นด์นด์˜ค ๋ธ”๋ผ์ธ๋“œ ์ฑ„์šฉ / Python  (0) 2019.02.12
๐Ÿฅ 2018 ์นด์นด์˜ค ๋ธ”๋ผ์ธ๋“œ ์ฑ„์šฉ ์•Œ๊ณ ๋ฆฌ์ฆ˜ ํ…Œ์ŠคํŠธ 3์ฐจ Python ํ’€์ด ๋ชจ์Œ / KAKAO BLIND RECRUITMENT  (0) 2019.02.09