programmers.co.kr/learn/courses/30/lessons/72413

 

코딩테스트 연습 - 합승 택시 요금

6 4 6 2 [[4, 1, 10], [3, 5, 24], [5, 6, 2], [3, 1, 41], [5, 1, 24], [4, 6, 50], [2, 4, 66], [2, 3, 22], [1, 6, 25]] 82 7 3 4 1 [[5, 7, 9], [4, 6, 4], [3, 6, 1], [3, 2, 3], [2, 1, 6]] 14 6 4 5 6 [[2,6,6], [6,3,7], [4,6,7], [6,5,11], [2,5,12], [5,3,20], [2,4

programmers.co.kr

<풀이>

1. 적절한 지점까지 합승을 하여, 택시 요금이 최소가 되는 택시 요금을 구한다.

2. 최소 택시 요금을 반환한다.

 

<해법>

택시 합승은 다음과 같이 이루어집니다.

s에서 어떤 지점까지는 합승을 하고, 그 지점에서 각자 택시를 타고 가는 것입니다.

이 때 알아야 하는 것은 s에서 어떤 지점까지 가는 최소 요금, 어떤 지점에서 각자 도착지점까지 가는 최소 요금 이렇게 두 가지 입니다.

여기서 모든 정점 간의 최소거리를 계산하는 플로이드 알고리즘을 떠올릴 수 있습니다. 

따라서, 플로이드 알고리즘을 이용하여 모든 정점 간의 최소 거리를 구하고, 각각 지점까지 합승했을 때의 택시요금을 구한 후, 그 중 최소요금을 반환합니다.

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
#include <iostream>
#include <string>
#include <vector>
#include <string.h>
#include <algorithm>
#define INF 123456789
 
using namespace std;
 
int W[201][201]; //주어진 그래프
int D[201][201]; //플로이드 알고리즘을 거친 후, 최단거리 배열
 
//플로이드 알고리즘
void floyd(int n) {
 
    //초기화
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            D[i][j] = W[i][j];
        }
    }
 
    //플로이드 핵심
    for (int k = 1; k <= n; k++) {
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                D[i][j] = min(D[i][j], D[i][k] + D[k][j]);
            }
        }
    }
    
}
 
int solution(int n, int s, int a, int b, vector<vector<int>> fares) {
 
    int answer = INF;
 
    //초기화
    memset(W, INF, sizeof(W));
    for (int i = 1; i <= n; i++) {
        //1번지점 -> 1번지점으로 가는 경우 -> 0원
        W[i][i] = 0;
    }
 
    //그래프 그리기
    for (int i = 0; i < fares.size(); i++) {
        int first = fares[i][0];
        int second = fares[i][1];
        int fare = fares[i][2];
 
        W[first][second] = fare;
        W[second][first] = fare;
    }
 
    //플로이드 알고리즘
    floyd(n);
 
    //정답 갱신
    for (int i = 1; i <= n; i++) {
        /*
        D[s][i] + D[i][a] + D[i][b]
        : s부터 i까지는 같이가고, i부터는 각자 가는 경우의 택시요금
        */
        answer = min(answer, D[s][i] + D[i][a] + D[i][b]);
    }
 
    //반환
    return answer;
}
 

 

플로이드 알고리즘에 대해 알아볼 수 있는 문제였습니다.

저작자표시

'알고리즘 문제풀이 > 프로그래머스' 카테고리의 다른 글

[C++] 프로그래머스 - 파일명 정렬  (0) 2021.04.23
[C++] 프로그래머스 - 순위 검색  (0) 2021.02.02
[C++] 프로그래머스 - 메뉴 리뉴얼  (0) 2021.01.31
[C++] 프로그래머스 - 신규 아이디 추천  (0) 2021.01.31
[C++] 프로그래머스 - 압축  (0) 2021.01.19

programmers.co.kr/learn/courses/30/lessons/72411

 

코딩테스트 연습 - 메뉴 리뉴얼

