백준 닷컴 단계 별로 풀어보기 13단계

1단계 수 정렬하기

• 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 절댓값이 1,000보다 작거나 같은 정수이다. 수는 중복되지 않는다.
• 첫째 줄부터 N개의 줄에 오름차순으로 정렬한 결과를 한 줄에 하나씩 출력한다.

import java.util.Arrays;
import java.util.Scanner;

public class Step_1 {
	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		
		int n = scan.nextInt();
		
		int[] arr = new int[n];
		for (int i=0; i<n; i++) {
			arr[i]=scan.nextInt();
		}
		Arrays.sort(arr);
		for (int i=0; i<n; i++) {
			System.out.println(arr[i]);
		}
	}
}

A.

• 배열을 받아주고 Arrays.sort 기능을 이용해 정렬 후 출력한다.

2단계 대표값2

• 첫째 줄부터 다섯 번째 줄까지 한 줄에 하나씩 자연수가 주어진다. 주어지는 자연수는 100 보다 작은 10의 배수이다.
• 첫째 줄에는 평균을 출력하고, 둘째 줄에는 중앙값을 출력한다. 평균과 중앙값은 모두 자연수이다.

import java.util.Arrays;
import java.util.Scanner;

public class Step_1 {
	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		

		int[] arr = new int[5];
		int sum=0;
		for (int i=0; i<5; i++) {
			arr[i]=scan.nextInt();
			sum+=arr[i];
		}
		Arrays.sort(arr);
		System.out.println(sum/5);
		System.out.println(arr[2]);
	}
}

A.

• 배열을 받아주고 Arrays.sort 기능을 이용해 정렬 한다.
• 배열의 각 값을 sum에 받고 평균을 출력한다.
• 배열의 중앙인 arr[2]를 출력한다.

3단계 커트라인

• 첫째 줄에는 응시자의 수 N과 상을 받는 사람의 수 k가 공백을 사이에 두고 주어진다.
• 둘째 줄에는 각 학생의 점수 x가 공백을 사이에 두고 주어진다.
• 상을 받는 커트라인을 출력하라.

import java.util.Arrays;
import java.util.Scanner;

public class Step_1 {
	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		
		int n = scan.nextInt();
		int k = scan.nextInt();
		int[] arr = new int[n];
		for (int i=0; i<n; i++) {
			arr[i]=scan.nextInt();
		}
		Arrays.sort(arr);
		System.out.println(arr[n-k]);
	}
}

A.

• 배열을 받아주고 Arrays.sort 기능을 이용해 정렬 한다.
• k번째로 높은 점수는 arr[n-k]로 출력한다.

4단계 수 정렬하기 2

• 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 절댓값이 1,000,000보다 작거나 같은 정수이다. 수는 중복되지 않는다.
• 첫째 줄부터 N개의 줄에 오름차순으로 정렬한 결과를 한 줄에 하나씩 출력한다.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;

public class Step_1 {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

		int n = Integer.parseInt(br.readLine());
		int[] arr = new int[n];
		for (int i = 0; i < n; i++) {
			arr[i] = Integer.parseInt(br.readLine());
		}
		br.close();

		Arrays.sort(arr);
		for (int i = 0; i < n; i++) {
			bw.write(arr[i] + "\\n");
		}
		bw.flush();
		bw.close();
	}
}

A.

• 배열의 길이가 길고, 요구 시간이 적기 때문에 Scanner 사용 시 시간 초과가 발생한다.
• buffer를 사용하여 처리할 필요가 있다.
• 정렬 방법도 버블이나 선택 정렬 같은 정렬은 n제곱의 시간 복잡도를 가지기 때문에 자바의 Arrays.sort 기능을 이용하면 nlogn의 시간 복잡도의 정렬을 실시할 수 있다.
• 해당 코드를 이용하여 작성시 1.7초의 시간이 소요된다.

5단계 수 정렬하기 3

