좌표 압축 : Xi 를 좌표 압축한 결과 Xi'은 Xi > Xj 를 만족하는 서로 다른 좌표의 개수와 같아야 한다.
이 말은 쉽게 말해서
자기보다 작은 숫자의 개수
와 같다. 따라서 배열 반복문 돌면서 자기보다 작은 숫자의 개수를 세주면 된다.
당연히 첫 번째로 생각한 풀이는 배열 루프 돌면서 자기보다 작은 원소의 개수를 세고 그걸 기록해주는 방식이다.
하지만 N이 최대 1,000,000 이므로 당연히? 시간초과가 뜰 것이다. 이걸 직접 해봐야 시간 초과가 날 것이라고 알만한 그런 하꼬는 아니다. 그래도 지금까지 푼 문제가 있는데ㅡㅡ
곧바로 두 번째 풀이를 생각해냈다.
주어진 입력 배열을 정렬 시키는데 이 때 원래의 자기 위치(인덱스)를 기억해놓는 것이다. 왜냐하면 정답을 출력할 때 주어진 입력의 순서대로 답을 내야하기 때문이다.
따라서 오름차순으로 정렬을 해주는데 자기의 원래 인덱스를 기억할 것이고 cnt를 0부터 시작해서 += 1 해줄거고 이 때 바로 이전의 원소와 해당 원소가 같지 않다면 cnt를 증가시켜주지 않으면 된다. 젤 처음에는 cnt를 모두 0으로 초기화 시켜 세 번째 원소로 둔다.
정리를 해보면 2차원 배열은 다음과 같은 형태이다.
(입력이 2, 4, -10, 4, -9 일 때를 가정)
초기 상태
[0] = 원래의 자기 위치(인덱스)
[1] = 입력값(숫자)
[2] = cnt(0으로 초기화)
[
[0, 2, 0],
[1, 4, 0],
[2, -10, 0],
[3, 4, 0],
[4, -9, 0],
]sort 후 상태 (입력값에 따라 오름차순)
[
[2, -10, 0],
[4, -9, 1],
[0, 2, 2],
[1, 4, 3],
[3, 4, 3]
]=> 4와 4는 똑같으므로 cnt 증가 x => 3 추가
정답 출력을 위해 sort 후 마지막 상태 (원래의 자기 위치에 따라 오름차순)
[
[0, 2, 2],
[1, 4, 3],
[2, -10, 0],
[3, 4, 3],
[4, -9, 1]
]그러고 [2] 자리의 원소를 차례대로 출력해주면? 정답!
패드에 끄적였던 내용도 같이 기록해둔다.
하.. 이걸 내가 풀었다고? ㅋㅋㅋ 미치겠다^^ 오늘 저녁 맛있는 거 먹어야지
오늘부터 부산대 축제가 시작됐다.
정말 많은 사람들이 학교로 몰렸고 제도관(컴공 건물)에도 처음보는 사람들이 많이들 왔다. 조금 어수선하기까지 하다. (올해는 컴공 학생회에서 게임 부스를 하나 운영하는데 제도관에 1층에서 오징어게임?을 하더라)
다들 축제라고 밖에 나가서 열심히 논다. 나는 혼자 과도에 박혀서 공부한다. (혼자는 아니고 주용이랑 인욱이랑 같이 있긴 하다)
저녁 간단하게 먹고 밤까지 계속 할꺼다. 오히려 평소보다 더 열심히 할거다.
물론 지금 애들 데꼬 나가서 맛있는 거 먹고 사람 구경도 하고 게임도 하면서 축제를 즐기고 놀아도 된다.
하지만 그러지 않는 이유는 ?
딱히 없다.
그냥 되도 않는 곤조?에 가깝고 그냥 똥고집이다.
남들 공부 열심히 할 때 나는 그렇게 열심히 죽자고 덤벼들지 않았다(이는 지극히 상대적이니 나보다 열심히 안한 사람들도 분명 있을 것이다. 하지만 걔네들은..굳이 신경쓸 필요조차 없다)
그들은 아마 지금까지 열심히 공부했으니 축제만큼은 나가서 놀자!! 라는 생각일 것이다. 또한 날씨가 너무 좋아진 요즘 외로운 사람들은 여자친구를 만들겠다는 목적으로 오는 사람들도 분명 많을 것이다.
지금까지 열심히 했으니 지금만큼은 다같이 놀자고, 머리 식히고 다시 열심히 하자고, 그러자고 정해준 축제 기간이다.
근데 아이러니하게 여기서 같이 놀면 너무 뒤쳐지는 느낌이 든다. 평소에 그렇게 죽자 살자 열심히 하지 않았기 때문일지 모른다.
또 하나 이상한 점은 (컴공이라 그럴지 모른다)
시험 기간이 다가와도 이렇게나 많은 사람들이 과도에 공부하러 오지는 않았는데... 지금 자리가 꽉 찼다. 사람 진짜 많다. 심지어 다들 너무 열심히 한다. 처음보는 사람도 많다.
도대체 어떤 원리로 밖에는 노는 사람들로 꽉 차서 걸어다니기 힘들 정도인데 도서관에는 평소보다 더 사람이 더 많을까
이러면.. 위에 적어 놓은게 (뭐 대충,, "니들 놀 때 공부할게 그럼 됐제?" 라는 내용의 똥고집) 전부 개소리가 되는 마법이 벌어진다. 얘네는 평소에도 열심히 하고 지금도 이렇게 열심히 하니까.. 하지만 해결 방법은 간단하다. 오늘만큼은 얘네보다 더 열심히 하면 된다.
아니? 얘네랑 비교할 필요도 없고 평소에 내가 했던 공부보다 훨씬 더 많이 훨씬 더 집중해서 하면 된다.