레스토랑을 운영하던 스카피는 코로나19로 인한 불경기를 극복하고자 메뉴를 새로 구성하려고 고민하고 있습니다. 기존에는 단품으로만 제공하던 메뉴를 조합해서 코스요리 형태로 재구성해서

programmers.co.kr

<풀이>

1. 주어진 메뉴의 개수만큼 가장 많이 선택된 메뉴 조합을 구한다.

2. 메뉴 조합을 사전순으로 정렬하고 반환한다.

 

<해법>

1. 주문한 메뉴 조합에서 코스 개수에 따른 조합 개수 구하는 방법

=> 주문한 메뉴 조합이 "ABCDE"이고 만들려고하는 코스 개수가 "2"개라면 만들 수 있는 모든 코스는 AB, AC, AD, AE, BC, BD, ... 이 있습니다. 이렇게 만들어진 코스 이름과 코스 개수를 저장해두어야 합니다. 따라서, 저는 map을 사용하여 만들어진 코스 이름과 코스 개수를 저장해두었습니다.

예를 들어, 메뉴조합은 "ABCDE, AB, CDE"이고 코스개수는 "2"개 라고 한다면

ABCDE -> AB, AC, AD, AE, BC, BD, ...

AB -> AB

CDE -> CD, CE, DE

메뉴조합은 위와 같이 나타낼 수 있습니다.

이를 map에 [AB : 2], [AC : 1], [AD: 1] 방식으로 저장합니다.

 

2. 가장 많이 함께 주문된 메뉴 구성 구하는 방법

=> 메뉴 구성과 개수를 map에 저장해두었습니다. map에 있는 개수를 기준으로 정렬하여야 하므로, map에 있는 데이터를 vector로 옮기고 정렬을 진행하였습니다. 이 후, 가장 많이 함께 구성된 메뉴를 answer에 넣어줍니다.

 

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <algorithm>
 
using namespace std;
 
map<string, int> m;
 
bool cmp(pair<string, int> a, pair<string, int> b) {
    return a.second > b.second;
}
 
void findAllCourse(string order, int size, string s, int index) {
 
    //종료조건
    if (s.length() == size) {
        map<string, int>::iterator iter;
 
        iter = m.find(s);
 
        //맵에 코스가 이미 존재하는 경우 -> 개수 + 1
        if (iter != m.end()) {
            iter->second++;
        }
        //맵에 코스가 존재하지 않는 경우 -> 맵에 삽입
        else {
            m.insert(pair<string, int>(s, 1));
        }
 
        return;
    }
 
    for (int i = index; i < order.length(); i++) {
        findAllCourse(order, size, s + order[i], i + 1);
    }
}
 
vector<string> solution(vector<string> orders, vector<int> course) {
 
    vector<string> answer;
 
    //코스 크기 만큼 모두 해보기
    for (int i = 0; i < course.size(); i++) {
 
        m.clear();
 
        for (int j = 0; j < orders.size(); j++) {
 
            //메뉴 정렬(ex. CBA -> ABC)
            sort(orders[j].begin(), orders[j].end());
 
            //주문한 조합에서 코스 개수만큼 골라서, 모든 조합 만들기 -> 맵에 저장
            if (course[i] <= orders[j].length()) {
                findAllCourse(orders[j], course[i], "", 0);
            }
        }
 
        //map -> vector 옮기기
        vector<pair<string, int>> v(m.begin(), m.end());
 
        //만들어진 조합 개수에 따라 정렬
        sort(v.begin(), v.end(), cmp);
 
        if (!v.empty()) {
            //최대 개수 크기만큼 정답에 저장
            int biggest = v[0].second;
 
            //최소 2명 이상 손님으로부터 주문된 조합이어야 하므로
            if (biggest >= 2) {
                for (int i = 0; i < v.size(); i++) {
                    if (v[i].second == biggest) {
                        answer.push_back(v[i].first);
                    }
                    else {
                        break;
                    }
                }
            }
        }
    }
 
    //정렬
    sort(answer.begin(), answer.end());
 
    //반환
    return answer;
}
 

 