• 첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 10,000보다 작거나 같은 자연수이다.
• 첫째 줄부터 N개의 줄에 오름차순으로 정렬한 결과를 한 줄에 하나씩 출력한다.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;

public class Step_1 {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

		int n = Integer.parseInt(br.readLine());
		int[] arr = new int[n];
		for (int i = 0; i < n; i++) {
			arr[i] = Integer.parseInt(br.readLine());
		}
		br.close();

		Arrays.sort(arr);
		for (int i = 0; i < n; i++) {
			bw.write(arr[i] + "\\n");
		}
		bw.flush();
		bw.close();
	}
}

A.

• 4번과 방법으로 해결할 수 있다.
• 해당 코드를 이용하여 작성 시 2.5초의 시간이 소요된다.

6단계 소트인사이드

• 첫째 줄에 정렬하려고 하는 수 N이 주어진다. N은 1,000,000,000보다 작거나 같은 자연수이다.
• 첫째 줄에 자리수를 내림차순으로 정렬한 수를 출력한다.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;

public class Step_6 {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

		String n = br.readLine();
		br.close();
		String[] strArr = n.split("");

		Arrays.sort(strArr);
		for (int i = 0; i < n.length(); i++) {
			bw.write(strArr[n.length() - 1 - i]);
		}
		bw.write("\\n");
		bw.flush();
		bw.close();
	}
}

A.

• 숫자를 String으로 받아준다.
• 각 글자를 받을 String 배열을 선언하고 n을 split 하여 초기화한다.
• String 배열을 sort 기능으로 정렬한다.
• 역순으로 나란히 출력한다.

7단계 좌표 정렬하기

• 2차원 평면 위의 점 N개가 주어진다. 좌표를 x좌표가 증가하는 순으로, x좌표가 같으면 y좌표가 증가하는 순서로 정렬한 다음 출력하는 프로그램을 작성하시오.
• 첫째 줄에 자리수를 내림차순째 줄에 점의 개수 N (1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개의 줄에는 i번점의 위치 xi와 yi가 주어진다. (-100,000 ≤ xi, yi ≤ 100,000) 좌표는 항상 정수이고, 위치가 같은 두 점은 없다.으로 정렬한 수를 출력한다.
• 첫째 줄부터 N개의 줄에 점을 정렬한 결과를 출력한다.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Step_7 {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		int n = Integer.parseInt(br.readLine());
		StringTokenizer st;
		int[][] arr = new int [n][2];
		for (int i=0; i<n; i++) {
			st = new StringTokenizer(br.readLine());
			arr[i][0] = Integer.parseInt(st.nextToken());
			arr[i][1] = Integer.parseInt(st.nextToken());
		}
		Arrays.sort(arr, (o1, o2)-> {
			if (o1[0]==o2[0]) {
				return Integer.compare(o1[1], o2[1]);
			} else {
				return Integer.compare(o1[0], o2[0]);				
			}
		});
		for (int i=0; i<n; i++) {
			bw.write(arr[i][0]+" "+arr[i][1]+"\\n");
		}
		bw.flush();
		bw.close();
	}
}

A.

• 2차원 배열의 정렬과 관련된 문제이다.
• 각 좌표를 2차원 배열에 대입한다.
• Java의 sort 기능을 사용한다. arr, 뒤에 정렬 방식에 대한 조건을 설정할 수 있다.
• o1,o2는 override의 약자로 비교하여 정렬하기 위한 2 배열을 나타낸다.
• (o1, o2) → { return;}을 이용하여 o1, 02를 조건에 따라 어떻게 리턴 할 것인지 제시할 수 있다.
• Integer.compare(o1[0], o2[0]); = 각 배열의 0번을 비교하여 정렬한다.
• if 내부 조건은 0번이 같을 경우 1번의 값끼리 비교하여 정렬한다.
• else 부분은 0번으로 정렬한다를 나타낸다.

8단계 좌표 정렬하기 2

