구름톤 챌린지 DAY6 - 문자열 나누기

 

문제)
1. 문자열 S가 주어진다.
2. 이 문자열을 세부분으로 나누는데, 각 부분은 원래 문자열 순서대로 서로 연결되어 있어야 한다.
3. 모든 경우의 부분집합을 구하고 그것을 사전 순서대로 정렬했을 때,
4. 각 경우의 수의 각 부분집합이 정렬한 부분집합들의 몇번째에 나타날 텐데, 이때 이 '몇'이 점수가 된다.
5. 경우의 수마다 세 부분집합의 점수가 나오는데, 이 합이 최종 점수가 된다. 최대 점수를 구하라.

 

생각해보기)
1. 세 부분으로 나눌 수 있는 모든 경우의 수를 구하고
2. set에 넣고, 정렬
3. 경우마다 점수를 구하고 가장 큰 점수를 구하기

 

쉽게 생각하면,
배열 안에 작대기 두개를 넣는다고 생각하면 된다.
그리고 중복 for문처럼 int i = 0; i++ / int j = i; j++ << 이런식으로 해서 구한 애들을 set에 넣기, 그리고 경우의 수에도 넣기
경우의 수마다 점수 구하면 된다.

 

입력값을 받아준다.

 

세 부분으로 나눈 string은 구조체에 넣을건데, score를 넣어서 최종 점수까지 같이 보관한다.

 

 

각 경우의 수를 모을 vector, 부분집합들을 모두 구해서 중복없이(←set) 넣을 set을 선언 해준다.

그리고 문자열을 돌면서 첫부분, 둘째부분, 마지막 부분을 substr로 나눈다.
처음엔 0부터 i만큼, 다음엔 i부터 j - i 만큼, 다음엔 j부터 마지막부분까지 substr해준다.

이후 vector와 set에 넣어준다.

 

foreach문으로 전체 순회를 하면서 s1의 위치, s2의 위치, s3의 위치를 다 더해서 점수를 구하는 코드다.
(foreach문의 참조값(ps)은 실제 data에 영향을 미치지 않는다는 소리를 어렴풋이 들었다.)
그래서 i값으로 넣어줬는데 이럴줄 알았으면 for문 쓸걸

 

마지막으로 max값을 구하고 그걸 출력한다.

 

 

결과 정답!

 

 

 

오늘은 꽤 애를 먹었던 것 같다.

우선 문제를 이해하기도 좀 빡셌고...
day5와 마찬가지로 파이썬이 많이 보고 싶었다.

그리고 STL에서 find를 하면 iterator가 반환된다는 것도 처음 알아서,
그럴때 어떻게 index값을 끌어낼 수 있는지도 처음 알았다.
(std::distance로 가능하다)

그리고 substr하는 부분..
i와 j값에 따라 나눠줘야 했는데,
이것도 파이썬이 많이 그리웠다.