브루트포스에 대해 알아볼 수 있는 문제였습니다.

저작자표시

'알고리즘 문제풀이 > 프로그래머스' 카테고리의 다른 글

[C++] 프로그래머스 - 순위 검색  (0) 2021.02.02
[C++] 프로그래머스 - 합승 택시 요금  (0) 2021.01.31
[C++] 프로그래머스 - 신규 아이디 추천  (0) 2021.01.31
[C++] 프로그래머스 - 압축  (0) 2021.01.19
[C++] 프로그래머스 - 방금그곡  (0) 2021.01.19

programmers.co.kr/learn/courses/30/lessons/72410

 

코딩테스트 연습 - 신규 아이디 추천

카카오에 입사한 신입 개발자 네오는 카카오계정개발팀에 배치되어, 카카오 서비스에 가입하는 유저들의 아이디를 생성하는 업무를 담당하게 되었습니다. 네오에게 주어진 첫 업무는 새로 가

programmers.co.kr

<풀이>

1. 새로 가입하는 유저의 아이디를 '7단계의 처리과정'을 거쳐 추천 아이디를 생성한다.

2. 추천 아이디를 반환한다.

 

<해법>

문제를 푸는데 특별한 아이디어가 필요하지 않습니다. '7단계 처리과정'을 정확하게 구현하는 것이 문제의 핵심입니다. 문자열 관련 문제이므로, 문자열 처리 함수를 사용하면 보다 쉽게 구현할 수 있습니다.

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
#include <string>
#include <vector>
 
using namespace std;
 
string solution(string new_id) {
 
    string answer = "";
 
    //step 1
    for (int i = 0; i < new_id.length(); i++) {
        new_id[i] = tolower(new_id[i]);
    }
    
    //step 2
    string str = "";
    for (int i = 0; i < new_id.length(); i++) {
        if ((new_id[i] >= 'a' && new_id[i] <= 'z') || (new_id[i] >= '0' && new_id[i] <= '9') || new_id[i] == '-' || new_id[i] == '_' || new_id[i] == '.') {
            str += new_id[i];
        }
    }
    new_id = str;
 
    //step 3
    while (true) {
        int index = new_id.find("..");
 
        if (index == string::npos) {
            break;
        }
 
        new_id.replace(index, 2, ".");
    }
 
    //step 4
    if (new_id[0] == '.') {
        new_id = new_id.substr(1);
    }
    if (new_id[new_id.length() - 1] == '.') {
        new_id = new_id.substr(0, new_id.length() - 1);
    }
 
    //step 5
    if (new_id == "") {
        new_id = "a";
    }
 
    //step 6
    if (new_id.length() >= 16) {
        new_id = new_id.substr(0, 15);
        if (new_id[14] == '.') {
            new_id = new_id.substr(0, 14);
        }
    }
 
    //step 7
    if (new_id.length() <= 2) {
        char lastChar = new_id[new_id.length() - 1];
        while (true) {
            if (new_id.length() == 3) {
                break;
            }
            new_id += lastChar;
        }
    }
 
    answer = new_id;
 
    return answer;
}
 

 

문자열과 구현에 대해 알아볼 수 있는 문제였습니다.

저작자표시

'알고리즘 문제풀이 > 프로그래머스' 카테고리의 다른 글

[C++] 프로그래머스 - 합승 택시 요금  (0) 2021.01.31
[C++] 프로그래머스 - 메뉴 리뉴얼  (0) 2021.01.31
[C++] 프로그래머스 - 압축  (0) 2021.01.19
[C++] 프로그래머스 - 방금그곡  (0) 2021.01.19
[C++] 프로그래머스 - 다트 게임  (0) 2021.01.16

programmers.co.kr/learn/courses/30/lessons/17684

 

코딩테스트 연습 - [3차] 압축

TOBEORNOTTOBEORTOBEORNOT [20, 15, 2, 5, 15, 18, 14, 15, 20, 27, 29, 31, 36, 30, 32, 34]

