문제 요약
자세한 내용은 leetcode에서 확인
https://leetcode.com/problems/count-and-say/
숫자로 구성된 스트링이 있다. 각 숫자가 연속으로 나열된 횟수를 세어 횟수 + 숫자로 변환하라. 이걸 n 만큼 반복한다.
n = 1 일때 output은 "1"이다. (베이스 케이스)
예제
input: n = 4
output: "1211"
n = 1: "1"
n = 2: 1이 한 개니까 1 + 캐릭터 1을 더해서 "11"
n = 3: 1이 두 개니까 2 + 캐릭터 1을 더해서 "21"
n = 4: 2가 한 개니까 1 + 캐릭터 2, 1이 한 개니까 1 + 캐릭터 1을 더해서 "1211"
풀이
2 포인터 문제.
메인 메소드는 for loop을 n 만큼 돌며 세컨 메소드를 호출한다. 결과값을 저장했다가 다음번 iteration의 input으로 사용한다.
세컨 메소드는 2 포인터를 사용한다. 두 포인터(p1, p2)가 인덱스 0에서 시작하여 서로 다른 캐릭터를 가리킬 때까지 두 번째 포인터(p2)를 움직인 다음, 해당 캐릭터가 몇 번 반복되었는지 카운팅 (p2 - p1)하고 해당 캐릭터(s.charAt(p1))을 합쳐서 변수에 저장하고 p2가 스트링의 길이보다 작을 동안 계속 반복한 후에 변수를 반환한다.
// 메인 메소드
public String countAndSay(int n) {
// n = 1 일때 "1" 반환
String res = "1";
// 베이스 케이스 후인 i = 1 부터 시작
for (int i=1; i<n; i++) {
// say 메소드를 매번 호출, 결과값을 다음에 다시 사용한다
res = say(res);
}
return res;
}
// 세컨 메소드
private String say(String s) {
String res = "";
// 2 포인터
int p1 = 0;
int p2 = 0;
while (p2 < s.length()) {
// 두개의 포인터가 다른 캐릭터를 가리킬 경우
if (s.charAt(p1) != s.charAt(p2)) {
// 카운팅과 캐릭터를 변수에 저장한다
res += (p2 - p1) + "" + s.charAt(p1);
// p1을 카운팅 할 새로운 캐릭터인 p2로 이동시킨다
p1 = p2;
}
p2++;
}
// 맨 마지막 카운팅이 위의 loop에 포함되지 않았기 때문에 한번 더 계산해준다
res += (p2 - p1) + "" + s.charAt(p1);
return res;
}
Complexity
time: O(n^2) - 메인 메소드에서 n번, 세컨 메소드에서 n번 돌았으니까 n^2
space: O(1) - 몇개 안되는 변수를 생성하였다.