알고리즘을 좋아하는 나

문제를 딱 보고.

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

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

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

풀이과정은

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

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

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

100000000>N의 숫자를 각 자리수를 뽑아서 내림차순으로 정렬하는 문제다.

Character로 받아서 바로 int로 바꿔주고 배열에 담는다.

그리고 그 배열에서 9~0까지 차례대로 출력~

카운팅 정렬을 사용했다.

제공되는 숫자들의 절댓값이 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세트씩 계속 주기위해서.

k-1층의 1~b호 까지의 사람들이 k층 b호에 살아야 된다.

0층 i호에는 i명이 산다.

배열이

1 2 3 4 5

1 3 6 10 15

이런식으로 만들어진다.

위에서 부터 0층 1층 으로 계산했을때

d[i][j] = d[i-1][j] + d[i][j-1] 이다.

그래서 처음 입력받기 전에 초기화해주고 

입력받는 값으로 배열에 대입해서 출력하면 된다.

H * W 호텔에서 N번째 사람이  어디에 들어가는지 구하는 문제.

첫 번째 문제를 푼 아이디어는

(N/H+1)*100+N/H+1

이였다. 

일단 내가 W에 대해 아무것도 작성하지 않은 이유는 굳이 W까지 해서 계산할 필요 없이 나눈값 + 1이 들어가기 때문이다.

근데 이 풀이는 N과 H가 같으면 출력이 잘못된다.

그래서 반복문으로 N에 H를 빼면서 W를 1씩 더해주면서 호수를 구해줬다.

코드를 보는게 이해가 더 쉽게 될 것이다.