programmers.co.kr

<풀이>

1. 문자열을 주어진 LZW 압축 과정에 따라 압축한다.

2. 압축이 모두 완료된 후, 색인 번호들을 반환한다.

 

<해법>

문제를 푸는데 특별한 아이디어가 필요하지 않습니다. 주어진 LZW 압축 과정을 정확하게 구현하는 것이 문제의 핵심이라고 생각합니다. 저는 주어진 압축 과정을 최대한 똑같이 구현하는데 초점을 두어서 구현하였습니다.

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
#include <iostream>
#include <string>
#include <vector>
 
using namespace std;
 
//사전
vector<string> dict;
 
//메시지 안에 같은 단어가 있는지 확인
bool hasSameVocab(string msg, string vocab) {
 
    for (int i = 0; i < vocab.length(); i++) {
        if (vocab[i] != msg[i]) {
            return false;
        }
    }
 
    return true;
}
 
vector<int> solution(string msg) {
    vector<int> answer;
 
    /*
    1. 사전 만들기
    */
    dict.push_back("#");
    for (int i = 0; i < 26; i++) {
        char alpha = 'A' + i;
        dict.push_back(string(1, alpha));
    }
 
    /*
    2번 ~ 5번 반복
    */
    while (true) {
 
        /*
        2. 사전에서 입력과 일치하는 가장 긴 문자열 찾기
        */
        string removeVocab = ""; //지워지는 단어
        int index; //사전 색인
 
        //사전을 모두 탐색
        for (int i = 1; i < dict.size(); i++) {
 
            string vocab = dict[i];
 
            //메시지안에 같은 단어가 있고, 길이가 더 긴 단어 지우기
            if (hasSameVocab(msg, vocab) && vocab.length() > removeVocab.length()) {
                removeVocab = vocab;
                index = i;
            }
        }
 
        /*
        3. 색인 번호 담고, 메시지에서 해당 단어 지우기
        */
        answer.push_back(index);
        msg = msg.substr(removeVocab.length());
 
        /*
        4. 다음 글자가 남아 있을 경우, 다음 글자 포함해서 사전 등록
        */
        if (msg.empty()) {
            break;
        }
        else {
            dict.push_back(removeVocab + msg[0]);
        }
    }
 
    //결과 반환
    return answer;
}
 

 

구현에 대해서 알아볼 수 있는 문제였습니다.

저작자표시

'알고리즘 문제풀이 > 프로그래머스' 카테고리의 다른 글

[C++] 프로그래머스 - 메뉴 리뉴얼  (0) 2021.01.31
[C++] 프로그래머스 - 신규 아이디 추천  (0) 2021.01.31
[C++] 프로그래머스 - 방금그곡  (0) 2021.01.19
[C++] 프로그래머스 - 다트 게임  (0) 2021.01.16
[C++] 프로그래머스 - 비밀지도  (0) 2021.01.16

programmers.co.kr/learn/courses/30/lessons/17683

 

코딩테스트 연습 - [3차] 방금그곡

방금그곡 라디오를 자주 듣는 네오는 라디오에서 방금 나왔던 음악이 무슨 음악인지 궁금해질 때가 많다. 그럴 때 네오는 다음 포털의 '방금그곡' 서비스를 이용하곤 한다. 방금그곡에서는 TV,

programmers.co.kr

<풀이>

1. 주어진 음악 정보 문자열을 분리하여서, 시간동안 재생된 멜로디를 구한다.

2. 시간동안 재생된 멜로디에서 네오가 기억한 멜로디가 있는지 찾는다.

3. 찾아진 음악들을 주어진 기준에 따라 정렬하고, 결과를 반환한다.

 

<해법>

문제를 푸는데 특별한 아이디어가 필요하지 않다고 생각합니다. 문제를 푸는 방법을 코드로 정확히 구현하는 것이 핵심이라고 생각합니다. 저는 문자열을 다루는 함수를 최대한 사용하여서, 구현하였습니다.

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
 
using namespace std;
 
