카카오 1차 코딩테스트 3번 캐시 문제풀이

카카오 1차 코딩 테스트 3번 문제풀이

문제 및 해설 바로가기

3. 캐시(난이도: 하)

캐시크기	도시이름 배열	실행시간
3	"Jeju", "Pangyo", "Seoul", "NewYork", "LA", "Jeju", "Pangyo", "Seoul", "NewYork", "LA"	50
3	"Jeju", "Pangyo", "Seoul", "Jeju", "Pangyo", "Seoul", "Jeju", "Pangyo", "Seoul"	21
2	"Jeju", "Pangyo", "Seoul", "NewYork", "LA", "SanFrancisco", "Seoul", "Rome", "Paris", "Jeju", "NewYork", "Rome"	60
5	"Jeju", "Pangyo", "Seoul", "NewYork", "LA", "SanFrancisco", "Seoul", "Rome", "Paris", "Jeju", "NewYork", "Rome"	52
2	"Jeju", "Pangyo", "NewYork", "newyork"	16
0	"Jeju", "Pangyo", "Seoul", "NewYork", "LA"	25

C++ 소스코드

#include <iostream>
#include <string>
using namespace std;

void ToLower(string *str);

int main()
{
	int cacheSize = 3;
	string cities[]{ "Jeju", "Pangyo", "Seoul", "NewYork", "LA", "Jeju", "Pangyo", "Seoul", "NewYork", "LA" };
	for (auto str : cities)
		cout << str << ", ";
	cout << endl << endl;

	int resultTime = 0;
	if (cacheSize == 0)
	{
		resultTime = sizeof(cities) / sizeof(string);
		resultTime *= 5;
	}
	else
	{
		string *cache = new string[cacheSize];
		int *nArr = new int[cacheSize];

		for (int i = 0; i < cacheSize; i++)
			nArr[i] = cacheSize - i - 1;

		for (auto str : cities)
		{
			ToLower(&str);

			int large = 0;
			int idx = -1;

			for (int i = 0; i < cacheSize; i++)
			{
				if (cache[i].compare(str) == 0) 
				{
					idx = i;
					break;
				}
			}

			for (int i = 0; i < cacheSize; i++)
				nArr[i]++;

			if (idx > -1)
			{
				resultTime += 1;
			}
			else
			{
				for (int i = 0; i < cacheSize; i++)
				{
					if (nArr[i] > large)
					{
						large = nArr[i];
						idx = i;
					}
				}
			
				cache[idx].clear();
				cache[idx].append(str);
				resultTime += 5;
			}
			nArr[idx] = 0;

			for (int i = 0; i < cacheSize; i++)
				cout << cache[i] << ", ";
			cout << endl;
		}

		delete[] nArr;
		delete[] cache;
	}
	cout << endl << "Time: " << resultTime << endl;

	system("pause");
	return 0;
}

void ToLower(string *str)
{
	int leng = (*str).length();
	for (int i = 0; i <= leng; i++)
		(*str)[i] = tolower((*str)[i]);
}