• 2차원 평면 위의 점 N개가 주어진다. 좌표를 y좌표가 증가하는 순으로, y좌표가 같으면 x좌표가 증가하는 순서로 정렬한 다음 출력하는 프로그램을 작성하시오.
• 첫째 줄에 자리수를 내림차순째 줄에 점의 개수 N (1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개의 줄에는 i번점의 위치 xi와 yi가 주어진다. (-100,000 ≤ xi, yi ≤ 100,000) 좌표는 항상 정수이고, 위치가 같은 두 점은 없다.으로 정렬한 수를 출력한다.
• 첫째 줄부터 N개의 줄에 점을 정렬한 결과를 출력한다.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Step_8 {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		int n = Integer.parseInt(br.readLine());
		StringTokenizer st;
		int[][] arr = new int [n][2];
		for (int i=0; i<n; i++) {
			st = new StringTokenizer(br.readLine());
			arr[i][0] = Integer.parseInt(st.nextToken());
			arr[i][1] = Integer.parseInt(st.nextToken());
		}
		Arrays.sort(arr, (o1, o2)-> {
			if (o1[1]==o2[1]) {
				return Integer.compare(o1[0], o2[0]);
			} else {
				return Integer.compare(o1[1], o2[1]);				
			}
		});
		for (int i=0; i<n; i++) {
			bw.write(arr[i][0]+" "+arr[i][1]+"\\n");
		}
		bw.flush();
		bw.close();
	}
}

A.

• 좌표 정렬하기 1과 같은 방식으로 하되 정렬 방식을 바꿔서 처리한다.
• sort 뒤에 정렬 우선순위로 y좌표에 해당하는 [1]의 값이 같다면 [0]으로 비교, 그 이외는 [1]을 기준으로 정렬하도록 하고 출력한다.

9단계 단어 정렬

• 알파벳 소문자로 이루어진 N개의 단어가 들어오면 아래와 같은 조건에 따라 정렬하는 프로그램을 작성하시오.
  1. 길이가 짧은 것부터
  2. 길이가 같으면 사전 순으로
• 단, 중복된 단어는 하나만 남기고 제거해야 한다.
• 첫째 줄에 단어의 개수 N이 주어진다. (1 ≤ N ≤ 20,000) 둘째 줄부터 N개의 줄에 걸쳐 알파벳 소문자로 이루어진 단어가 한 줄에 하나씩 주어진다. 주어지는 문자열의 길이는 50을 넘지 않는다.
• 조건에 따라 정렬하여 단어들을 출력한다.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;

public class Step_8 {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

		int n = Integer.parseInt(br.readLine());

		String[] arr = new String[n];
		for (int i = 0; i < n; i++) {
			arr[i] = br.readLine();
		}
		Arrays.sort(arr, (o1, o2) -> {
			if (o1.length() == o2.length()) {
				return o1.compareTo(o2);
			} else {
				return Integer.compare(o1.length(), o2.length());
			}
		});
		for (int i = 0; i < n; i++) {
			if(i<n-1&&!arr[i].equals(arr[i+1])) {
			bw.write(arr[i] + "\\n");
			}
		}
		bw.write(arr[n-1] + "\\n");
		bw.flush();
		bw.close();
	}
}

A.

• 정렬 방법은 2가지를 설정한다.
• 길이가 같다면 사전 순으로는 문자열의 정렬을 나타내는 o1.compare(o2)으로 처리한다.
• 길이가 다르다면 integer.compare로 문자열의 길이를 비교하여 처리한다.
• 중복된 단어를 제외해야 하기 때문에 다음 문자열의 값과 같다면(.equals) 출력하지 않는 조건을 설정한다.

10단계 나이 순 정렬