//구조체 : 음악 정보
struct music {
    int index;
    int time;
    string title;
};
 
vector<music> v;
 
//멜로디 변환 함수('#' 없애기)
string changeMelody(string s) {
 
    while (true) {
 
        //'#'을 찾기
        int index = s.find("#");
 
        //'#'이 없으면 종료
        if (index == string::npos) {
            break;
        }
 
        //'#'이 있으면, '#'전에 있는 알파벳 소문자로 변환
        char alpha = tolower(s[index - 1]);
 
        //소문자 알파벳으로 바꾸기(ex. C# -> c)
        s.replace(index - 1, 2, string(1, alpha));
    }
 
    return s;
}
 
//벡터 정렬 기준
bool compare(music a, music b) {
    if (a.time == b.time) {
        return a.index < b.index;
    }
    return a.time > b.time;
}
 
string solution(string m, vector<string> musicinfos) {
 
    string answer = "";
 
    //네오가 기억한 멜로디 -> '#'없앤 멜로디로 변환
    string neoMelody = changeMelody(m);
 
    //주어진 음악 정보 탐색
    for (int i = 0; i < musicinfos.size(); i++) {
 
        /*
        1. 시간 정보 탐색
        */
        string timeInfo = musicinfos[i].substr(0, 11);
 
        int start_time = stoi(timeInfo.substr(0, 2)) * 60 + stoi(timeInfo.substr(3, 2));
        int finish_time = stoi(timeInfo.substr(6, 2)) * 60 + stoi(timeInfo.substr(9, 2));
 
        //총 소요시간
        int time = finish_time - start_time;
 
        /*
        2. 제목, 멜로디 정보 탐색
        */
        string musicInfo = musicinfos[i].substr(12);
 
        //',' 위치 찾기
        int comma_pos = musicInfo.find(',');
 
        //',' 위치를 기준으로 제목, 멜로디 정보 찾기
        string title = musicInfo.substr(0, comma_pos);
        string melody = musicInfo.substr(comma_pos + 1);
 
        /*
        3. 소요시간만큼 진행된 멜로디 구하기
        */
        //멜로디 변환
        melody = changeMelody(melody);
 
        string totalMelody = "";
 
        //멜로디 길이 >= 소요시간
        if (melody.length() >= time) {
            totalMelody = melody.substr(0, time);
        }
        //멜로디 길이 < 소요시간
        else {
 
            //몫만큼 멜로디를 반복
            int repeatCount = time / melody.length();
            for (int j = 0; j < repeatCount; j++) {
                totalMelody += melody;
            }
 
            //나머지 시간, 나머지 멜로디
            int remain = time % melody.length();
            totalMelody += melody.substr(0, remain);
        }
 
        /*
        4. 토탈 멜로디에서 네오 멜로디 찾기
        */
        int index = totalMelody.find(neoMelody);
 
        //멜로디를 찾은 경우 벡터에 저장
        if (index != string::npos) {
            v.push_back({ i, time, title });
        }
    }
 
    //찾은 멜로디 정렬
    sort(v.begin(), v.end(), compare);
 
    //결과 갱신
    if (v.empty()) {
        answer = "(None)";
    }
    else {
        answer = v[0].title;
    }
 
    //결과 반환
    return answer;
}
 

 

문자열과 구현에 대해 알아볼 수 있는 문제였습니다.

저작자표시

'알고리즘 문제풀이 > 프로그래머스' 카테고리의 다른 글

[C++] 프로그래머스 - 신규 아이디 추천  (0) 2021.01.31
[C++] 프로그래머스 - 압축  (0) 2021.01.19
[C++] 프로그래머스 - 다트 게임  (0) 2021.01.16
[C++] 프로그래머스 - 비밀지도  (0) 2021.01.16
[C++] 프로그래머스 - 캐시  (0) 2021.01.11

programmers.co.kr/learn/courses/30/lessons/17682

 

코딩테스트 연습 - [1차] 다트 게임

 

programmers.co.kr

<풀이>

