1-K 질문

인프런 커뮤니티 질문&답변

작성한 질문수

10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트

1-K

해결된 질문

작성

292

- 학습 관련 질문을 남겨주세요. 상세히 작성하면 더 좋아요!
- 먼저 유사한 질문이 있었는지 검색해보세요.
- 서로 예의를 지키며 존중하는 문화를 만들어가요.
- 잠깐! 인프런 서비스 운영 관련 문의는 1:1 문의하기를 이용해주세요.

안녕하세요. 강사님.

이런 느낌으로 팰린드롬 변환을 구현해봤습니다.

사실 문자열 최대길이가 50이라서 시간복잡도 문제는 없을거라 생각하는데요.
삽입을 사용안하고 풀어보려고 했는데 reverse도 결국 O(N)이라서 유의미한 차이는 없는거 같습니다.

실제로 중간 삽입, reverse도 중간부분을 뒤집는거라 같은 시간복잡도가 예상되는데 맞을까요?

답변 1

지식공유자

안녕하세요 재윤님 ㅎㅎ

정말 잘 짜셨네요.

        if(cnt[i] % 2 == 0) {
            for(int j = 0; j < cnt[i]/2; j++) temp += i + 65;
        } else {
            t++;

홀수와 짝수 분리하면서 t를 기반으로 펠린드롬이 안될 경우 체크하는 것도 너무 좋았습니다.

    ret = temp;
    reverse(temp.begin(), temp.end());
    if (c.empty()) cout << ret + temp << "\n";

사실 이 reverse는 어쩔 수 없는 거 같아요.

예를 들어 reverse를 안쓴다면 for문을 통해서 역순으로 집어넣어야 하는데 그거나 그거나 똑같습니다..

그러나 이렇게 함수 하나하나 시간복잡도를 신경쓰면서 코드를 구축하시려고 한 점은 너무나도 좋습니다. 계속해서 이렇게 해주세요.

잘 짜셨습니다.

또 질문 있으시면 언제든지 질문 부탁드립니다.

좋은 수강평과 별점 5점은 제가 큰 힘이 됩니다. :)

감사합니다.

강사 큰돌 올림.

작성한 질문수