• 온라인 저지에 가입한 사람들의 나이와 이름이 가입한 순서대로 주어진다. 이때, 회원들을 나이가 증가하는 순으로, 나이가 같으면 먼저 가입한 사람이 앞에 오는 순서로 정렬하는 프로그램을 작성하시오.
• 둘째 줄부터 N개의 줄에는 각 회원의 나이와 이름이 공백으로 구분되어 주어진다. 나이는 1보다 크거나 같으며, 200보다 작거나 같은 정수이고, 이름은 알파벳 대소문자로 이루어져 있고, 길이가 100보다 작거나 같은 문자열이다. 입력은 가입한 순서로 주어진다.
• 첫째 줄부터 총 N개의 줄에 걸쳐 온라인 저지 회원을 나이 순, 나이가 같으면 가입한 순으로 한 줄에 한 명씩 나이와 이름을 공백으로 구분해 출력한다.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Step_10 {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st;
		int n = Integer.parseInt(br.readLine());

		String[][] arr = new String[n][2];
		for (int i=0; i<n; i++) {
			st=new StringTokenizer(br.readLine());
			arr[i][0]=st.nextToken();
			arr[i][1]=st.nextToken();
		}
		Arrays.sort(arr,(o1,o2)->{
			
			return Integer.compare(Integer.parseInt(o1[0]), Integer.parseInt(o2[0]));
		});
		for (int i=0; i<n; i++) {
			bw.write(arr[i][0]+" "+arr[i][1]+"\\n");
		}
		
		bw.flush();
		bw.close();
	}
}

A.

• 정보를 2차원 문자열 배열에 대입한다.
• sort의 기준은 o1[0]을 int로 변환한 값을 기준으로 정렬한다.
• 2차원 배열의 경우 [0]을 지정하고 [1]을 지정하지 않은 경우 [1]에 대해서는 입력 순서로 출력하게 된다.

11단계 좌표 압축

• 수직선 위에 N개의 좌표 X1, X2, ..., XN이 있다. 이 좌표에 좌표 압축을 적용하려고 한다.
• Xi를 좌표 압축한 결과 X'i의 값은 Xi > Xj를 만족하는 서로 다른 좌표 Xj의 개수와 같아야 한다.
• X1, X2, ..., XN에 좌표 압축을 적용한 결과 X'1, X'2, ..., X'N를 출력해보자.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Step_11 {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		int n = Integer.parseInt(br.readLine());

		StringTokenizer st = new StringTokenizer(br.readLine());

		int[][] arr = new int[n][2];
		for (int i = 0; i < n; i++) {
			arr[i][0] = Integer.parseInt(st.nextToken());;
			arr[i][1] = i;
		}
		br.close();

		Arrays.sort(arr, (o1, o2) -> {
			return Integer.compare(o1[0], o2[0]);
		});
		int count = 0;
		int temp = arr[0][0];

		for (int i = 0; i < n; i++) {
			if (i > 0 && arr[i][0] != temp) {
				count++;
			}
			temp = arr[i][0];
			arr[i][0] = count;
		}
		Arrays.sort(arr, (o1, o2) -> {
			return Integer.compare(o1[1], o2[1]);
		});
		for (int i = 0; i < n; i++) {
			bw.write(arr[i][0]+"");
			if (i != n - 1) {
				bw.write(" ");
			}
		}
		bw.flush();
		bw.close();
	}
}

A.

• 2차원 배열을 만들어 [i][0]에는 입력 값, [i][1]에는 순번을 위한 i값을 넣어준다.
• 배열을 o1[0]을 기준으로 정렬한다.
• 순번을 체크할 count와 임시 int temp를 [0][0]으로 초기화한다.
• n>0부터 값이 temp 값과 같다면 count를 유지하고 다르다면 count를 증가시키는 조건문을 작성한다.
• temp에 현재 [i][0]값을 저장하고 [i][0]에 count 값을 저장한다.
• [i][1]값을 기준으로 정렬하고 각 값을 출력한다.
• bw.write()는 문자열만을 인식하기 때문에 int 값을 출력하기 위해서는 +””를 붙여서 문자열로 변환 후 출력해야 한다.