1. 주어진 문자열에서 총 3게임의 점수를 구한다.

2. 각 1게임 마다 점수, 보너스, 옵션을 분리해서 해당 게임의 점수를 계산한다.

3. 3게임 점수의 합을 반환한다.

 

<해법>

특별한 아이디어가 필요없는 문제라고 생각합니다. 문자열을 하나하나 분리해 나가면서, 주어진 방법에 따라 계산하는 방식으로 구현하였습니다. 주어진 점수 계산 방법을 정확하게 구현하는 것이 이 문제의 핵심이라고 생각합니다.

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
#include <iostream>
#include <string>
 
using namespace std;
 
//3게임 점수
int scores[3];
 
int solution(string dartResult) {
    int answer = 0;
 
    //문자열 index
    int index = 0;
 
    //각 게임마다 점수 구하기
    for (int i = 0; i < 3; i++) {
 
        //1. 점수
        int score;
        if (dartResult[index] == '1' && dartResult[index + 1] == '0') { //점수가 10일 경우
            score = 10;
            index++;
        }
        else { //그 외
            score = dartResult[index] - '0';
        }
        scores[i] = score;
        index++;
 
        //2. 보너스
        char bonus;
        switch (dartResult[index]) {
        case 'S': scores[i] = scores[i] * 1; break;
        case 'D': scores[i] = scores[i] * scores[i]; break;
        case 'T': scores[i] = scores[i] * scores[i] * scores[i]; break;    
        }
        index++;
 
        //3. 옵션
        char option;      
        if (dartResult[index] == '*') {
            if (i != 0) { //첫 게임이 아닐 경우
                scores[i - 1] *= 2;
            }
            scores[i] *= 2;
        }
        else if (dartResult[index] == '#') {
            scores[i] *= -1;
        }
        else { //옵션이 없을 경우
            continue;
        }
        index++;
 
    }
 
    //점수 합계
    for (int i = 0; i < 3; i++) {
        answer += scores[i];
    }
 
    //결과 반환
    return answer;
}
 

 

문자열과 구현에 대해 알아볼 수 있는 문제였습니다.

저작자표시

'알고리즘 문제풀이 > 프로그래머스' 카테고리의 다른 글

[C++] 프로그래머스 - 압축  (0) 2021.01.19
[C++] 프로그래머스 - 방금그곡  (0) 2021.01.19
[C++] 프로그래머스 - 비밀지도  (0) 2021.01.16
[C++] 프로그래머스 - 캐시  (0) 2021.01.11
[C++] 프로그래머스 - 프렌즈4블록  (0) 2021.01.07

programmers.co.kr/learn/courses/30/lessons/17681

 

코딩테스트 연습 - [1차] 비밀지도

비밀지도 네오는 평소 프로도가 비상금을 숨겨놓는 장소를 알려줄 비밀지도를 손에 넣었다. 그런데 이 비밀지도는 숫자로 암호화되어 있어 위치를 확인하기 위해서는 암호를 해독해야 한다. 다

programmers.co.kr

<풀이>

1. 두 개의 지도를 합쳐서 지도를 해독한다.

2. 해독한 지도를 반환한다.

 

<해법>

1. 지도를 합치는 방법

=> 저는 비트 연산자를 이용하였습니다. 주어지는 지도가 결국 2진수로 바꿔서 생각해야하는 걸 보면, 바꾸지 않고 비트연산자로 해결해야 겠다는 아이디어를 얻을 수 있었습니다.

 

2. 해독한 지도를 옮기는 방법

=> 비트 연산자를 통해 해독한 지도의 한 줄(10진수)을 알 수 있습니다. 이 숫자를 '#'과 ' '으로 나타내기 위해서는 2진수로 바꿔야 합니다. 따라서, 해당 숫자를 2로 계속 나누어서 '#'과 ' '을 구분하였습니다.

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include <iostream>
#include <string>
#include <vector>
 
using namespace std;
 
