zoonvivor

음수가 있는지 모르고 엄청 헤맨 문제;;

첫째 줄에 수의 개수 N(1<=N<=1,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 숫자가 주어진다. 이 수는 절대값이 1,000,000보다 작거나 같은 정수이다. 수는 중복되지 않는다. 라는 문구를 제대로 이해하지 못했다.

즉, 음수도 가능하다는 얘기

그렇다면 음수와 양수를 어떻게 나눌 것인가에 대한 문제가 생긴다. 

배열 위치는 항상 양수만 가능하기 때문에 (arr[-900]같은 음수들은 존재 불가)

나는 0~1000000까지는 음수를 저장하는 변수로 1000001~2000000 은 양수를 저장하는 변수로 만들었다.

처음에 1000000을 더해주고 결과를 낼때는 1000000을 빼주면 된다.

예를들어) -1000000은 Arr[0]에 저장되고, 나올때 -1000000의 값을 빼기때문에 결과는 큰 상관이 없다.

그리고 Count Sorting을 이용하여 문제를 풀었다.

문제에 나와있는대로 

1. 첫 번째 조각의 수가 두 번째 수보다 크다면, 둘의 위치를 서로 바꾼다.

2. 두 번째 조각의 수가 세 번째 수보다 크다면, 둘의 위치를 서로 바꾼다.

3. 세 번째 조각의 수가 네 번째 수보다 크다면, 둘의 위치를 서로 바꾼다.

4. 네 번째 조각의 수가 다섯 번째 수보다 크다면, 둘의 위치를 서로 바꾼다.

5. 만약 순서가 1, 2, 3, 4, 5 순서가 아니라면 1 단계로 다시 간다.

의 규칙대로 진행해주면 된다.

1자리 수 일때는 1 만 올 수 있다. (1개)

2자리 수 일때는 10 만 올 수 있다. (1개)

3자리 수 일때는 101, 100 이 올 수 있다. (2개)

4자리 수 일때는 1010, 1000, 1001 이 올 수 있다. (3개)

5자리 수 일때는 10100, 10101, 10000, 10001, 10010 이 올 수 있다. (5개)

6자리 수 일때는 101000, 101001, 101010, 100000, 100001, 100010, 100100, 100101 이 올 수 있다. (8개)

어느 정도 규칙이 보이지 않는가? 1 - 1 - 2- 3- 5- 8 - ???

안 보인다면 7자리 수일떄도 해보겠다.

1010000, 1010001, 1010010, 1010100, 1010101, 1000000, 1000001, 1000010, 1000100, 1000101, 1001000, 1001001, 1001010 (13개)

이정도면 보였으리라 생각한다. 피보나치의 규칙을 갖고 있다.

피보나치의 규칙을 이용해서 문제를 풀면 끝!

사실 이문제는 끝자리가 0으로 끝나는 dp[N][0], 1로 끝나는 dp[N][1] 로 푸는게 맞다.

앞의 수가 0일때는 0,1이 둘다 올수 있고 앞의수가 1일때는 0밖에 못오니깐..

아무튼 쉬운 경로로 풀면 되긴 하지만, 좀 더 직관적으로 보이는 뒤의 방법을 이용하는 것이 좋아보인다.

Comparator 를 이용한 문제 

Compartor 안에 조건문을 걸어주고 return 시켜 주면 이중, 삼중으로 정렬 할 수 있다.

return 값에서 x,y 부분을 반대로 바꿔주면 [오름차순 <-> 내림차순] 으로 바꿀 수 있다.

알고리즘 분류로 정렬 문제를 풀고있는데 이문제는 정렬의 문제가 아닌거 같다.

가장 중요한건 long 변수를 사용해야 한다는 점?

2중 반복문으로 전체를 계산했기 떄문에 시간 성능 나쁘다.

정렬을 하나 마나 똑같을 테고..

좀 더 빠른 방법이 있긴 할텐데..

1931 문제를 풀고 난 후 푸니까 매우 쉬웠다.

