N M9 2번째 시도, 문제 복기

정답 소스코드와 속도 차이 비교 분석 index번째 수를 저장할 때 속도차이가 발생한다! 배열을 사용할 경우 그 다음 경우의 수를 넣을 때 사용했던 수 삭제할 필요없이 그냥 덮어쓰면 된다. 배열리스트를 사용할 경우, 현재 사용한 수를 제거해줘야하고, 제거할 때 n개의 수가 들어있다면 제거하는 데에 O(n)만큼의 시간복잡도가 소요되기 때문이다!

	정답	내 코드
자료 구조	배열	배열리스트
index번째 수 저장할 때	a[index] = i	a.add(i) ... a.remove(a.size()-1)

문제의 핵심

1. N개의 숫자를 입력받은 후 중복을 제거한 N'개의 숫자를 저장한다!

2. 중복 횟수를 저장한다!

i번째 수와 i+1번째 수를 비교해서 다음의 2가지 배열을 만든다.

1. 중복을 제거한 수 N개를 저장하는 배열

2. 중복 횟수를 저장하는 배열

비교를 반복하는 반복문을 만들 때 i와 i+1번째 수를 비교할 때, i에 맞춰서 반복문을 구성했다. => for(int i=0;i<N-1;i++) : N이 4라면 i의 범위는 0,1,2

이 경우 for문이 num을 다 완성하기도 전에 끝나기 때문에 for문을 나와서도 살아있는 변수가 필요하다! =>num의 인덱스가 되는 변수 필요, num에 들어가는 수를 변수로 생성해서 for문 밖에서도 사용할 수 있어야 한다. ex) num[n-1] = temp[n-1]

그냥 정답을 따라서 i와 i+1번째 수를 비교할 때 i+1에 맞춰서 반복문을 구성해본다. =>for(int i=1;i<N;i++) i번째, i+1 번째 수 비교 다르면 : 중복횟수 저장 배열 cnt[i] = 1 i번째 수를 num[i]에 넣으면 됨. 같으면 : 중복횟수 저장 배열 cnt[i] = 2 i번째 수를 num[i]에 넣으면 됨.//이까진 ok.하지만 i+1루프가 됐을 때 문제가 된다! =>i+1이 됐을 때, i+1과 i+2가 다르면 i+1도 num[i+1] = temp[i+1] 들어간다. =>그러면 결과적으로 i, i+1번째 숫자가 같은데 둘다 들어가버리게 되는 것이다! =>또한, 중복 숫자가 발생하면 중복이 끝날 때까지 횟수를 카운팅해야하기 때문에 중복이 끝나면 그제서야 num과 cnt에 저장한다!

그렇기 때문에 같으면 i번째 루프에서는 num에 숫자 저장❌ i+1 루프에서 현재의 i(i+1)가 됐을 때 num[i] = temp[i] 넣는다!!!

⭐️for문 스코프 밖(Before for-loop) 1. 비교할 수 : int x = temp[0] 2. num 인덱스 : int k = 0 3. 중복 횟수 : c = 1

⭐️for문 for(int i=1;i<N;i++){ if(x == temp[i]) {c++;}//중복 횟수만 증가시키고, i+1가 됐을 때 num과 cnt배열에 저장한다! else{ num[k] = x; cnt[k] = c; k++; x = temp[i]; c = 1;//c가 2였다면 다시 1로 초기화. } }//for문 끝

⭐️for문 스코프 밖(After for-loop) : 변수들이 살아있기 때문에 for문 내부 코드 그대로 사용가능하다! num[k] = x; cnt[k] = c; n = k+1;//중복 제거한 숫자 갯수는 num의 인덱스+1이다!

⭐️재귀함수 구현

위에서 중복을 제거한 N개의 숫자 배열로 순열을 만든다! => NM1, NM5와 동일하다. 하지만 달라진 점은 중복되는 숫자의 경 중복횟수를 저장했기 때문에 중복횟수만큼 재사용할 수 있다는 점이다!

재귀함수에서 다음 경우 호출하는 경우 (참고로 num[index]를 저장하는 것이 아니라 num배열의 index를 저장하고, M개를 다 골랐을 때 일괄적으로 한번에 num[index] 을 저장한다!)

StringBuilder ans = new StringBuilder();
for(int i=0;i<n;i++){
    if(cnt[i] > 0){
        cnt[i]--;
        a[index] = i;
        ans.append(go(index+1,n,m));
        cnt[i]++;
    }
}