vector<string> solution(int n, vector<int> arr1, vector<int> arr2) {
 
    vector<string> answer;
 
    for (int i = 0; i < n; i++) {
 
        //각 라인 숫자 OR(비트 연산자)로 구하기
        int line = arr1[i] | arr2[i];
 
        string str = "";
 
        //10진법 -> 2진법으로 바꾸기
        for (int j = 0; j < n; j++) {
 
            if (line % 2 == 1) {
                str = "#" + str;
            }
            else {
                str = " " + str;
            }
 
            line = line / 2;
        }
 
        //결과 갱신
        answer.push_back(str);
    }
 
    //결과 반환
    return answer;
}
 

 

비트 연산자와 진법에 대해 알아볼 수 있는 문제였습니다.

저작자표시

'알고리즘 문제풀이 > 프로그래머스' 카테고리의 다른 글

[C++] 프로그래머스 - 방금그곡  (0) 2021.01.19
[C++] 프로그래머스 - 다트 게임  (0) 2021.01.16
[C++] 프로그래머스 - 캐시  (0) 2021.01.11
[C++] 프로그래머스 - 프렌즈4블록  (0) 2021.01.07
[C++] 프로그래머스 - 셔틀버스  (0) 2021.01.04

programmers.co.kr/learn/courses/30/lessons/17680

 

코딩테스트 연습 - [1차] 캐시

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, S

programmers.co.kr

<풀이>

1. 각 도시이름을 캐시에 넣는다.

2. LRU 알고리즘에 따라, 캐시를 교체하고 실행시간을 갱신한다.

3. 총 실행시간을 반환한다.

 

<해법>

1. 캐시 구현 방법

=> 저는 deque를 이용하여 캐시를 구현하였습니다. 또한 가장 오래전에 사용된 값은 덱의 맨 앞에, 가장 최근에 사용된 값은 덱의 맨 뒤에 저장하였습니다. 덱을 사용한 이유는, 교체될 덱의 맨 앞의 값을 pop_front() 함수를 써서 쉽게 빼기 위함입니다.

 

2. 캐시 교체 방법

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include <iostream>
#include <string>
#include <vector>
#include <deque>
 
using namespace std;
 
int solution(int cacheSize, vector<string> cities) {
 
    int answer = 0;
 
    //pop_front()를 사용하기 위해 deque를 사용
    deque<string> cache;
 
    for (int i = 0; i < cities.size(); i++) {
 
        //캐시에 넣어야 할 도시
        string city = cities[i];
 
        //대문자 -> 소문자 변환
        for (int j = 0; j < city.length(); j++) {
            city[j] = tolower(city[j]);
        }
 
        //캐시 hit, miss인지 판단
        bool hit = false;
        int index = 0;
        for (index = 0; index < cache.size(); index++) {
            if (cache[index] == city) {
                hit = true;
                break;
            }
        }
 
        //일단 cache 가장 뒤에 넣기(LRU 이므로)
        cache.push_back(city);
 
        //캐시 hit일 경우
        if (hit) {
            //캐시에 있는 기존 데이터 삭제
            cache.erase(cache.begin() + index);
            answer += 1;
        }
        //캐시 miss일 경우
        else {
            //캐시가 넘쳤을 경우, 맨 앞에 있는 가장 오래된 데이터 삭제
            if (cache.size() > cacheSize) {
                cache.pop_front();
            }
            answer += 5;
        }
    }
 
    //결과 반환
    return answer;
}
 

 

구현에 대해 알아볼 수 있는 문제였습니다.

저작자표시

'알고리즘 문제풀이 > 프로그래머스' 카테고리의 다른 글

[C++] 프로그래머스 - 다트 게임  (0) 2021.01.16
[C++] 프로그래머스 - 비밀지도  (0) 2021.01.16
[C++] 프로그래머스 - 프렌즈4블록  (0) 2021.01.07
[C++] 프로그래머스 - 셔틀버스  (0) 2021.01.04
[C++] 프로그래머스 - 뉴스 클러스터링  (0) 2021.01.01

+ Recent posts

티스토리툴바