set/map 문제풀이 + 팀대회

1. 베스트 셀러

 

key값을 string 

value 값을 int로해서

문자열 몇개나왔는지 count 해줘서

제일 많이나온 key값에 대해서 저장해주고,

만약 똑같은 애가 여러개면

사전순으로 정렬해서 출력

compare는 왼,오를 비교해주는, 왼쪽이 사전순으로 빠르면 음수, 느리면 양수(1), 같다면 0출력해야함.

s;m[s]는?

m[s] ++를 하면 뭐라고하는거지..

 

 

 

2. 근무지옥

행 -> 시간

열 -> 요일

근무를 얼마나 하는지 맵에 저장해준다음에,

근무를 제일 많이 서는 애랑 안서는애랑 12시간 이내 차이 -> Yes ,아니면 No

 

 

맵 선언 잊지말고

 

3. 가희와 키워드

n개의 문자가 주어진다.

m개만큼 줄이 주어졌을때 

주어진 문자를 지워버린 다음에 한줄씩 처리했을때 

메모장에 문자열이 몇개 남아있나?

입력에 쉼표가 들어있어서 전처리 과정이 필요함.

중복으로 들어오는것에 대해서도 주의해야한다.

키워드의 길이가 10이라서

10^6만큼만 

문자열의 길이만큼 돌아야하는걸 생각을해야한다.

 (안해도 풀리기는 함 근데, 알고 )

 

 

 

4. 화살을 쏘자

일직선상에 제일 풍선이 많이 놓여있을 경우

맵의 키 값을 페어로 만들었음

 

 

다른방법

cmath라는 헤더파일 안에  arctant 가 있다. (탄젠트 역함수 -> 기울기값)

atan2(기울기값) *(180/3.141592) = 각도 나온다.

 

또 다른방법

x,y 가 주어졌을때 두 값에 절댓값을 씌워준뒤, gcd값을 구해서 (i라고 하자)

x/i,y/i 를 해주면 최대 공약수로 나눴기 때문에

같은 일직선상에 위치해있다면, 같은 직선에 있는 모든 점들은 x/i,y/i 와 같은 점들을 가지게 될것이다.

이걸 key로 사용해서 value값중에서 출력을 해줘도 되는 문제임

 

 

 

5. 무한 수열

 

A0 = 1,

Ai = ~ (써있음)

N,P,Q가 주어지고, An을 구하는 문제

 

N값이 10^12 승으로 굉장히 크다.

N이 크지만 않으면 백트래킹으로 A0=1 이라는 값을 ,

0보다 같다면 1을 반환하는 식으로 재귀로 짤 수 있다.

근데 N이 크기때문에 배열로 만들면굉장히 크고,

메모리 초과가 나오게 될 것이다.

N이라는 int값을 key값으로 맵을 만들게되면,

재귀를 통해 쉽게 구할 수 있으며

log(10^12)로 변함

template 는 int라고 보면된다.

 

---

팀대회

아우 또 졸려..

아 개빡쳐 다날라감

1.

2.

3. mst

4.

 

5. 는 어려움