정적 프로퍼티, 메서드

  • 정적은 static을 의미, 자바에서 클래스에서 static으로 정의할 경우 인스턴스 생성하지 않아도 사용 가능한 개념과 유사
  • 생성자 함수로 인스턴스 생성하지 않아도 사용할수 있는 프로퍼티, 메서드
  • 생성자 함수도 객체이므로, 프로퍼티, 메서드 소유 가능
  • 단, 생성자 함수로 생성한 인스턴스로는 사용 불가
  • 예시 : Object
    • Object.create : Object 생성자 함수의 정적 메서드
    • Object 상속받은 객체에서는 호출 불가능
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
예시
// 생성자 함수
function Person(name) {
    this.name = name;
}
 
// 정적 프로퍼티, 메서드 추가
Person.staticProp = ‘static prop’;
Person.staticMethod = function() {
    console.log(‘static method’);
}
 
Person.staticProp(); // static prop
Person.staticMethod(); // static method
 
// 인스턴스에서 호출
const me = new Person(‘Han’);
me.staticProp(); // Error
 
 
cs

출처

  • 모던 자바스크립트 Deep Dive, Ch 19

'자바스크립트' 카테고리의 다른 글

[자바스크립트] __proto__  (0) 2021.02.07
[자바스크립트] 직접상속 Object.create  (0) 2021.02.07
[자바스크립트] 생성자 함수  (0) 2021.02.05
[자바스크립트] this  (0) 2021.02.05
[자바스크립트] 내부 슬롯, 내부 메서드  (0) 2021.02.05

문제링크 : https://www.acmicpc.net/problem/5052

문제 접근

시간복잡도 계산

  • 모든 문자열에 대해 순회 N
    • 문자열에 대해 한글자 한글자 순회 : M
    • O(NM) : 50 * 1e4 : 5e5

코드

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
#include <iostream>
#include <queue>
#include <vector>
 
using namespace std;
 
// 각 노드의 인접 리스트
vector<int> adj[32010];
// 각 노드에 들어오는 간선 개수
int indeg[32010];
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    int N,M; cin >> N >> M;
    for(int i=0; i<M; i++) {
        int a,b; cin >> a >> b;
        // 인접한 간선 추가
        adj[a].push_back(b);
        // 들어오는 간선의 개수 증가
        indeg[b]++;
        
    }
    
    queue<int> q;
    for(int i=1; i<=N; i++) {
        if(indeg[i]==0) q.push(i);
    }
    
    vector<int> rs;
    while(!q.empty()) {
        int eq = q.front(); q.pop();
        rs.push_back(eq);
        
        for(int x : adj[eq]) {
            // 들어오는 간선의 개수 감소
            indeg[x]--;
            // 만약 들어오는 간선의 개수가 0일때 큐에 추가
            if(indeg[x] == 0) q.push(x);
        }
    }
    
    for(int ers : rs) cout << ers << ' ';
    
    return 0;
}
 
cs

문제유형

  • TRIE

'알고리즘 > 백준' 카테고리의 다른 글

백준 1197 최소 스패닝 트리 쉬운 풀이(C++/CPP)  (0) 2021.02.08
백준 1786 찾기 쉬운 풀이(C++/CPP)  (0) 2021.02.07
백준 2252 줄 세우기 쉬운 풀이(C++/CPP)  (0) 2021.02.07
백준 2805 나무 자르기 쉬운 풀이(C++/CPP)  (0) 2021.02.07
백준 14226 이모티콘  (0) 2021.02.06

문제 정의

  • 접두사를 확인하는 문제
    • 접미사도 확인 가능 : 글자를 거꾸로 뒤집으면 됨

문제 접근

  • 각 문자열을 TRIE 배열에 저장하면서 문제 해결
    • TRIE 배열
      • 각 문자에 해당하는 노드가 저장되는 곳
      • 노드 포함해야하는 것
        • fin : 이 노드에서 문자열이 끝난적이 있음
        • child : 문자열중 이 노드의 다음 글자의 위치(TRIE 배열 중 인덱스)
  • TRIE 배열을 활용해서 문제 해결 가능
    • 접두사가 있는지 확인하는 문제
      • 이미 접두사가 있었는지 확인 : 각 노드의 fin 확인
      • 현재의 문자열이 접두사가 되는경우 : 문자열의 마지막 글자가 이미 있을떄

시간복잡도

  • 모든 문자열에 대해 순회 N
  • 문자열에 대해 한글자 한글자 순회 : M
  • O(NM)

대표예제 : 백준 5052 전화번호 목록

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
#include <iostream>
#include <string>
#include <vector>
 
using namespace std;
// 각 문자가 들어갈 node 정의
struct node {
    // 문자열이 끝날경우 fin = true;
    bool fin;
    // 다음 문자의 위치(TRIE 안에서의 인덱스)
    // 현재 문제는 숫자이므로 10개만, 알파벳이면 26개
    int child[10];
    
    // 초기화
    node() {
        fin = false;
        // child값이 -1일 경우, 다음 글자가 없음
        for(int i=0; i<10; i++) child[i] = -1;
    }
};
 
vector<node> trie;
bool sw;
 
// s : trie에 넣을 문자열
// idx : 문자열중 현재 글자의 위치 (인덱스)
// nodi : 삽입할 노드의 인덱스, 처음 시작은 0부터 시작
void insert(string& s, int idx, int nodi) {
    if(idx==s.size()) {
        // 마지막 글자일경우
        trie[nodi].fin = true;
        return;
    }
    
    // 현재 노드에서의 글자
    int cur = s[idx] -'0';
    
    // 이미 접두사가 있을경우
    if(trie[nodi].fin == true) sw = 1;
    // 내가 접두사가 될경우, 문자열의 마지막 글자인 동시에 trie에는 다음 글자가 있을때
    if(idx == s.size()-1 && trie[nodi].child[cur] != -1) sw = 1;
    
    // 문자열의 다음 글자가 없을경우 노드 추가
    if(trie[nodi].child[cur] == -1) {
        trie[nodi].child[cur] = trie.size();
        trie.push_back(node());
    }
    
    // 다음 글자를 TRIE에 삽입
    insert(s,idx+1,trie[nodi].child[cur]);
}
 
int main() {
    int t; cin >> t;
    while(t--) {
        sw =false;
        trie.clear();
        
        // TRIE 배열에 처음 시작하는 빈 노드를 넣어줘야함
        trie.push_back(node());
        int N; cin >> N;
        while(N--) {
            string s; cin >> s;
            // 각 문자열을 trie에 삽입
            insert(s,0,0);
        }
        
        if(sw) cout << "NO\n";
        else cout << "YES\n";
    }
    return 0;
}
 
cs

'알고리즘 > 개념' 카테고리의 다른 글

[알고리즘] Dijkstra, 다익스트라 알고리즘  (0) 2021.02.14
[알고리즘] Floyd Warshall, 플로이드 와샬 알고리즘  (0) 2021.02.08
[알고리즘] Minimum Spanning Tree, 최소 스패닝 트리  (0) 2021.02.08
[알고리즘] 문자열 KMP, Rabin Karp  (0) 2021.02.07
[알고리즘] Topological Sort, 위상정렬  (0) 2021.02.07

+ Recent posts

티스토리툴바