[c++] 코딩인터뷰 완전분석 - 배열과 문자열 5

문제

같은 문자가 연속으로 반복될 경우, 그 횟수를 사용해 문자열을 압축하는 메서드를 구현하라. 가령 압축해야 할 문자열이 aabccccccccaaa라면 a2b1c8a3과 같이 압축되어야 한다. 압축 결과로 만들어지는 문자열이 원래 문자열보다 짧아지지 않는 경우, 이 메서드는 원래 문자열을 그대로 반환해야 한다.

 

풀이

문자열의 앞에서부터 같은 문자의 개수를 세고 다른 문자가 나오면 문자와 문자의 개수를 압축형태로 만들어나가면 됩니다.

 

이때 자바에서는 문자열을 + 연산으로 합치는 경우 새로운 문자열 객체를 생성하고 붙이는 작업을 수행할 때 O(n²)이 소요되어 문자배열을 사용해야 시간복잡도 O(n)으로 줄일 수 있습니다.

c++에서는 + 연산에서 새로운 문자열 객체를 생성하지 않는다고 하고 명확하진 않지만 일반적으로는 선형시간의 시간복잡도를 가진다고 하니 + 연산 혹은 append를 사용해도 무방할 것 같습니다.

 

 

구현 코드