๋ฌธ์ ์ค๋ช
์ง๋๊ฐ๋ฐํ์์ ๊ทผ๋ฌดํ๋ ์ ์ด์ง๋ ์ง๋์์ ๋์ ์ด๋ฆ์ ๊ฒ์ํ๋ฉด ํด๋น ๋์์ ๊ด๋ จ๋ ๋ง์ง ๊ฒ์๋ฌผ๋ค์ ๋ฐ์ดํฐ๋ฒ ์ด์ค์์ ์ฝ์ด ๋ณด์ฌ์ฃผ๋ ์๋น์ค๋ฅผ ๊ฐ๋ฐํ๊ณ ์๋ค.
์ด ํ๋ก๊ทธ๋จ์ ํ ์คํ ์ ๋ฌด๋ฅผ ๋ด๋นํ๊ณ ์๋ ์ดํผ์น๋ ์๋น์ค๋ฅผ ์คํํ๊ธฐ ์ ๊ฐ ๋ก์ง์ ๋ํ ์ฑ๋ฅ ์ธก์ ์ ์ํํ์๋๋ฐ, ์ ์ด์ง๊ฐ ์์ฑํ ๋ถ๋ถ ์ค ๋ฐ์ดํฐ๋ฒ ์ด์ค์์ ๊ฒ์๋ฌผ์ ๊ฐ์ ธ์ค๋ ๋ถ๋ถ์ ์คํ์๊ฐ์ด ๋๋ฌด ์ค๋ ๊ฑธ๋ฆฐ๋ค๋ ๊ฒ์ ์๊ฒ ๋์๋ค.
์ดํผ์น๋ ์ ์ด์ง์๊ฒ ํด๋น ๋ก์ง์ ๊ฐ์ ํ๋ผ๊ณ ๋ฆ๋ฌํ๊ธฐ ์์ํ์๊ณ , ์ ์ด์ง๋ DB ์บ์๋ฅผ ์ ์ฉํ์ฌ ์ฑ๋ฅ ๊ฐ์ ์ ์๋ํ๊ณ ์์ง๋ง ์บ์ ํฌ๊ธฐ๋ฅผ ์ผ๋ง๋ก ํด์ผ ํจ์จ์ ์ธ์ง ๋ชฐ๋ผ ๋๊ฐํ ์ํฉ์ด๋ค.
์ดํผ์น์๊ฒ ์๋ฌ๋ฆฌ๋ ์ ์ด์ง๋ฅผ ๋์, DB ์บ์๋ฅผ ์ ์ฉํ ๋ ์บ์ ํฌ๊ธฐ์ ๋ฐ๋ฅธ ์คํ์๊ฐ ์ธก์ ํ๋ก๊ทธ๋จ์ ์์ฑํ์์ค.
์ ๋ ฅ ํ์
- ์บ์ ํฌ๊ธฐ(cacheSize)์ ๋์์ด๋ฆ ๋ฐฐ์ด(cities)์ ์ ๋ ฅ๋ฐ๋๋ค.
- cacheSize๋ ์ ์์ด๋ฉฐ, ๋ฒ์๋ 0 โฆ cacheSize โฆ 30 ์ด๋ค.
- cities๋ ๋์ ์ด๋ฆ์ผ๋ก ์ด๋ค์ง ๋ฌธ์์ด ๋ฐฐ์ด๋ก, ์ต๋ ๋์ ์๋ 100,000๊ฐ์ด๋ค.
- ๊ฐ ๋์ ์ด๋ฆ์ ๊ณต๋ฐฑ, ์ซ์, ํน์๋ฌธ์ ๋ฑ์ด ์๋ ์๋ฌธ์๋ก ๊ตฌ์ฑ๋๋ฉฐ, ๋์๋ฌธ์ ๊ตฌ๋ถ์ ํ์ง ์๋๋ค. ๋์ ์ด๋ฆ์ ์ต๋ 20์๋ก ์ด๋ฃจ์ด์ ธ ์๋ค.
์ถ๋ ฅ ํ์
- ์ ๋ ฅ๋ ๋์์ด๋ฆ ๋ฐฐ์ด์ ์์๋๋ก ์ฒ๋ฆฌํ ๋, "์ด ์คํ์๊ฐ"์ ์ถ๋ ฅํ๋ค.
์กฐ๊ฑด
- ์บ์ ๊ต์ฒด ์๊ณ ๋ฆฌ์ฆ์ LRU(Least Recently Used)๋ฅผ ์ฌ์ฉํ๋ค.
- cache hit์ผ ๊ฒฝ์ฐ ์คํ์๊ฐ์ 1์ด๋ค.
- cache miss์ผ ๊ฒฝ์ฐ ์คํ์๊ฐ์ 5์ด๋ค.
๋ด ํ์ด
์บ์๋ฅผ queue๋ก ๊ตฌํํด์ ํ์๋ค.
์ฃผ์ํ ์ ์ ์บ์๋ฅผ ์ํํ๋ฉด์ ๋์ ์ด๋ฆ์ ์ฐพ์ ๋, ์บ์ ํฌ๊ธฐ์ ๋ณ๋์ด ์์ ์ ์๊ธฐ ๋๋ฌธ์ ์บ์ ํฌ๊ธฐ๋ฅผ ๋ฏธ๋ฆฌ ์ ์ฅํ ๋ค์ for๋ฌธ์ ๋์์ผํ๋ค๋ ๊ฒ์ด๋ค. ์ด๊ฑธ ๊น๋นกํ๋ค๋ใ ใ
#include <string>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
int solution(int cacheSize, vector<string> cities) {
int answer = 0;
queue<string> cache;
// ์บ์ ํฌ๊ธฐ๊ฐ 0 ์ผ๋
if(cacheSize == 0)
{
answer = cities.size() * 5;
return answer;
}
for(int i = 0; i < cities.size(); i++)
{
// ์๋ฌธ์๋ก ์ ํ
string city;
city.resize(cities[i].size());
transform(cities[i].begin(), cities[i].end(), city.begin(), ::tolower);
// cache๊ฐ ๋น์ด์์ ๊ฒฝ์ฐ
if(cache.empty())
{
cache.push(city);
answer += 5;
continue;
}
// cache์ ํ์ฌ ๋์ ์ด๋ฆ์ด ์๋์ง ์ฐพ๋๋ค
bool find = false;
int size = cache.size();
for(int s = 0; s < size; ++s)
{
string cur = cache.front();
cache.pop();
// ๋์ ์ด๋ฆ์ด ์๋ค๋ฉด ์บ์ ์ ์ค
if(cur == city)
{
find = true;
answer += 1;
}
else
{
cache.push(cur);
}
}
cache.push(city);
// ๋์ ์ด๋ฆ์ด ์์ ๊ฒฝ์ฐ ์บ์ ๋ฏธ์ค
if(!find)
{
answer += 5;
if(cache.size() > cacheSize)
{
cache.pop();
}
}
}
return answer;
}
'๐ฅ๏ธ Study Note > Coding Test' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
[ํ๋ก๊ทธ๋๋จธ์ค]level.2 - ์ฐ์ ๋ถ๋ถ ์์ด ํฉ์ ๊ฐ์(C++) (0) | 2023.07.23 |
---|---|
[ํ๋ก๊ทธ๋๋จธ์ค]level.3 -ํ๋ ธ์ด์ ํ(C++) (2) | 2023.07.22 |
[ํ๋ก๊ทธ๋๋จธ์ค]level.2 - ํํ(C++) (0) | 2023.07.18 |
[ํ๋ก๊ทธ๋๋จธ์ค]level.2 - ์ ์ฐ๊ธฐ(C++) (0) | 2023.07.17 |
[ํ๋ก๊ทธ๋๋จธ์ค]level.2 - 124 ๋๋ผ์ ์ซ์(C++) (0) | 2023.07.14 |