Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commit5da9133

Browse files
committed
Update
1 parent8fc1e7d commit5da9133

File tree

3 files changed

+143
-0
lines changed

3 files changed

+143
-0
lines changed

‎15/2.cpp

Lines changed: 33 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,33 @@
1+
#include<bits/stdc++.h>
2+
3+
usingnamespacestd;
4+
5+
// 이진 탐색 소스코드 구현(재귀 함수)
6+
intbinarySearch(vector<int>& arr,int start,int end) {
7+
if (start > end)return -1;
8+
int mid = (start + end) /2;
9+
// 고정점을 찾은 경우 중간점 인덱스 반환
10+
if (arr[mid] == mid)return mid;
11+
// 중간점의 값보다 중간점이 작은 경우 왼쪽 확인
12+
elseif (arr[mid] > mid)returnbinarySearch(arr, start, mid -1);
13+
// 중간점의 값보다 중간점이 큰 경우 오른쪽 확인
14+
elsereturnbinarySearch(arr, mid +1, end);
15+
}
16+
17+
int n;
18+
vector<int> arr;
19+
20+
intmain(void) {
21+
cin >> n;
22+
for (int i =0; i < n; i++) {
23+
int x;
24+
cin >> x;
25+
arr.push_back(x);
26+
}
27+
28+
// 이진 탐색(Binary Search) 수행
29+
int index =binarySearch(arr,0, n -1);
30+
31+
// 결과 출력
32+
cout << index <<'\n';
33+
}

‎15/3.cpp

Lines changed: 49 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,49 @@
1+
#include<bits/stdc++.h>
2+
3+
usingnamespacestd;
4+
5+
// 집의 개수(N)와 공유기의 개수(C)
6+
int n, c;
7+
vector<int> arr;
8+
9+
intmain() {
10+
cin >> n >> c;
11+
12+
// 전체 집의 좌표 정보를 입력 받기
13+
for (int i =0; i < n; i++) {
14+
int x;
15+
cin >> x;
16+
arr.push_back(x);
17+
}
18+
// 이진 탐색 수행을 위해 정렬 수행
19+
sort(arr.begin(), arr.end());
20+
21+
int start = arr[1] - arr[0];// 집의 좌표 중에 가장 작은 값
22+
int end = arr[n -1] - arr[0];// 집의 좌표 값 중에서 가장 큰 값
23+
int result =0;
24+
25+
while (start <= end) {
26+
// mid는 가장 인접한 두 공유기 사이의 거리(Gap)을 의미
27+
int mid = (start + end) /2;
28+
int value = arr[0];
29+
int cnt =1;
30+
// 현재의 mid 값을 이용해 공유기를 설치하기
31+
for (int i =1; i < n; i++) {// 앞에서부터 차근차근 설치
32+
if (arr[i] >= value + mid) {
33+
value = arr[i];
34+
cnt +=1;
35+
}
36+
}
37+
// C개 이상의 공유기를 설치할 수 있는 경우, 거리를 증가시키기
38+
if (cnt >= c) {
39+
start = mid +1;
40+
result = mid;// 최적의 결과를 저장
41+
}
42+
// C개 이상의 공유기를 설치할 수 없는 경우, 거리를 감소시키기
43+
else {
44+
end = mid -1;
45+
}
46+
}
47+
48+
cout << result <<'\n';
49+
}

‎15/4.cpp

Lines changed: 61 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,61 @@
1+
#include<bits/stdc++.h>
2+
3+
usingnamespacestd;
4+
5+
// 값이 [left_value, right_value]인 데이터의 개수를 반환하는 함수
6+
intcountByRange(vector<string>& v, string leftValue, string rightValue) {
7+
vector<string>::iterator rightIndex =upper_bound(v.begin(), v.end(), rightValue);
8+
vector<string>::iterator leftIndex =lower_bound(v.begin(), v.end(), leftValue);
9+
return rightIndex - leftIndex;
10+
}
11+
12+
// 문자열 내에서 특정한 문자열을 다른 문자열로 모두 치환하는 함수
13+
stringreplaceAll(string str, string from, string to){
14+
string res = str;
15+
int pos =0;
16+
while((pos = res.find(from, pos)) != string::npos)
17+
{
18+
res.replace(pos, from.size(), to);
19+
pos += to.size();
20+
}
21+
return res;
22+
}
23+
24+
// 모든 단어들을 길이마다 나누어서 저장하기 위한 리스트
25+
vector<string> arr[10001];
26+
// 모든 단어들을 길이마다 나누어서 뒤집어 저장하기 위한 리스트
27+
vector<string> reversed_arr[10001];
28+
29+
vector<int>solution(vector<string> words, vector<string> queries) {
30+
vector<int> answer;
31+
32+
// 모든 단어를 접미사 와일드카드 배열, 접두사 와일드카드 배열에 각각 삽입
33+
for (int i =0; i < words.size(); i++) {
34+
string word = words[i];
35+
arr[word.size()].push_back(word);// 단어를 삽입
36+
reverse(word.begin(), word.end());
37+
reversed_arr[word.size()].push_back(word);// 단어를 뒤집어서 삽입
38+
}
39+
40+
// 이진 탐색을 수행하기 위해 각 단어 리스트 정렬 수행
41+
for (int i =0; i <10001; i++) {
42+
sort(arr[i].begin(), arr[i].end());
43+
sort(reversed_arr[i].begin(), reversed_arr[i].end());
44+
}
45+
46+
// 쿼리를 하나씩 확인하며 처리
47+
for (int i =0; i < queries.size(); i++) {
48+
string q = queries[i];
49+
int res =0;
50+
if (q[0] !='?') {// 접미사에 와일드 카드가 붙은 경우
51+
res =countByRange(arr[q.size()],replaceAll(q,"?","a"),replaceAll(q,"?","z"));
52+
}
53+
else {// 접두사에 와일드 카드가 붙은 경우
54+
reverse(q.begin(), q.end());
55+
res =countByRange(reversed_arr[q.size()],replaceAll(q,"?","a"),replaceAll(q,"?","z"));
56+
}
57+
// 검색된 단어의 개수를 저장
58+
answer.push_back(res);
59+
}
60+
return answer;
61+
}

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp