개요
문제 : 백준 1015. 수열 정렬
백준 1015 : 수열 정렬
[문제 분석]
P[0], P[1], ...., P[N-1]은 0부터 N-1까지(포함)의 수를 한 번씩 포함하고 있는 수열이다. 수열 P를 길이가 N인 배열 A에 적용하면 길이가 N인 배열 B가 된다. 적용하는 방법은 B[P[i]] = A[i]이다.
배열 A가 주어졌을 때, 수열 P를 적용한 결과가 비내림차순이 되는 수열을 찾는 프로그램을 작성하시오. 비내림차순이란, 각각의 원소가 바로 앞에 있는 원소보다 크거나 같을 경우를 말한다. 만약 그러한 수열이 여러개라면 사전순으로 앞서는 것을 출력한다.
[입력]
첫째 줄에 배열 A의 크기 N이 주어진다. 둘째 줄에는 배열 A의 원소가 0번부터 차례대로 주어진다. N은 50보다 작거나 같은 자연수이고, 배열의 원소는 1,000보다 작거나 같은 자연수이다.
[출력]
첫째 줄에 비내림차순으로 만드는 수열 P를 출력한다.
[풀이 전략]
일단, 문제를 읽었을 때, 이해가 잘 안간다.
내 한국어 능력이 문제인지, 문제가 이상한 건지 모르겠다.
풀이 전에 문제를 정리를 해보자.
- A라는 수열이 있고
- 그에 대한 B라는 비내림차순(단조증가)로 정렬된 수열이 있다.
- P는 B에 적용했을때, A가 되는 Index의 수열이다.
즉, B[P[i]] = A[i]
여기서 P[i] 는 두값이 같아지는 Index 이다 .
예시)
N = 3 , A = [2, 3, 1]인 경우
B = [1, 2, 3] 일것이다.
B[P[i]] = A[i] 이여야한다 .
A[0]=2
B[P[0]]= 2
=> P[0] = 1
이런 식으로 유추된다.
따라서, 해당 예시에서 P[i] = [1, 2, 0] 으로 구할 수 있다.
처음 생각했을 때, 생각했던 로직은 다음과 같다
(1) A, B, P 수열을 생성하고 A의 수열을 입력받는다.
(2) B는 A에서 깊은 복사를 받은 후 정렬을 해준다.
(3) 조건문과 반복문을 통해 P[i]의 값을 추정하여 수열을 만든다.
[구현코드]
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
int[] A = new int[N];
int[] P = new int[N];
for (int i = 0 ; i<N ; i++) {
A[i] = sc.nextInt();
}
int[] B = A.clone();
for (int i = 0 ; i< N-1; i++)
for (int j = 0 ; j< N-1; j++) {
if(B[j] > B[j+1]) {
int tmp = B[j];
B[j] = B[j+1];
B[j+1] =tmp;
}
}
for (int i =0 ; i<N ; i++)
for (int j = 0 ; j< N; j++) {
if (A[i]== B[j]) {
P[i] = j;
B[j] = -1;
break;
}
}
for (int i = 0 ; i<N ; i++)
System.out.print(P[i]+" ");
}
}
[다른풀이]
-
Arrays.sort() 사용
원래 본래 풀이에서는 실제 그냥 버블 정렬을 통해서 정렬을 했다. 하지만, Arrays.sort()라는 Java에서 배열을 정렬할 때 사용하는 표준 메서드가 있다.
cf) .clone() : 그냥 '='할당을 하게되면 얕은복사가 되서 해당 문제풀이에서 이슈가 발생한다. 따라서 깊은 복사를 통해서 만들어야지 적절한 문제해결이 가능하다. -
풀이적용
import java.util.Arrays;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
int[] A = new int[N];
int[] P = new int[N];
for (int i = 0 ; i<N ; i++) {
A[i] = sc.nextInt();
}
int[] B = A.clone();
Arrays.sort(B);
for (int i =0 ; i<N ; i++)
for (int j = 0 ; j< N; j++) {
if (A[i]== B[j]) {
P[i] = j;
B[j] = -1;
break;
}
}
for (int i = 0 ; i<N ; i++)
System.out.print(P[i]+" ");
}
}
오늘은 머리가 아팠던 런치야미 끝
