정렬

[JAVA] 백준 11004번 【K번째 수】

이 문제는, BufferedReader 로 입력 받고, sort() 메서드를 쓰면 해결되긴 하지만, 정렬 알고리즘 유형 특성상, 정렬을 구현하게끔 설계해놨을 것이라 생각이 들기도 했고, 속도도 느린 것 같아 찾아보니 Quick Sort 알고리즘을 이용해서 푸는 사람들이 많았다. double pivot quick sort 라는 quick sort 의 다른 버전도 있었지만, Quick sort 자체를 처음 접해봐서, 일단 Quick Sort 를 공부해보고 코드를 작성하여 제출하였다. 오름차순 기준으로 설명해보겠다. 간단하게 설명하면, 기준 값을 하나 정하고, start index 0에서부터 기준값보다 크거나 값을 발견하고, end index 끝에서부터 기준값보다 작거나 같은 값을 발견할 시, 두수의 위치를 ..

[JAVA] 백준 11652번 【카드】

최근에, Map 사용해서 카운팅하는 메서드를 많이 작성해봤던게, 이 문제를 푸는데 도움을 주었다. 확실히, 여러 알고리즘을 풀어보는게 프로그래밍 언어의 다양한 문법들을 복습하고 배우는데 도움이 되는 것 같다. 아무튼! 수의 범위가 크므로, Map map의 키 값으로 입력되는 수를 기록할 것이고, integer 에는 횟수를 셀 것이다. Map 카운팅 자체는 크게 어려운 부분은 없지만, 가장 많이 가지고 있는 정수가 여러가지라면 작은 것을 출력해야 하므로 이 부분 조건식을 작성할 때, 주의해야한다. maxTime을 0으로 초기화 시키고, maxTime 보다 큰 횟수를 가진 key 값이 존재하면, maxKey와 maxTime을 업데이트 해준다. 만약, 어떤 키의 횟수가, 이미 등록된 maxTime과 동일하다면..

[JAVA] 백준 10989번 【수 정렬하기 3】

문제 자체는 평범한 오름차순 문제이지만, 메모리와 시간 제한이 까다로워서 곰곰히 생각해보고 문제를 풀어봤다. 요즘, 정렬 문제를 풀어보면서 StringBuilder 의 위대함을 느끼고 있어서, StringBuilder 를 이용해서 문제를 풀어보았다. 방법은 간단하다. StringBuilder 배열을 만들어서, 입력값이 1~10000이라고 했으므로, 입력되는 값을 인덱스로 지정하고 그 인덱스 값에 "\n" 을 추가해서 문자열을 append 해준 후 출력하면 된다. 참고로 String str 을 루프 안에서 선언할 경우, 메모리 초과가 일어날 수 있으니 주의해야한다. import java.io.BufferedReader; import java.io.IOException; import java.io.Input..

[JAVA] 백준 10825번 【국영수】

이제, 정렬 문제를 람다식을 사용해서 해결하는 방법을 완전히 터득한 것 같다. 그리고, 정렬 문제를 풀때마다 StringBuilder를 사용해서 출력하는 것의 엄청난 효과를 느끼는 것 같다. 웬만하면 StringBuilder를 사용해서 출력해야겠다. ㅎㅎ for each문을 사용해서 println 하는 방법과 StringBuilder에 쌓아두고 한번에 출력하는 방법 속도가 거의 2배 차이 난다...ㅎㅎ 아무튼 이 문제의 키포인트는 국어 점수는 감소하는 순서, 영어 점수는 증가하는 순서, 수학 점수는 감소하는 순서, 이름은 증가하는 순서 임을 파악하고 이에 맞는 return 값을 건네주면 된다. 참고로 이름은 String 이므로, compareTo() 메서드를 사용했다. [JAVA] Comparator 와..

[JAVA] 백준 10814번 【나이순 정렬】

이 문제도, 다른 정렬 문제와 비슷하다. 처음에, Member 클래스를 생성한 뒤, Comparable을 implements 한 다음 나이가 같다면, 맴버 아이디를 비교하고, 나이가 다르다면, 나이를 기준으로 오름차순 되게끔 compareTo()를 정의한 후 List memberList = new ArrayList(); 를 선언해서 Member 타입의 객체들을 기록한 뒤, Collections.sort()를 사용해서 정렬하였다. 그리고 출력 시, [나이 이름] 이 출력되야 하므로, toString()을 오버라이딩하였다. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java..

[JAVA] 백준 11651번 【좌표 정렬하기 2】

이번 문제는, 이전에 풀었었던 11650 문제와 굉장히 흡사하다. [JAVA] 백준 11650번 【좌표 정렬하기】 이 문제는, 단순히 1차원 오름차순 정렬이 아닌, x좌표가 같은 경우 y좌표도 비교해야 하기 때문에, sort 함수의 정렬 조건을 변경시켜주어야 한다. [JAVA] Comparator 와 Comparable에 대해 이해하기 배열 yinq.tistory.com 다만, 차이점이 있다면, y좌표 기준으로 먼저 오름차순 정렬을 한 뒤에, y좌표가 같다면, x좌표를 비교해서 오름차순으로 비교한다는 점이다. 저번 문제에서는, Comparator 을 implements 하는 CustomComparator 객체를 만들어서 해결했었는데, 이번엔 람다 식 연습도 할 겸, 람다식을 이용해서 풀어봤다. 람다식으로..

[JAVA] 백준 11650번 【좌표 정렬하기】

이 문제는, 단순히 1차원 오름차순 정렬이 아닌, x좌표가 같은 경우 y좌표도 비교해야 하기 때문에, sort 함수의 정렬 조건을 변경시켜주어야 한다. [JAVA] Comparator 와 Comparable에 대해 이해하기 배열을 오름차순하는 가장 쉬운 방법은 Arrays 를 import 해준 뒤, Arrays의 sort 메서드를 사용하면 알아서 오름차순 정렬을 해준다! sort 메서드는 Comparable 인터페이스를 Arrays 클래스에서 구현하여 동 yinq.tistory.com 마침 최근에, 한 백엔드 스쿨 동기분 덕분에 Comparator 에 대한 이해를 한 상태라서 수월하게 해결할 수 있었다. 먼저, Arrays.sort(int [][] array) 와 같은 방식으로 sort 메서드를 사용할 ..

[JAVA] 백준 2751번 【수 정렬하기 2】

정답을 맞추긴 했지만, 시간이 비정상적으로 높은 것 같아 다양한 방법을 시도했다. 1. BufferedReader 와 Arrays.sort()를 사용한 뒤, 향상된 for문을 사용해서 BufferedWriter로 출력하게끔 답을 제출했더니 1708ms 가 나왔다. 2. BufferedReader 와 Arrays.sort()를 사용한 뒤, 일반적인 for문을 사용해서 BufferedWriter로 출력하게끔 답을 제출했더니 1472ms 가 나왔다. 향상된 for문보다 그냥 for문 루프를 돌리는게 속도가 더 빠르다는 사실을 얼떨결에 알게 되었다. 3. BufferedReader 로 입력을 받은 뒤, Arrays.sort 를 사용하고 StringBuilder를 사용해서 데이터들을 저장한 뒤, 한번에 출력하게끔..