[JAVA] 알고리즘 문제풀이 기초 - Sorting and Searching-2
Sorting and Searching
중복 확인 (6-5)
-
설명 : 현수네 반에는 N명의 학생들이 있습니다. 선생님은 반 학생들에게 1부터 10,000,000까지의 자연수 중에서 각자가 좋아하는 숫자 하나 적어 내라고 했습니다. 만약 N명의 학생들이 적어낸 숫자 중 중복된 숫자가 존재하면 D(duplication)를 출력하고, N명이 모두 각자 다른 숫자를 적어냈다면 U(unique)를 출력하는 프로그램을 작성하세요.
-
입력 : 첫 번째 줄에 자연수 N(5<=N<=100,000)이 주어진다. 두 번째 줄에 학생들이 적어 낸 N개의 자연수가 입력된다.
-
출력 : 첫 번째 줄에 D 또는 U를 출력한다.
-
작성 답안
import java.util.*;
public class Main {
public static void main(String[] args) {
Main t = new Main();
Scanner scan = new Scanner(System.in);
int num = scan.nextInt();
int[] arr = new int[num];
for(int i=0; i<num; i++){
arr[i] = scan.nextInt();
}
System.out.println(t.solution(arr));
}
public String solution(int[] arr){
String result = "U";
for(int i=0; i<arr.length-1; i++){
for(int j=i+1; j<arr.length; j++){
if(arr[i]==arr[j]) {
return "D";
}
}
}
return result;
}
}
- 풀이 답안
import java.util.*;
public class Main {
public static void main(String[] args) {
Main t = new Main();
Scanner scan = new Scanner(System.in);
int num = scan.nextInt();
int[] arr = new int[num];
for(int i=0; i<num; i++){
arr[i] = scan.nextInt();
}
System.out.println(t.solution(arr));
}
public String solution(int[] arr){
String result = "U";
Arrays.sort(arr);
for(int i=0; i<arr.length-1; i++){
if(arr[i]==arr[i+1]) {
return "D";
}
}
return result;
}
}
- 특징
- 풀이 접근방식은 동일하나 나의 경우는 기존의 배열에 직접 비교한것, 풀이는 Arrays.sort();를 사용
- 기존 함수를 최대한 사용하지 않고 풀이해야한다고 생각했는데 어떨때 사용해도 되는건지 풀이의 기준을 잘 모르겠음…
- 풀이 접근방식은 동일하나 나의 경우는 기존의 배열에 직접 비교한것, 풀이는 Arrays.sort();를 사용
장난꾸러기 (6-6)
-
설명 : 새 학기가 시작되었습니다. 철수는 새 짝꿍을 만나 너무 신이 났습니다. 철수네 반에는 N명의 학생들이 있습니다. 선생님은 반 학생들에게 반 번호를 정해 주기 위해 운동장에 반 학생들을 키가 가장 작은 학생부터 일렬로 키순으로 세웠습니다. 제일 앞에 가장 작은 학생부터 반 번호를 1번부터 N번까지 부여합니다. 철수는 짝꿍보다 키가 큽니다. 그런데 철수가 앞 번호를 받고 싶어 짝꿍과 자리를 바꿨습니다. 선생님은 이 사실을 모르고 학생들에게 서있는 순서대로 번호를 부여했습니다. 철수와 짝꿍이 자리를 바꾼 반 학생들의 일렬로 서있는 키 정보가 주어질 때 철수가 받은 번호와 철수 짝꿍이 받은 번호를 차례로 출력하는 프로그램을 작성하세요.
-
입력 : 첫 번째 줄에 자연수 N(5<=N<=100)이 주어진다. 두 번째 줄에 제일 앞에부터 일렬로 서있는 학생들의 키가 주어진다. 키(높이) 값 H는 (120<=H<=180)의 자연수 입니다.
-
출력 : 첫 번째 줄에 철수의 반 번호와 짝꿍의 반 번호를 차례로 출력합니다.
-
작성 답안 1 (수동 체크)
import java.util.*;
public class Main {
public static void main(String[] args) {
Main t = new Main();
Scanner scan = new Scanner(System.in);
int num = scan.nextInt();
int[] arr = new int[num];
for(int i=0; i<num; i++){
arr[i] = scan.nextInt();
}
System.out.println(t.solution(arr));
}
public String solution(int[] arr){
String result = "";
int lt=-1, rt=-1;
for(int i=0; i<arr.length-1; i++){
if(lt==-1 && arr[i]>arr[i+1]) {
lt=i-1;
while(arr[i]==arr[lt]){
lt--;
}
lt += 2;
}
if(lt!=-1 && arr[i]>arr[i+1]) rt=i+2;
}
return lt+" "+rt;
}
}
- 작성 답안 2 (Arrays.sort 사용)
import java.util.*;
public class Main {
public static void main(String[] args) {
Main t = new Main();
Scanner scan = new Scanner(System.in);
int num = scan.nextInt();
int[] arr = new int[num];
for(int i=0; i<num; i++){
arr[i] = scan.nextInt();
}
System.out.println(t.solution(arr));
}
public String solution(int[] arr){
String result = "";
int[] arr2 = new int[arr.length];
for(int i=0; i<arr.length; i++){
arr2[i] = arr[i];
}
Arrays.sort(arr2);
for(int i=0; i<arr.length; i++){
if(arr[i]!=arr2[i]) result += i+1+" ";
}
return result;
}
}
- 특징
- Arrays.sort 사용한버전과 사용하지 않은버전 두가지로 풀이함
- Arrays.sort 사용하지 않은 버전
- 사용하지 않은 경우 앞숫자보다 뒷숫자가 작은경우를 구했고
- 이때 lt와 rt라는 값을 작은학생,큰학생으로 임의 구분하여, 앞에서 lt가 찾아진경우 rt를 구하도록 함
- 동일한 키의 학생이 있을수 있기 때문에 앞의 수가 동일한 수가 있는지 while문으로 체크
- 동일수 체크가 끝나면 배열은 0부터지만 앞문자 체크를위해 또 –해둔상태라 +2를 해서 lt에 저장
- 뒷숫자는 굳이 동일수를 찾아줄 필요가 없기에+2만 해주면 됨(작은수를 찾아야하기에 +1, 인덱스번호가 0부터라 +1)
- Arrays.sort 사용한 버전
- 깊은복사로 똑같은 배열을 하나 더 만듬
- 복사배열을 오름차순으로 정렬함
- 비교해서 다른 값의 인덱스를 찾음
- Arrays.sort 사용한버전과 사용하지 않은버전 두가지로 풀이함
좌표 정렬 (6-7)
-
설명 : N개의 평면상의 좌표(x, y)가 주어지면 모든 좌표를 오름차순으로 정렬하는 프로그램을 작성하세요. 정렬기준은 먼저 x값의 의해서 정렬하고, x값이 같을 경우 y값에 의해 정렬합니다.
-
입력 :첫째 줄에 좌표의 개수인 N(3<=N<=100,000)이 주어집니다. 두 번째 줄부터 N개의 좌표가 x, y 순으로 주어집니다. x, y값은 양수만 입력됩니다.
-
출력 : N개의 좌표를 정렬하여 출력하세요.
-
작성 답안
import java.util.*;
public class Main {
public static void main(String[] args) {
Main t = new Main();
Scanner scan = new Scanner(System.in);
int num = scan.nextInt();
int[][] arr = new int[num][2];
for(int i=0; i<num; i++){
arr[i][0] = scan.nextInt();
arr[i][1] = scan.nextInt();
}
for (int[] ints : t.solution(arr, num)) {
System.out.println(ints[0]+" "+ints[1]);
}
}
public int[][] solution(int[][] arr, int size){
int[][] tmp = new int[1][2];
for(int i=0; i<size; i++){
int max1 = -1;
tmp[0][0] = arr[size-i-1][0];
tmp[0][1] = arr[size-i-1][1];
for (int j=size-i-1; j>=0; j--){
if(arr[j][0]>tmp[0][0]) {
max1 = j;
tmp[0][0] = arr[j][0];
tmp[0][1] = arr[j][1];
}
if(arr[j][0] == tmp[0][0]) {
if(arr[j][1]>tmp[0][1]) {
max1 = j;
tmp[0][0] = arr[j][0];
tmp[0][1] = arr[j][1];
}
}
}
if(max1>-1){
arr[max1][0] = arr[size-i-1][0];
arr[max1][1] = arr[size-i-1][1];
arr[size-i-1][0] = tmp[0][0];
arr[size-i-1][1] = tmp[0][1];
}
}
return arr;
}
}
- 풀이 답안
import java.util.*;
class Point implements Comparable<Point>{
int x;
int y;
Point(int x, int y){
this.x = x;
this.y = y;
}
@Override
public int compareTo(Point o){
if(this.x == o.x) return this.y-o.y;
else return this.x-o.x;
}
}
public class Main {
public static void main(String[] args) {
Main t = new Main();
Scanner scan = new Scanner(System.in);
int num = scan.nextInt();
ArrayList<Point> arr = new ArrayList<>();
for(int i=0; i<num; i++){
int x = scan.nextInt();
int y = scan.nextInt();
arr.add(new Point(x, y));
}
Collections.sort(arr);
for (Point point : arr) {
System.out.println(point.x+" "+ point.y);
}
}
}
- 특징 (반드시 복습할것)
- 나의 경우 수기로 이중 배열을 만들어 하나하나 정렬을 하는 식으로 방법을 생각
- 코테상에서 요구하는 것은 Comparable을 사용하여 비교하는것이었음
- 별도의 클래스를 만들고 Comparable를 implements 받음
- compareTo를 오버라이드 해서 비교
- 이때 this.y-o.y를 해줬기 때문에 내림차순. 반대의 경우 오름차순
- 따로 함수를 돌릴필요 없이 Collections.sort()를 사용해서 정렬을 마침
- 나의 경우 수기로 이중 배열을 만들어 하나하나 정렬을 하는 식으로 방법을 생각
이분검색 (6-8)
-
설명 : 임의의 N개의 숫자가 입력으로 주어집니다. N개의 수를 오름차순으로 정렬한 다음 N개의 수 중 한 개의 수인 M이 주어지면 이분검색으로 M이 정렬된 상태에서 몇 번째에 있는지 구하는 프로그램을 작성하세요. 단 중복값은 존재하지 않습니다.
-
입력 : 첫 줄에 한 줄에 자연수 N(3<=N<=1,000,000)과 M이 주어집니다. 두 번째 줄에 N개의 수가 공백을 사이에 두고 주어집니다.
-
출력 : 첫 줄에 정렬 후 M의 값의 위치 번호를 출력한다.
-
작성 답안
import java.util.*;
public class Main {
public static void main(String[] args) {
Main t = new Main();
Scanner scan = new Scanner(System.in);
int size = scan.nextInt();
int[] arr = new int[size];
int num = scan.nextInt();
for(int i=0; i<size; i++){
arr[i] = scan.nextInt();
}
System.out.println(t.solution(arr, num));
}
public int solution(int[] arr, int num){
int result = 0;
Arrays.sort(arr);
for (int i : arr) {
result++;
if(i==num) break;
}
return result;
}
}
- 풀이 답안
import java.util.*;
public class Main {
public static void main(String[] args) {
Main t = new Main();
Scanner scan = new Scanner(System.in);
int size = scan.nextInt();
int[] arr = new int[size];
int num = scan.nextInt();
for(int i=0; i<size; i++){
arr[i] = scan.nextInt();
}
System.out.println(t.solution(arr, num));
}
public int solution(int[] arr, int num){
int result = 0;
Arrays.sort(arr);
int lt=0, rt=arr.length-1;
while(lt<=rt){
int mid = (lt+rt)/2;
if(arr[mid]==num) {
result = mid+1;
break;
}
if(arr[mid]<num) lt=mid+1;
else rt=mid-1;
}
return result;
}
}
- 특징
- 단순 카운트가 아니라 이분검색을 하는것이 핵심. 따라 내가 작성한 풀이는 접근이 틀림
- 이분검색은 무조건 정렬이 되어있는 상태에서만 가능
- lt와 rt를 선언한 다음에, 이용하여 중간값을 구함
- 중간값이 찾는 값과 동일한지 확인. 찾으면 끝
- 동일하지 않으면 더 큰지, 작은지 확인해서 lt또는 rt를 변경
- 이분검색 방법은 암기해둘것
- 단순 카운트가 아니라 이분검색을 하는것이 핵심. 따라 내가 작성한 풀이는 접근이 틀림