[ํ”„๋กœ๊ทธ๋ž˜๋จธ์Šค]level.2 - ์บ์‹œ(C++)

2023. 7. 20. 12:41ยท๐Ÿ–ฅ๏ธ Study Note/Coding Test

๋ฌธ์ œ ์„ค๋ช…

์ง€๋„๊ฐœ๋ฐœํŒ€์—์„œ ๊ทผ๋ฌดํ•˜๋Š” ์ œ์ด์ง€๋Š” ์ง€๋„์—์„œ ๋„์‹œ ์ด๋ฆ„์„ ๊ฒ€์ƒ‰ํ•˜๋ฉด ํ•ด๋‹น ๋„์‹œ์™€ ๊ด€๋ จ๋œ ๋ง›์ง‘ ๊ฒŒ์‹œ๋ฌผ๋“ค์„ ๋ฐ์ดํ„ฐ๋ฒ ์ด์Šค์—์„œ ์ฝ์–ด ๋ณด์—ฌ์ฃผ๋Š” ์„œ๋น„์Šค๋ฅผ ๊ฐœ๋ฐœํ•˜๊ณ  ์žˆ๋‹ค.

์ด ํ”„๋กœ๊ทธ๋žจ์˜ ํ…Œ์ŠคํŒ… ์—…๋ฌด๋ฅผ ๋‹ด๋‹นํ•˜๊ณ  ์žˆ๋Š” ์–ดํ”ผ์น˜๋Š” ์„œ๋น„์Šค๋ฅผ ์˜คํ”ˆํ•˜๊ธฐ ์ „ ๊ฐ ๋กœ์ง์— ๋Œ€ํ•œ ์„ฑ๋Šฅ ์ธก์ •์„ ์ˆ˜ํ–‰ํ•˜์˜€๋Š”๋ฐ, ์ œ์ด์ง€๊ฐ€ ์ž‘์„ฑํ•œ ๋ถ€๋ถ„ ์ค‘ ๋ฐ์ดํ„ฐ๋ฒ ์ด์Šค์—์„œ ๊ฒŒ์‹œ๋ฌผ์„ ๊ฐ€์ ธ์˜ค๋Š” ๋ถ€๋ถ„์˜ ์‹คํ–‰์‹œ๊ฐ„์ด ๋„ˆ๋ฌด ์˜ค๋ž˜ ๊ฑธ๋ฆฐ๋‹ค๋Š” ๊ฒƒ์„ ์•Œ๊ฒŒ ๋˜์—ˆ๋‹ค.

์–ดํ”ผ์น˜๋Š” ์ œ์ด์ง€์—๊ฒŒ ํ•ด๋‹น ๋กœ์ง์„ ๊ฐœ์„ ํ•˜๋ผ๊ณ  ๋‹ฆ๋‹ฌํ•˜๊ธฐ ์‹œ์ž‘ํ•˜์˜€๊ณ , ์ œ์ด์ง€๋Š” 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
'๐Ÿ–ฅ๏ธ Study Note/Coding Test' ์นดํ…Œ๊ณ ๋ฆฌ์˜ ๋‹ค๋ฅธ ๊ธ€
  • [ํ”„๋กœ๊ทธ๋ž˜๋จธ์Šค]level.2 - ์—ฐ์† ๋ถ€๋ถ„ ์ˆ˜์—ด ํ•ฉ์˜ ๊ฐœ์ˆ˜(C++)
  • [ํ”„๋กœ๊ทธ๋ž˜๋จธ์Šค]level.3 -ํ•˜๋…ธ์ด์˜ ํƒ‘(C++)
  • [ํ”„๋กœ๊ทธ๋ž˜๋จธ์Šค]level.2 - ํŠœํ”Œ(C++)
  • [ํ”„๋กœ๊ทธ๋ž˜๋จธ์Šค]level.2 - ์  ์ฐ๊ธฐ(C++)
Beankong_
Beankong_
์ฃผ๋‹ˆ์–ด ํด๋ผ์ด์–ธํŠธ ํ”„๋กœ๊ทธ๋ž˜๋จธ ๊ณต๋ถ€ ๊ธฐ๋ก
  • Beankong_
    Beankong's Devlog
    Beankong_
  • ์ „์ฒด
    ์˜ค๋Š˜
    ์–ด์ œ
    • ์ „์ฒด ๊ธ€ (146)
      • โ›… Daily (0)
      • ๐Ÿ–ฅ๏ธ Study Note (2)
        • C++ (1)
        • Unreal Engine (5)
        • Coding Test (123)
        • Design Patteren (5)
        • VCS (Git..) (1)
        • Server (1)
      • ๐Ÿงญ Devlog (8)
        • ์˜ค๋‹ต๋…ธํŠธ (4)
        • UE5 GameLift Server Test Project (1)
        • TIL (3)
  • ๋ธ”๋กœ๊ทธ ๋ฉ”๋‰ด

    • ๋งํฌ

    • ๊ณต์ง€์‚ฌํ•ญ

    • ์ธ๊ธฐ ๊ธ€

    • ํƒœ๊ทธ

      UnrealEngine5
      ์ฝ”๋”ฉํ…Œ์ŠคํŠธ
      ๊ทธ๋ž˜ํ”„ ์ˆœํšŒ
      ์ตœ๋‹จ ๊ฑฐ๋ฆฌ ์•Œ๊ณ ๋ฆฌ์ฆ˜
      ๊ทธ๋ฆฌ๋””(greedy)
      ๊ฒŒ์ž„ ๊ฐœ๋ฐœ
      ํ—ฌํ…Œ์ด์ปค
      UnrealEngine
      ๊ฒŒ์ž„ ๋ชจ์ž‘
      cpp
      ๊ฒŒ์ž„ํ”„๋กœ๊ทธ๋ž˜๋ฐ
      ์•Œ๊ณ ๋ฆฌ์ฆ˜
      ํ”„๋ฃŒ๊ทธ๋ž˜๋จธ์Šค
      propertyaccess
      unrealengine build system
      unrealengine module
      OnlineSubsystem
      ํ”„๋กœ๊ทธ๋ž˜๋จธ์Šค
      ๊ฒŒ์ž„ ํ”„๋กœ๊ทธ๋ž˜๋ฐ
      programmers
    • ์ตœ๊ทผ ๋Œ“๊ธ€

    • ์ตœ๊ทผ ๊ธ€

    • hELLOยท Designed By์ •์ƒ์šฐ.v4.10.3
    Beankong_
    [ํ”„๋กœ๊ทธ๋ž˜๋จธ์Šค]level.2 - ์บ์‹œ(C++)
    ์ƒ๋‹จ์œผ๋กœ

    ํ‹ฐ์Šคํ† ๋ฆฌํˆด๋ฐ”