Comparator를 사용한 정렬을 했다.

아래는 1931 문제에서 Comparator를 사용한 내용

그리고 11650 좌표정렬하기 1 번이랑 문제가 또오오오옥같다. (x좌표랑 y좌표만 바꾸면 됨)

-------------------------------------1931------------------------------------- 

이때, 나는 Comparator를 이용해 정렬을 했다.

정렬을 할 때 

1 1                0 1

1 1      --->      1 1

0 1      --->      1 1

2 3                2 3

처럼 정렬이 되어야 하는데 기본 Comparator 에서는 정렬되지 않기 때문에

동일 시 되었을 경우 앞에 값을 우선으로 하는 start[1] ==end[1] 이라는 조건을 넣어

종료시간 정렬 후 종료 시간이 같을 경우, 시작시간에 따라 다시 한번 정렬을 했다.

-------------------------------------1931------------------------------------- 

11651 좌표 정렬하기 2 소스코드

계속 해서 Comparator를 사용해서 문제를 풀고 있다. 으흠

1. 맨처음 나이순으로 정렬한다.

끝이다.

그 다음 가입한 순서대로 정렬을 해야하는데 들어온 순서가 가입한 순서기 때문에 이미 정렬이 되서 들어왔다.

단순히 String[][] 2차원 배열을 어떻게 정렬할까에 대한 문제이다.

1931 문제를 풀고 난 후 푸니까 매우 쉬웠다.

Comparator를 사용한 정렬을 했다.

아래는 1931 문제에서 Comparator를 사용한 내용

-------------------------------------1931------------------------------------- 

이때, 나는 Comparator를 이용해 정렬을 했다.

정렬을 할 때 

1 1                0 1

1 1      --->      1 1

0 1      --->      1 1

2 3                2 3

처럼 정렬이 되어야 하는데 기본 Comparator 에서는 정렬되지 않기 때문에

동일 시 되었을 경우 앞에 값을 우선으로 하는 start[1] ==end[1] 이라는 조건을 넣어

종료시간 정렬 후 종료 시간이 같을 경우, 시작시간에 따라 다시 한번 정렬을 했다.

-------------------------------------1931------------------------------------- 

11650 좌표 정렬하기 <소스코드>

Comparator 가 부족한것 같아서 Compartor를 이용해서 문제를 풀었다.

Comparator에서 int, float, char 등은 원시적인 데이터등은 정렬이 되지 않고 Object등만 정렬 가능하다. (String, Integer 등등)

그런데 원시적인 데이터의 2차 배열은 객체인가보다.. int[][]는 Comparator를 통해 정렬을 할 수 있다.  너므 어려운것...

나는 그래서 이문제를 Comparator를 통해 풀고자 int배열이 아닌 Integer 배열을 사용했다.

나처럼 Comparator를 사용해서 푼 사람은 많이 없는거 같아서 나한텐 어려웠던 문제

푸는 방법) 

끝난 시간이 빠를 수록 다음 시작시간이 빠르기 때문에 2차원 배열을 정렬한다.

다음 제일 빨리 시작하는 회의를 선택한다. (끝나는 시간도 제일 빠르다. 이미 정렬을 해 놨으므로)

차례대로 마지막까지 반복한다.

1. 시작시간 - 종료시간 을 arr[][] 배열에 저장한다.

2. arr[][] 배열을 종료시간에 따라 정렬한다.

이때, 나는 Comparator를 이용해 정렬을 했다.

정렬을 할 때 

1 1                0 1

1 1      --->      1 1

0 1      --->      1 1

2 3                2 3

처럼 정렬이 되어야 하는데 기본 Comparator 에서는 정렬되지 않기 때문에

동일 시 되었을 경우 앞에 값을 우선으로 하는 start[1] ==end[1] 이라는 조건을 넣어

종료시간 정렬 후 종료 시간이 같을 경우, 시작시간에 따라 다시 한번 정렬을 했다.

3. 정렬이 되었다면, 종료시간과 다음에 올 시작시간을 비교하면 된다.