문제
문자열이 주어졌을 때 같은 알파벳이 두 번 이상 사용되지 않는 가장 긴 Substring을 구하시오.
Substring이란?
우선 Substring이란, 해당 String을 슬라이싱해서 나올 수 있는 String을 뜻한다.
즉, "Apple"의 Substring은
A, p, p, l, e,
Ap, pp, pl, le,
App, ppl, ple,
Appl, pple,
Apple
이렇게 총 1+2+3+4+5 = 15개이다.
즉 길이가 N인 String에서 나올 수 있는 Substring의 갯수는
N * (N+1) /2 개이다.
Table이란?
Key, Value로 쌍을 이뤄 데이터를 저장하는 자료구조.
Key값을 통한 Random Access에 O(1)의 시간이 소요된다.
두 가지 풀이법
접근1) 포인트 두 개 사용 (비효율적인 풀이)
1. a, c를 가리키는 두 포인터를 선언한다.
>> 공간 O(1)소모
2. 두 포인터는 2중 루프를 돌면서 가능한 모든 Substring들을 구하고 저장한다.
>> 시간 O(N^2) 소요, 공간 O(N^2) 소모
3. 이렇게 구한 Substring들 중에서 for문을 통해 가장 길이가 큰 Substring을 구한다.
>> 시간 O(N) 소요
접근2) 포인터 두 개 사용 + 테이블(key-value) 사용 (권장되는 풀이)
1. a를 가리키는 포인터 ptr1, ptr2를 선언한다.
정수값을 저장하는 maxLength, startIndex, endIndex 변수들을 선언한다.
>> 공간 O(1) 소모
2. 주어진 string 안에 들어있는 모든 알파벳을 key로 가지는 테이블을 선언하고, value값을 -1로 초기화한다.
ex) { a : -1, b : -1, c : -1, d : -1, e : -1}
>> 알파벳의 경우 아무리 많은 알파벳이 사용되었다고 해도 26개를 넘지 않으므로 O(1)의 공간을 소모한다.
3. ptr2를 인덱스를 1씩 증가시키며 이동시킨다.
이동하고 나면 ptr2가 가리키는 알파벳을 테이블에서 찾고, 값이 -1인지 확인한다.
(값이 -1이라는 것은 아직 그 알파벳이 한 번도 발견되지 않았음을 의미한다.)
A. 값이 -1이라면 value값을 알파벳의 index값으로 설정한다.
예를 들어 ptr2가 한 칸 이동해 index 1의 위치에 있는 b를 가리키게 되었다면, 테이블을 다음과 같이 변경한다.
{ a : -1, b : 1, c: -1, d : -1, e : -1}
테이블의 Random Access는 O(1)의 Time Complexity를 지원하므로 이 과정은 O(1) 만큼 소요된다.
B. 값이 -1이 아니라면 ptr1을 (알파벳의 index값 + 1)의 위치로 이동시킨다. 또 value값을 알파벳의 index값으로 설정한다.
이때 주의해야 할 점은 ptr1은 오직 인덱스가 증가하는 방향으로만 이동해야 한다는 점이다. 따라서 값이 -1이 아니라도 ptr1을 뒤로 이동해서는 안된다. 중복이 발생할 수 있기 때문이다.
위 문제를 예시로 들어보겠다.
< 올바른 예 >
ptr1: a, ptr2: a (연산 시작)
ptr1: a, ptr2: b
ptr1: a, ptr2: c
ptr1: a, ptr2: d
ptr1: a, ptr2: e
ptr1: a, ptr2: c (c != -1 확인) -> ptr1: d, ptr2: c
ptr1: d, ptr2: a (a != -1 확인, 그러나 a의 인덱스는 0이므로, ptr1을 뒤로 이동시키지 않는다.) -> ptr1: d, ptr2: a
연산 종료, startIndex = 0, endIndex = 4, substring = abcde
>> 정답
< 잘못된 예 >
ptr1: a, ptr2: a (연산 시작)
ptr1: a, ptr2: b
ptr1: a, ptr2: c
ptr1: a, ptr2: d
ptr1: a, ptr2: e
ptr1: a, ptr2: c (c != -1 확인) -> ptr1: d, ptr2: c
ptr1: d, ptr2: a (a != -1 확인, 여기서 만약 ptr1을 (a의 인덱스 + 1)로 이동시킨다면?) -> ptr1: b, ptr2: a
연산 종료, startIndex = 1, endIndex = 6, substring = bcdeca
>>잘못된 결과 발생
4. 이렇게 테이블 값을 변경했다면 그에 맞게 startIndex와 endIndex값을 변경하고, endIndex - startIndex값이 maxLength보다 크다면 maxLength값도 변경해준다.
5. 위 과정을 반복하며 ptr2가 string의 끝에 도달하면 멈춘다.
>> 총 시간 O(N) 소요
코드
접근2의 방식을 사용한 풀이 (C++11로 작성했습니다)
코드:
#include <iostream>
#include <map>
int main()
{
// String 선언, 초기화
int arrLen = 7;
char* strArr = new char[arrLen] { 'a', 'b', 'c', 'd', 'e', 'c', 'a' };
// 포인터 2개 선언 후 string[0]으로 초기화
char* ptr1;
char* ptr2;
ptr1 = &strArr[0];
ptr2 = &strArr[0];
// 변수 선언
int maxLength = 1;
int startIndex = 0;
int endIndex = 0;
int tempStartIndex;// tempStartIndex와 tempEndIndex는 구조상 반드시 필요하지는 않은 변수들이지만 코드의 명확성을 위해 추가했다
int tempEndIndex;
// 테이블 선언
std::map<char, int> table;
table.insert(std::pair<char, int>('a', -1));
table.insert(std::pair<char, int>('b', -1));
table.insert(std::pair<char, int>('c', -1));
table.insert(std::pair<char, int>('d', -1));
table.insert(std::pair<char, int>('e', -1));
// TimeComplexity O(N)
for (int i = 0; i < arrLen; i++)// ptr2가 index를 1씩 늘려나간다
{
ptr2 = &strArr[i];
// ptr2가 가리키는 알파벳의 value값이 -1이라면 value값을 index값으로 변경한다
if (table[*ptr2] == -1)
{
table[*ptr2] = i;
}
else // ptr2가 가리키는 알파벳의 value값이 -1이 아니라면 조건에 따라 ptr1을 (value + 1)을 가리키도록 변경하고 value값을 index값으로 변경한다.
{
// ptr1을 뒤로 되돌리는 일이 발생하지 않도록 조건을 걸어둔다.
if (table[*ptr2] + 1 >= table[*ptr1])
{
ptr1 = &strArr[table[*ptr2] + 1];
}
table[*ptr2] = i;
}
// 최댓값 갱신
tempStartIndex = table[*ptr1];
tempEndIndex = table[*ptr2];
if (tempEndIndex - tempStartIndex + 1 > maxLength)
{
maxLength = tempEndIndex - tempStartIndex + 1;
startIndex = tempStartIndex;
endIndex = tempEndIndex;
}
}
// 결과 프린트
std::cout << "startIndex: " << startIndex << " endIndex: " << endIndex << " maxLength: " << maxLength << std::endl;
for (int i = startIndex; i <= endIndex; i++)
{
std::cout << strArr[i];
}
delete[] strArr;
}결과:
'software engineering > PS' 카테고리의 다른 글
| boj 3197 (0) | 2021.01.22 |
|---|---|
| 0/1 Knapsack problem (0) | 2021.01.20 |
| Stack을 활용한 Remove Adjacent Duplicates(연속된 중복 제거) 문제 (0) | 2020.12.27 |
| Stack을 활용한 괄호 문제 (0) | 2020.12.24 |
| 같은 알파벳이 겹치지 않도록 문자열 재배열하기 (0) | 2020.12.23 |