[java] 문제 021 (백준 1517)

문제

버블 소트

 

교재 풀이

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
public class P1517_버블소트2 {
  public static int[] A, tmp;
  public static long result;
  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    int N = Integer.parseInt(br.readLine());
    A = new int[N + 1];
    tmp = new int[N + 1];
    StringTokenizer st = new StringTokenizer(br.readLine());
    for (int i = 1; i <= N; i++) {
      A[i] = Integer.parseInt(st.nextToken());
    }
    result = 0;
    merget_sort(1, N); //병합정렬 수행하기
    System.out.println(result);
  }

  private static void merget_sort(int s, int e) { 
    if (e - s < 1)
      return;
    int m = s + (e - s) / 2;
    //재귀함수 형태로 구현
    merget_sort(s, m); 
    merget_sort(m + 1, e);
    for (int i = s; i <= e; i++) {
      tmp[i] = A[i];
    }
    int k = s;
    int index1 = s;
    int index2 = m + 1;
    while (index1 <= m && index2 <= e) {  //두 그룹을 Merge 해주는 로직 
      if (tmp[index1] > tmp[index2]) {
        A[k] = tmp[index2];
        result = result + index2 - k; // 뒤쪽 데이터 값이 작아 선택되는 경우 결과 값 업데이트
        k++;
        index2++;
      } else {
        A[k] = tmp[index1];
        k++;
        index1++;
      }
    }
    while (index1 <= m) {
      A[k] = tmp[index1];
      k++;
      index1++;
    }
    while (index2 <= e) {
      A[k] = tmp[index2];
      k++;
      index2++;
    }

  }
}

 

내 풀이) 24.6.11에 풀다 말고 슈도 코드만 적음 / 1시간 제한두고

import java.util.*;
import java.io.*;

public class Main
{
	public static void main(String[] args) throws IOExcption{
		첫째 줄에 N(1 ≤ N ≤ 500,000)이 주어진다.
	    다음 줄에는 N개의 정수로 A[1], A[2], …, A[N]이 주어진다. 
	        각각의 A[i]는 0 ≤ |A[i]| ≤ 1,000,000,000의 범위에 들어있다.
	        
        첫째 줄에 Swap 횟수를 출력한다
        접근법
            nlogn 정렬을 사용해서 구한다. 
            저번에 스왑 구할 땐 인덱스 차를 이용함
            일단 지금은 병합 정렬을 이용해보자고 
            병합정렬 구현하면서 
            아이디어가 
                병합정렬의 경우 어떤 원소가 결과 배열에서 이동하면 
                원래 기존 배열의 인덱스에서 결과 배열의 인덱스 차만큼 이동한 게 됨
                인덱스가 이동한 거리를 변수로 만들어서 계속 더한다라 
        슈도코드 
            n을 입력받음 
            n개의 수를 배열로 입력받음 
                인트 배열이고
            
            정합 정렬 함수 구현 (시작점, 끝점 )
                어떤 수가 옮겨진 만큼 ans 변수를 ++한다. 
                
                투 포인터 변수를 선언함 
                
                베이스 코드를 만들고 
                재귀 로직 호출
                    sort(시작점부터 중간까지)
                    sort(중간 다음부터 끝까지)
                
                투 포인터   
                    i=s; 앞 배열 시작점 
                    j=m+1; 뒷 배열 시작점 
                k라는 변수 선언, 초기화는 0으로?
                    res 배열에 채워넣을 때 사용하는 변수 
                
                정렬한 배열 res을 만든다 
                일단 tmp 배열에 기존 배열 복사한다 
                while i<=m && j<=e일 때 
                    a[i], a[j] 비교해서 a[i]가 더 작으면
                        res[k]=tmp[i]
                        i++
                        k++
                        
                        즉 i가 가리키는 거가 있고, 그게 res의 k번째 인덱스에 들어갔다면 
                            k<i라면 -> 왼쪽으로 스왑되었다면 
                            i-k만큼 ans 변수 더해주기 
                        
                    비교해서 a[j]가 더 작으면  
                        res[k]=tmp[j]
                        j++
                        k++
                
                만약 어떤 부분이 남았을 때를 대비해서 
                앞 부분이 남았다?
                    while i<=m 
                        res[k]=tmp[i]
                        i++
                        k++
                    while j<=e
                        res[k]=tmp[j]
                        j++
                        k++
                
                이럼 정렬 완료인데 
                    버블 정렬로 할 때 스왑 횟수를 구해야 하니까 
                    1 2 3 8 /4 5 6 7에서 
                        1이 res 배열의 0번째로 갔다면
                        총 3번 이동한 거임 
                        즉 a에서 인덱스 3에서 res에서 인덱스 0이라 
                        그럼 움직인 거리는 3-0=3임 
                        이런 식으로 한 번 res[k]=tmp[]를 할 때
                        이 로직을 넣으면 됨 
                    ??
                        오름차순 정렬, 즉 재귀로 어느 정도 작은 부분이 오름차순으로 되었을 때 
                        총 배열의 두 부분으로만 나뉘어져 있을 때 그 때 이동한 거리가 
                        아니아니 
                        버블 정렬3 2 8 1 / 7 4 5 6을 보자 
                        23/18/47/56 이렇게 재귀로 되었을 것이고
                            이 때 스왑이 3번 일어난 건가? 버블 정렬일 때? 
                        1 2 3 8 / 4 5 6 7 
                            1이 2번
                            2는 노 카운트 -> 오른쪽으로 이동한 거니까
                    느낌 왔어 
                        왼쪽으로 이동했을 때 카운트 올리기 
                        적용해보자 

            swap 횟수 출력, ans 변수 출력 
            
	}
}

 

설명

교재 설명 보면 교재 풀이 이해 됨