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

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

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

**문제의 핵심**

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\
&#x20;            i번째 수를 num\[i]에 넣으면 됨. \
같으면 : 중복횟수 저장 배열 cnt\[i] = 2\
&#x20;           i번째 수를 num\[i]에 넣으면 됨.//이까진 ok.하지만 i+1루프가 됐을 때 문제가 된다!\
&#x20;    \=>i+1이 됐을 때, i+1과 i+2가 다르면 i+1도 num\[i+1] = temp\[i+1] 들어간다.\
&#x20;    \=>그러면 결과적으로 i, i+1번째 숫자가 같은데 둘다 들어가버리게 되는 것이다!\
&#x20;    \=>또한, 중복 숫자가 발생하면 중복이 끝날 때까지 횟수를 카운팅해야하기 때문에 중복이 끝나면 그제서야 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++){\
&#x20;  if(x == temp\[i]) {c++;}//중복 횟수만 증가시키고, i+1가 됐을 때 num과 cnt배열에 저장한다!\
&#x20; else{\
&#x20;      num\[k] = x;\
&#x20;      cnt\[k] = c;\
&#x20;      k++;\
&#x20;      x = temp\[i]; c = 1;//c가 2였다면 다시 1로 초기화.\
&#x20; }\
}//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] 을 저장한다!)

```java
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]++;
    }
}
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://heunnajo.gitbook.io/algorithms-problem-solving-skills/brute-force/n-m9-2.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.