알고리즘을 좋아하는 나

곱셈의 결합법칙을 이용해서 예외처리를 해줬다.

주석에 설명을 잘 달아놨다.

처음에 문제를 잘 못 이해해서,

8
4
3
6
8
7
5
2
1

이면

8 = n 이고

4번 +하고

4 - 3 + 1 만큼 -하고 이런식으로 되는 줄 알앗는데,

1~N까지 push하고 차례대로 pop해주는거였다.

아이디어 :

1. 에라토스테네스의 체를 이용해서 소수를 구한다.

2. 소수를 primeNumber에 하나씩 넣어준다. 마지막값은 0이다.

3. 2... 돌게되면 0이 나오는데 0이면 반복문을 종료한다.

4. 반복문 안에 반복문을 넣어서 값을 더해주고 맞으면 빼기한 값을 저장하고 그걸로 체크를한다.

더 좋은 방법.

어차피 빼기값을 최소로 구하는거니까. n/2부터 시작해서 하나씩 빼면서 맞는답이 나오면 바로 출력하면 더 빠르다.

이 방법을 사용하면 2번 과정이 없어진다.

더 좋은 방법을 사용한다면,

O(Nnlgn)이 될거같다.

문제를 딱 보고.

아 이건! 미리 구해놓고 하나씩 출력하면 될듯~

에라토스테네스의 체를 복습했다.

c++ 기본기 없이 코딩하려니 에러도 많이나서 질문도 많이했다.

풀이과정은

1. 무식하게 버블정렬 : 시간초과

2. sort를 사용하니까 통과됨

a.length >= b.length를 고려 안해줘서 조금 많이 틀렸다.

카운팅 정렬을 사용했다.

제공되는 숫자들의 절댓값이 4000을 넘지 않는다.

-4000 <= x <= 4000 

idx는 0부터 시작하니까 4000 을 더해주면 0 ~ 8000이다.

그럼 배열의 length 는 8001.

산술평균은 입력받는 값들을 합해서 N으로 나눠주면 된다.

중앙값은 idx 0 부터 체크하면서 N / 2 번째의 숫자를 확인해주면 된다.

최빈값은 애매하게 2번째로 작은값을 출력을 하라고 한다.

처음에 최빈값이 몇개 나왔는지를 구하고, 2번째로 작은 값을 구해준다.

범위는 간단하게 제일 작은값을 min으로 넣어주고, 가장 큰 값을 max로 넣어서 max - min 해준다.

min과 max를 넣어주는 과정은 최빈값을 구하는 과정에서 list[i] > 0 이면 체크해서 넣어준다.

KMP를 사용해서 풀었고,

LinkedList에 idx값을 담아줬다.

가장 큰 거

String을 그대로 사용하면 문자열 추가중에 시간초과가 남

StringBuilder를 사용하면 해결~

KMP는 더 공부가 필요함(PI를 구하는 쪽을 걍 넘어간듯)

1번째 풀이와 2번째 풀이가 있다.

1번째 풀이는 시간초과가 난다.

O(MN) = 16억번

2번째 풀이는

O(M)이다.

-1이 나오는 조건은 x가 N보다 크거나 같을때(스왑하는 과정이나 입력값이 이상할때)

정답을 구하는 방법은

앞 자리 즉 x 의 값으로 y 의 값을 찾아가는 형식이다.

M을 계속 더해줌

(tempy!=y&&_lcm==result)의 조건을 안넣어서 계속 틀렸었다.

(tempy!=y&&_lcm==result)를 넣지 않으면 거의다 lcm(M,N)의 값이 뜬다.

일단 문제를 보면 0~9까지의 숫자카드를 1세트로 계속 받고 6 = 9 이다.

그래서 9를 입력받으면 6배열에 ++해주고

for loop을 하면서 배열에 값을 하나씩 빼줬다.

6은 2개씩 빼줌

for문을 while문으로 감싼 이유는 1세트씩 계속 주기위해서.