Notice
Recent Posts
Recent Comments
Link
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 |
Tags
- unity #2d-game
- #유데미 #udemy #웅진씽크빅 #스나이퍼팩토리 #인사이드아웃 #미래내일일경험 #프로젝트캠프 #부트캠프 #react #리액트프로젝트 #프론트엔드개발자양성과정 #개발자교육과정
- firebase #파이어베이스
- flutter #플러터 #분석
- flutter #git
- flutter #깃
- flutter #상태관리
- 로컬저장소 #이름변경
- 플러터 #flutter #restful #rest api
- 백준 #boj #baekjoon
- flutter #todolist
- 비주얼스튜디오 #코드스니펫
- unity #2d-game #minigame #vscode
- 백준 #c++
- 인턴 #프론트엔드 #개발자 #프론트엔드개발자 #취준
- 비주얼 스튜디오 #vs #visual studio
- boj #baekjoon #c++
- baekjoon #백준 #boj
- boj #c++
- 백준 #boj
- VS #비주얼스튜디오
- flutter #app #취준
- 백준
- boj #baekjoon
- flutter #firebase #플러터 #파이어베이스 #연동
- flutter #플러터
- git #unity #깃허브
- baekjoon #boj #c++
- 유데미 #udemy #웅진씽크빅 #스나이퍼팩토리 #인사이드아웃 #미래내일일경험 #프로젝트캠프 #부트캠프 #react #리액트프로젝트 #프론트엔드개발자양성과정 #개발자교육과
- Flutter
Archives
- Today
- Total
cococo-coding
15786번. Send me the money 본문
문제 분석
원본 알파벳과 입력받은 알파벳을 비교하는 문자열 문제이다.
원본 알파벳이 순서대로 다 있다면 true를, 아니라면 false를 출력한다.
알고리즘 설계
이중포문을 이용해 구현했다.
원본을 a , 비교할 알파벳을 b로 설정하고 while문으로 b를 입력받는다.
a는 for(int i=0; i<n; i++)로
b는 for(int j=start; j<b.size(); j++)로 코드를 작성했는데
이때 j의 값 start는 초기값을 0으로 설정해주고, 만약 일치하는 알파벳을 찾으면 그 이후부터 비교해줘야하므로
start =j+1로 넣어준다.
시간 복잡도
while문으로 m개 문자열 입력받기 - n번
이중 포문 - n제곱
-> o(n3) 가 나왔다.
실제 코테에서는 쓰기 힘들 코드이다...
다른 방법으로도 풀어봐야겠다.
코드
#include <iostream>
#include <vector>
using namespace std;
/*
1.원본 알파벳 수n 포스트잇개수m 입력받기
2. 포스트잇 애들 입력받기
3. 가능성 여부 판단
4. 출력하기
*/
int main() {
//1
int n, m;
cin >> n >> m;
//2
string a, b;
cin >> a;
while(m--) {
int cnt = 0;
cin >> b;
int start = 0; //j값 시작 조절하기
for (int i = 0; i < n; i++) {
for (int j = start; j < b.size(); j++) {
if (a[i] == b[j]) {
cnt++;
//cout << "J: " << j << " post[j]: " << post[j] << '\n';
start = j + 1; //j값 조절 2
break;
}
if (cnt == n)break;
}
}
if (cnt == a.size()) cout << "true" << '\n';
else cout << "false" << '\n';
}
return 0;
}
느낀 점
이중포문에서 초기값을 항상 0으로만 쓰는 형태에 익숙했는데
이 문제에서는 한번 확인한 문자는 지나치고, 그 다음 문자부터 또다시 비교해야하므로 이 부분을 start 변수로 구현해본것이 생각의 전환이 되었다.
시간 복잡도로 따지면 좋은 코드는 아니지만, 혼자 힘으로 풀었다는 것에 의의를 둔다.
find() 함수로도 다시 풀어보고 코드를 추가해봐야겠다.
'[BOJ] 코드 모음 > C++_알고리즘' 카테고리의 다른 글
1789번. 수들의 합 (1) | 2024.02.06 |
---|---|
[C++ 풀이] 11034. 캥거루 세마리2 (1) | 2024.02.01 |
[C++ 풀이] 14659번. 한조서열정리하고옴ㅋㅋ (0) | 2024.02.01 |
[C++ 풀이] 2810번. 컵홀더 (1) | 2024.01.30 |
[C++ 풀이] 2864번. 5와 6의 차이 (0) | 2024.01.28 |