짬뽕얼큰하게의 맨땅에 헤딩 :: 'Programmers' 태그의 글 목록

프로그래머스 (PROGRAMMERS) 문자열압축

알고리즘 2021. 1. 18. 23:26

실수: 문자열의 길이가 1일경우를 생각하지 못해서 시간을 낭비.

시간 복잡도: O(N^2 +알파..?)


시간복잡도 계산이 잘 안된다. 

12번 라인과 17번 라인이 서로 의존적이다. 

n이1인경우 strncmp는 거의 연산비용이 들지 않게되고...

그렇다고 n을 N으로 키우면... 중간의 while(right < N) 반복문 접근수가 줄어든다.

잘 모르겠다.


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
#include <string>
#include <vector>
#include <iostream>
#include <string.h>
 
using namespace std;
 
int solution(string s) {
    int answer = 1001;
    int N = s.length();
    if (N == 1) return 1;
    for (int n = 1; n < N; n++) {
        string str = "";
        int left = 0, right = n;
        int equalCnt = 1;
        while(right < N){
            if (strncmp(&s[left], &s[right], n) == 0) {
                equalCnt++;
            }
            else {
                if (equalCnt == 1) {
                    str = str + s.substr(left, n);
                }
                else {
                    str = str + to_string(equalCnt) + s.substr(left, n);
                }
                left = right;
                equalCnt = 1;
            }
            right += n;
        }
        if (equalCnt == 1) {
            str = str + s.substr(left, n);
        }
        else {
            str = str + to_string(equalCnt) + s.substr(left, n);
        }
 
        if (answer > str.length()) {
            answer = str.length();
        }
        //std::cout << str << endl;
    }
    return answer;
}
 
cs


'알고리즘' 카테고리의 다른 글

Making A Large Island  (0) 2025.02.02
Redundant Connection  (0) 2025.02.01
프로그래머스 (Programmers) 입국심사  (0) 2021.01.12
프로그래머스 (Programmers) 가장 먼 노드  (0) 2021.01.11
프로그래머스 (Programmers) 섬 연결하기  (0) 2021.01.11
블로그 이미지

짬뽕얼큰하게

,

프로그래머스 (PROGRAMMERS) 오픈채팅방

카테고리 없음 2021. 1. 13. 23:34

처음 for문을 돌면서 id에 매칭되는 최종 닉네임을 구했고.

두번째 for문을 돌면서 enter, leave에 대한 문자열을 생성했다.

map을 사용하여 id에 대한 중복검사를 안해도 되지만..

C++ map 사용법이 익숙하지 않아서... hash를 사용했다.

hash 함수는 소문자 or 대문자 문자열만 있었다면 27법을 사용했겠지만.. 

대소문자+숫자까지 있기때문에 대충 곱하기로 구했다. 

해쉬 함수는 큰 의미가 있지 않으니, 참고하지 않았으면 좋겠다.



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
#include <iostream>
#include <string>
#include <string.h>
#include <vector>
#include <sstream>
#define HASH_TABLE_MAX 3000
using namespace std;
 
char* parseStr[100000][3];
struct _user {
    char *id;
    char *nickname;
};
_user user[100000];
vector<int> hashTable[HASH_TABLE_MAX];
int getHash(char* name) {
    unsigned int hash = 31;
    for (int i = 0; name[i]; i++) {
        hash *= name[i];
    }
    return hash % HASH_TABLE_MAX;
}
 
int userCnt = 0;
int add(char* id, char* nickname) {
    int hashValue = getHash(id);
    for (int i = 0; i < hashTable[hashValue].size(); i++) {
        int idx = hashTable[hashValue][i];
        if (strcmp(user[idx].id, id) == 0) {
            user[idx].nickname = nickname;
            return idx;
        }
    }
    user[userCnt].id = id;
    hashTable[hashValue].push_back(userCnt);
    user[userCnt].nickname = nickname;
    userCnt++;
    return userCnt - 1;
}
int get(char* id) {
    int hashValue = getHash(id);
    for (int i = 0; i < hashTable[hashValue].size(); i++) {
        int idx = hashTable[hashValue][i];
        if (strcmp(user[idx].id, id) == 0) {
            return idx;
        }
    }
}
vector<string> solution(vector<string> record) {
    vector<string> answer;
    int actionCnt = record.size();
    for (int i = 0; i < actionCnt; i++) {
        int strIdx = 0;
        parseStr[i][strIdx] = &record[i][strIdx];
        strIdx++;
        for (int j = 0; record[i][j]; j++) {
            if (record[i][j] == ' ') {
                record[i][j] = 0;
                parseStr[i][strIdx] = &record[i][j + 1];
                strIdx++;
            }
        }
        if (*parseStr[i][0] == 'E') {
            add(parseStr[i][1], parseStr[i][2]);
        }
        else if (*parseStr[i][0] == 'C') {
            add(parseStr[i][1], parseStr[i][2]);
        }
 
        //printf("%s %s %s\n", parseStr[i][0], parseStr[i][1], parseStr[i][2]);
    }
    for (int i = 0; i < actionCnt; i++) {
        if (*parseStr[i][0] == 'E') {
            int idx = get(parseStr[i][1]);
            answer.push_back(string(user[idx].nickname) + "님이 들어왔습니다.");
        }
        else if (*parseStr[i][0] == 'L') {
            int idx = get(parseStr[i][1]);
            answer.push_back(string(user[idx].nickname) + "님이 나갔습니다.");
        }
    }
 
    return answer;
}
cs
블로그 이미지

짬뽕얼큰하게

,

프로그래머스 (Programmers) 입국심사

알고리즘 2021. 1. 12. 00:19

입국심사.

처음엔 당황했지만.. 생각해보니 풀 수 있었다.

이분탐색 문제라는걸 몰랐으면 더 힘들었을 것 같다.



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
#include <string>
#include <vector>
 
using namespace std;
 
long long solution(int n, vector<int> times) {
    long long answer = 1000000000000000000;
    long long l = 1;
    long long r = answer;
 
    while (l <= r) {
        long long mid = (l + r) / 2;
        int simsa = times.size();
        long long person = 0;
        for (int i = 0; i < simsa; i++) {
            person += mid / times[i];
        }
        if (person >= n) {
            answer = mid;
            r = mid - 1;
        }
        else {
            l = mid + 1;
        }
    }
 
    return answer;
}
cs

'알고리즘' 카테고리의 다른 글

Redundant Connection  (0) 2025.02.01
프로그래머스 (PROGRAMMERS) 문자열압축  (0) 2021.01.18
프로그래머스 (Programmers) 가장 먼 노드  (0) 2021.01.11
프로그래머스 (Programmers) 섬 연결하기  (0) 2021.01.11
프로그래머스(programmers) N으로 표현  (0) 2021.01.11
블로그 이미지

짬뽕얼큰하게

,

프로그래머스 (Programmers) 가장 먼 노드

알고리즘 2021. 1. 11. 23:44

BFS 이용해서 풀었다.



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
#include <string>
#include <vector>
#include <queue>
 
using namespace std;
bool visited[20001];
vector<int> link[20001];
struct _pair {
    int num;
    int cnt;
};
queue<_pair> que;
int maxCnt = 0;
int solution(int n, vector<vector<int>> edge) {
    int answer = -1;
    int edgeN = edge.size();
    for (int i = 0; i < edgeN; i++) {
        int a = edge[i][0];
        int b = edge[i][1];
        link[a].push_back(b);
        link[b].push_back(a);
    }
    visited[1] = true;
    que.push({ 1, 0 });
    while (!que.empty()) {
        _pair pair = que.front();
        que.pop();
        if (pair.cnt > maxCnt) {
            maxCnt = pair.cnt;
            answer = 1;
        }
        else if (pair.cnt == maxCnt) {
            answer++;
        }
        for (int i = 0; i < link[pair.num].size(); i++) {
            int a = pair.num;
            int b = link[a][i];
            if (visited[b]) continue;
            visited[b] = true;
            que.push({ b,pair.cnt + 1 });
        }
    }
 
    return answer;
}
cs

'알고리즘' 카테고리의 다른 글

프로그래머스 (PROGRAMMERS) 문자열압축  (0) 2021.01.18
프로그래머스 (Programmers) 입국심사  (0) 2021.01.12
프로그래머스 (Programmers) 섬 연결하기  (0) 2021.01.11
프로그래머스(programmers) N으로 표현  (0) 2021.01.11
[논리 오류] 한번의 for문으로 여러 데이터의 hash값을 처리시 한 실수  (0) 2020.12.28
블로그 이미지

짬뽕얼큰하게

,

프로그래머스 (Programmers) 섬 연결하기

알고리즘 2021. 1. 11. 23:06

크루스칼로 풀었다.

/**

실수:

disjoint함수의 두 a,b값이 다른 경우 uf[disjoint(a)] = disjoint(b); 최상위 번호를 찾아 넣어줘야하는데...

uf[a] = disjoint(b) 로 넣어주었다.. ㅠㅠ

이렇게 되면 두집합이 합쳐질때 최상위번호가 바뀌는게 아니라.. 중간쯔음에서 바뀌기 때문에... 집합 전체가 합쳐지지 않는다.

오히려 이건 가능하다.

uf[disjoint(a)] = b

b는 최상위가 아니여도... a의 최상위를 b로 바꿔주었기때문에.. disjoint 함수를 부르게되면 최상위 번호로 갱신된다.


**/



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
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
bool cmp(const vector<int>& a, const vector<int>& b) {
    return a[2] < b[2];
}
int uf[100];
int disjoint(int x) {
    if (uf[x] == x) return x;
    return uf[x] = disjoint(uf[x]);
}
int solution(int n, vector<vector<int>> costs) {
    int answer = 0;
    for (int i = 0; i < n; i++) {
        uf[i] = i;
    }
 
    int row = costs.size();
 
    sort(costs.begin(), costs.end(), &cmp);
 
    for (int i = 0; i < row; i++) {
        int a = costs[i][0];
        int b = costs[i][1];
        int cost = costs[i][2];
        if (disjoint(a) != disjoint(b)) {
            uf[disjoint(a)] = disjoint(b);
            answer += cost;
        }
        else {
            continue;
        }
    }
 
    return answer;
}
 
cs


'알고리즘' 카테고리의 다른 글

프로그래머스 (Programmers) 입국심사  (0) 2021.01.12
프로그래머스 (Programmers) 가장 먼 노드  (0) 2021.01.11
프로그래머스(programmers) N으로 표현  (0) 2021.01.11
[논리 오류] 한번의 for문으로 여러 데이터의 hash값을 처리시 한 실수  (0) 2020.12.28
Visual Studio Code (VS Code) PS용 환경설정  (1) 2019.02.07
블로그 이미지

짬뽕얼큰하게

,

공지사항

글 보관함

달력

«   2025/04   »
일 월 화 수 목 금 토
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

티스토리툴바