[C++] 시간 초과 꿀팁, binary search, 벡터 원소 삭제, set 자료형, map 자료형

main에 최적화를 위한 두 줄 추가하고 시작하면 시간 초과 잘 안 난다

#include <iostream>
using namespace std;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
}

 

벡터 내에 특정 element 있는지 이진 탐색으로 확인하는 방법

- lower_bound를 사용해 삽입될 위치 포인터를 리턴받은다음 v.end() 아니고 해당 주소에 element 있는지 확인하면됨

    sort(v.begin(), v.end());
    
    for(int i=0; i<M; i++) {
        cin >> s;
        vector<string>::iterator it = lower_bound(v.begin(), v.end(), s);
        if(it != v.end() && *it == s) cnt++;
    }

python bisect.bisect_left()도 마찬가지

- 리턴받은 포인터가 배열의 끝이 아닌지, 그리고 해당 위치에 찾는 값이 들어가있는지 확인하면 됨

for _ in range(m):
    tmp = input()
    pos = bisect.bisect_left(arr1, tmp)
    if pos != n and arr1[pos] == tmp:
        cnt += 1

 

벡터 내의 특정 element 삭제하기

- <vector> 헤더와 <algorithm> 헤더 추가 (remove 함수 사용 위해)

- remove 함수는 일치하는 element들을 맨 끝으로 보내고 그 포인터 리턴한다, erase를 통해 삭제한다

v.erase(remove(v.begin(), v.end(), name), v.end());

 

set 자료형

- #include <set> 필요

- 균형 이진트리로 구성되어있으며, key 값 중복이 안되며, insert 시 자동으로 오름차순 정렬 된다

=> 원소를 꺼내고, 삭제하고, 접근하는데 효율적인듯 (vector로는 시간초과 떠도 set은 성공함)

 

- begin(), end(), rbegin(), rend() 를 통해 정방향/역방향 순회가 가능하다

// for(auto it=s.begin(); it!=s.end(); it++) 
for(auto it=s.rbegin(); it!=s.rend(); it++) {
    cout << *it << "\n";
}

- count(k): 원소 개수 반환, insert(k): 삽입, erase(iter): iter 가리키는 원소 제거, find(k): k를 가리키는 반복자 반환

https://blockdmask.tistory.com/79

 

in python?

- set() 자료형은 순서가 없고 중복을 허용하지 않는다, 인덱스 이용한 값 참조 힘듦

- remove() 사용 시 해당 원소 없으면 keyerror 발생, discard() 사용 시 해당 원소 없으면 pass

- 순서 정렬 원하면 list나 tuple로 변환 후 정렬하는 것 추

s = set()

for _ in range(n):
    name, status = input().split()
    if status=="enter":
        s.add(name)
    else: # leave
        s.discard(name)
        
 lst = sorted(list(s), reverse=True)

 

map 자료형

- 노드 기반으로 이루어진 균형 이진 트리 구조, set처럼 삽입 되면서 자동으로 정렬이 됨

- key 값 중복 불가능

- m[key] 통해 value 직접 접근 및 수정 가능

- begin(), end(), rbegin(), rend(), insert(), count(), find() 등의 멤버함수 존재

map <string, int> m;

for(int i=1; i<=N; i++) {
    cin >> uinput;
    m.insert({uinput, i});
}