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 | 31 |
Tags
- c++
- 1편
- LIS #Algorithm #요소추적
- BFS
- 소감
- 서버개발캠프
- Smilegate
- 보석쇼핑
- Union-find
- 스마일게이트
- IBK기업은행 #기업은행 #디지털 #직무 #정리
- BaekJoon
- 투포인터
- 삼성 #코테 #2020상반기 #c++
- 코테
- 코딩테스트
- Algorithm
- 유니온파인드
- 백준
- 알고리즘
- 식단
- 중반부
- 카카오인턴
- 카카오
Archives
- Today
- Total
짱아의 개발 기록장
LeetCode : 5. Longest Palindromic Substring 본문
반응형
팰린드롬 문제인데... 사실 풀이 방법은 여러가지가 있는 듯하다.
DP, Brute Force 등...
하지만, 일단 글쓴이는 Brute Force 방법 밖에는 생각이 나지 않아 이 방법으로 풀이를 했다.
추후, 다양한 방법에 대한 풀이를 update해보겠다.
Brute Force
시간복잡도 : O(n^2)
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
|
// BruteForce
class Solution {
public:
string longestPalindrome(string s) {
string S = "";
int ans = 0;
for(int i=0; i<s.size(); i++){
// 홀수 팰린드롬
int Start = i, End = i;
// 짝수 팰린드롬
int Start2 = i, End2 = i;
// 홀수 팰린드롬
while(Start>0 && End<s.size()-1){
Start--;
End++;
if(s[Start]!=s[End]){
Start++;
End--;
// check = true;
break;
}
}
// 짝수 팰린드롬
Start2 = i, End2 = i;
End2++;
if(End2<s.size()){
if(s[Start2]==s[End2]){
while(Start2>0 && End2<s.size()-1){
Start2--;
End2++;
if(s[Start2]!=s[End2]){
Start2++;
End2--;
break;
}
}
}else{
Start2 = i;
End2 = i;
}
}
// 최종 계산
int temp = End-Start+1;
int temp2 = End2-Start2+1;
if(temp<temp2){
if(ans<temp2){
ans = temp2;
S = s.substr(Start2, temp2);
}
}else{
if(ans<temp){
ans = temp;
S = s.substr(Start, temp);
}
}
}
return S;
}
};
|
cs |
반응형
'Algorithm > LeetCode' 카테고리의 다른 글
LeetCode : 9. Palindrome Number (0) | 2020.12.28 |
---|---|
LeetCode : 7. Reverse Integer (0) | 2020.12.27 |
LeetCode : 6. ZigZag Conversion (0) | 2020.12.27 |
LeetCode: 3. Longest Substring Without Repeating Characters (0) | 2020.12.26 |
LeetCode: 1. Two Sum (0) | 2020.12.26 |
Comments