백준 1377번 자바

문제

https://www.acmicpc.net/problem/1377

1377번: 버블 소트

 

1. 문제 내용이 처음엔 잘 이해가 안됐다. 결론부터 말하자면 출력의 숫자가 뜻하는 것은 버블정렬이 완료됐을 때 총 몇번의 loop를 돌았는지다.

 

2. 버블정렬을 구현해 문제를 풀면 시간 초과가 발생한다. 시간복잡도가 O(N2)이기 때문이다.

그럼 다른 방식으로 풀어야 하는데 이 때 버블 정렬의 규칙을 이용하면 된다.

버블 정렬은 인접한 인덱스의 값끼리 대소 비교를 하여 스왑을 한다. 배열의 끝까지 스왑을 마치면 배열의 마지막 원소는 정렬이 된 상태다. 

이 때 배열의 오른쪽 방향으로 이동하는 건 배열의 길이 이하에서 임의로 산정되지만 왼쪽으로 이동(스왑될 때 작은숫자가 앞으로 이동)은 한번의 loop에 1만큼만 이동한다.

 

그렇기 때문에 정렬된 배열의 인덱스와 초기의 배열 인덱스의 값을 빼 그 최대값 + 1(정렬을 마친 후 한번 더 loop를 돌아야 정렬이 완전히 됐다는걸 알기때문이다.)을 출력해주면된다.

 

예를 들어

정렬 전

val	2	3	5	1	4
idx	1	2	3	4	5

(중간생략)

정렬 후

val	1	2	3	4	5
idx	4	1	2	5	3

최대값 : 3 

출력 : 4

 

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

public class Main1377 {

	static int N;
	static Pair[] arr;
	
	static class Pair implements Comparable<Pair>{
		private int val;
		private int idx;
		
		public Pair(int val, int idx) {
			this.val = val;
			this.idx = idx;
		}
		
		public int compareTo(Pair p) {
			return this.val - p.val;
		}
	}

	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
		arr = new Pair[N];
		
		for (int i=0; i<N; i++) {
			arr[i] = new Pair(Integer.parseInt(br.readLine()), i);
		}
		
		Arrays.sort(arr);
		int max = 0;
		for (int i=0; i<N; i++) {
			if (max < arr[i].idx - i) {
				max = arr[i].idx - i;
			}
		}

		System.out.println(max + 1);
	}
}

 

정리 : 문제 내용자체는 크게 어렵지 않았다. 다만 Comparable을 구현하는 부분에서 많이 헤맸다. 아직 자바 기본이 부족한듯 하다. 

일단 문제를 풀며 짧게 공부한 내용은

Collections던 Arrays던 기본형, String의 경우 sort를 할 때 기본형은 wrapper클래스에서, String 내부에서 각각 compareTo를 구현한다. 하지만 이 문제와 같은 경우 새롭게 클래스를 만들어 객체를 생성하기 때문에 sort를 사용하려면 반드시 Comparable을 구현하고 compareTo를 오버라이딩해야한다. 

사실 당연한 부분인데 문제푸는데만 급급해 또 기본적인 부분을 놓쳤다. 덩달아 최근 정렬관련 문제들을 풀면서 compare와 관련된 자바지식이 많이 부족하다고 느꼈다.