[백준]1517 버블 소트 - 자바/Java

1517번: 버블 소트

🌱풀이

알고리즘

1. 버블 소트로 체크하면 시간 초과 날 것이다.
2. 이전에 병합 정렬에 대해 배웠고, 병합 정렬에서도 swap은 일어나므로 여기서 체크해보자.
3. 일반적인 병합 정렬의 코드에서 카운트 해 줄 변수 result를 선언하고, 얘를 갱신해나가자.
4. result가 갱신되는 위치는 우측 집합이 좌측 집합보다 작아서 수 교환이 일어날 때다.
5. 그냥 result++하면 안되냐고 할 수 있다. 나도 그렇게 했다가 틀렸다.
6. 버블 정렬에서의 swap은 인근의 숫자와 바꾸기 때문에 그렇다. 아래 병합 정렬 코드에서 일어난 swap을 버블 정렬에서 구현하려면 두 숫자의 인덱스 차이만큼 swap이 발생해야 한다. 그래서 바꿀 숫자들의 인덱스의 차를 더해주는 것이다.

메모리 : 95556KB, 시간 : 508ms

package book_algoTEst;

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

public class BOJ_1517 {
	public static int[] A, tmp;
	public static long result;
	public static void main(String[] args) throws NumberFormatException, 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;
		mergeSort(1,N);
		System.out.print(result);
	}
	
	private static void mergeSort(int s, int e) {
		if( e - s < 1) return;
		int m = s+(e-s)/2;
		
		mergeSort(s,m);
		mergeSort(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) {
			if(tmp[index1] > tmp[index2]) {
				A[k] = tmp[index2];
				k++;
				index2++; //얘까 더 작은 인덱스이므로 지나가면 됨
				result = result + index2-k; //오른쪽(뒤 쪽) 데이터가 더 작으므로, switch가 일어난 걸로 인식
			}
			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++;
		}
	}
}

---

🪴코드 리뷰

find는 중간 파티션 인덱스를 찾는 메소드, findIdx는 이진탐색을 구현한 메소드, 답을 구하는 메소드는 update 같은데 무슨 말인지 아직 모르겠다.

🌿메모리 : 95408KB, 시간 : 1620ms

💡 풀이자 : siyamaki

import java.io.BufferedWriter;
import java.io.DataInputStream;
import java.io.IOException;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashSet;

public class Main {
    public static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out), 1024 * 64);
    public static int N;
    public static int[] arr, segTree, idx;
    public static ArrayList<Integer> list;
    public static HashSet<Integer> set;
    public static boolean[] visited;
    public static void main(String[] args) throws Exception {
        FastReader fr = new FastReader();
        N = fr.nextInt();
        idx = new int[500001];

        set = new HashSet<>();
        list = new ArrayList<>();
        list.add(Integer.MIN_VALUE);
        arr = new int[N + 1];
        for(int i = 1; i <= N; i++) {
            arr[i] = fr.nextInt();
            if(!set.contains(arr[i])) {
                list.add(arr[i]);
                set.add(arr[i]);
            }
        }   // 좌표 압축
        segTree = new int[list.size() * 4];
        visited = new boolean[list.size()];
        Collections.sort(list);
        long sum = 0;
        for(int i = 1; i <= N; i++) {
            int idx = findIdx(1, list.size() - 1, arr[i]);
            if(!visited[idx]) {
                visited[idx] = true;
                int f = find(1, list.size(), 1, idx, list.size());
                sum += f;
                update(1, list.size(), 1, idx, 1);
            }
        }
        bw.write(Long.toString(sum));
        bw.flush();
        bw.close();
    }
    public static int find(int start, int end, int idx, int left, int right) {
        if(right < start || end < left) {
            return 0;
        }
        if(left <= start && end <= right) {
            return segTree[idx];
        }
        int mid = (start + end) / 2;
        return find(start, mid, idx * 2, left, right) + find(mid + 1, end, idx * 2 + 1, left, right);
    }
    public static void update(int start, int end, int idx, int target, int value) {
        if(target < start || end < target) {
            return;
        }
        segTree[idx] += value;
        if(start == end) {
            return;
        }
        int mid = (start + end) / 2;
        update(start, mid, idx * 2, target, value);
        update(mid + 1, end, idx * 2 + 1, target, value);
    }
    public static int findIdx(int start, int end, int target) {
        while(start < end) {
            int mid = (start + end) / 2;
            if(list.get(mid) == target) {
                return mid;
            } else if(list.get(mid) > target) {
                end = mid - 1;
            } else {
                start = mid + 1;
            }
        }
        return start;
    }

    public static class FastReader {
        private final DataInputStream din;
        private final int BUFFER_SIZE = 1 << 16;
        private final byte[] buffer;
        private int bufferPointer, bytesRead;

        public FastReader() {
            din = new DataInputStream(System.in);
            buffer = new byte[BUFFER_SIZE];
            bufferPointer = bytesRead = 0;
        }

        public String readLine() throws IOException {
            byte[] buf = new byte[BUFFER_SIZE]; // input line length
            int cnt = 0, c;
            while ((c = read()) != -1) {
                if (c == '\\n') {
                    break;
                }
                buf[cnt++] = (byte) c;
            }
            return new String(buf, 0, cnt);
        }

        public int nextInt() throws IOException {
            int ret = 0;
            byte c = read();
            while (c <= ' ') {
                c = read();
            }
            boolean neg = (c == '-');
            if (neg) {
                c = read();
            }
            do {
                ret = ret * 10 + c - '0';
            } while ((c = read()) >= '0' && c <= '9');

            if (neg) {
                return -ret;
            }
            return ret;
        }

        private void fillBuffer() throws IOException {
            bytesRead = din.read(buffer, bufferPointer = 0, BUFFER_SIZE);
            if (bytesRead == -1) {
                buffer[0] = -1;
            }
        }

        private byte read() throws IOException {
            if (bufferPointer == bytesRead) {
                fillBuffer();
            }
            return buffer[bufferPointer++];
        }
    }
}

---

위의 코드와 같은 것 같다. Segment Tree를 이용한 풀이 같은데, Tree 구조에 대해서 공부하고 난 후에야 이해할 수 있을 것으로 보인다.

🌿메모리 : 89704KB, 시간 : 1208ms

💡 풀이자 : chokim159

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {
	static class Node implements Comparable<Node> {
		int num, index;

		public Node(int index, int num) {
			// TODO Auto-generated constructor stub
			this.index = index;
			this.num = num;
		}

		@Override
		public int compareTo(Node n) {
			if (this.num == n.num)
				return this.index - n.index;
			return this.num - n.num;
		}
	}

	static class SegmentTree {
		// 세그먼트 트리를 구현할 배열
		int[] tree;

		// 생성자에서 세그먼트 트리의 전체노드 수 계산 (즉, 배열 길이)
		SegmentTree(int n) {
			// 트리의 높이 계산, log N 값 올림 후 +1
			double treeHeight = Math.ceil(Math.log(n) / Math.log(2)) + 1;
			// 트리의 노드 수 계산 2^트리의 높이
			long treeNodeCount = Math.round(Math.pow(2, treeHeight));
			// 트리의 길이 설정
			tree = new int[Math.toIntExact(treeNodeCount)];
		}

		// []arr : 세그먼트 트리는 리프노드에 배열 값을 저장.
		// node : 노드 인덱스 (항상 1부터 시작)
		// start, end : 트리의 노드들이 가지는 시작 / 종료 인덱스
		// 세그먼트 트리의 노드 값 초기화, ( insert )
		int init(int[] arr, int node, int start, int end) {
			// 세그먼트 트리의 리프노드인 경우 ( 자식이 없는 경우 )
			if (start == end) {
				// 리프노드에 배열의 값 저장 후 리턴
				return tree[node] = arr[start];
			} else {
				// 기준 : now
				// 자식노드 번호 : *2 , *2+1
				// 리프노드가 아닌 경우에는 자식노드의 값을 더해서 노드의 값 초기화 후 리턴
				return tree[node] = init(arr, node * 2, start, (start + end) / 2)
						+ init(arr, node * 2 + 1, (start + end) / 2 + 1, end);
			}
		}

		// node : node 번호
		// start : 노드가 가지는 합의 시작 인덱스
		// end : 노드가 가지는 합의 끝 인덱스
		// left : 구하려고 하는 배열의 합 구간 시작 인덱스
		// right : 구하려고 하는 배열의 구간 끝 인덱스
		// 배열의 특정 구간 합을 세그먼트 트리로 구하기
		int sum(int node, int nStart, int nEnd, int left, int right) {
			// 노드가 가지는 값의 구간이 구하려고 하는 합의 구간에 속하지 않는 경우 0리턴
			if (nEnd < left || right < nStart) {
				return 0;
			} else if (left <= nStart && nEnd <= right) {
				// 노드가 가지는 값의 구간이 구하려고 하는 합의 구간에 속하는 경우 노드 값 리턴
				return tree[node];
			} else {
				// 그 외는 2가지 경우가 존재
				// 1. 노드가 가지는 값의 구간이 구하려고 하는 합의 구간에 일부는 속하고 일부는 속하지 않는 경우
				// 2. 노드가 가지는 값의 구간이 구하려고 하는 합의 구간을 모두 포함하는 경우
				// 이와 같은 경우에는 자식노드를 탐색해서 값을 리턴
				int nMid = (nStart + nEnd) / 2;
				return sum(node * 2, nStart, nMid, left, right) + sum(node * 2 + 1, nMid + 1, nEnd, left, right);
			}
		}

		public void update(int node, int nStart, int nEnd, int idx, int diff) {
			if (idx < nStart || idx > nEnd)
				return;
			tree[node] = tree[node] + diff;
			int mid = (nStart + nEnd) / 2;
			if (nStart != nEnd) {
				// 리프노트는 이미 변경된 상태이므로 변경할 필요없음!

				update(node * 2, nStart, mid, idx, diff);
				update(node * 2 + 1, mid + 1, nEnd, idx, diff);
			}
		}

	}

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		PriorityQueue<Node> q = new PriorityQueue<>();

		int N = Integer.parseInt(br.readLine());
		StringTokenizer st = new StringTokenizer(br.readLine());
		for (int i = 0, n; i < N; i++) {
			n = Integer.parseInt(st.nextToken());
			q.add(new Node(i, n));
		}

		SegmentTree tree = new SegmentTree(N);
		int[] arr = new int[N + 1];
		tree.init(arr, 1, 1, N);

		long ans = 0;
		int time = -1;
		while (!q.isEmpty()) {
			Node n = q.poll();
			int index = n.index + tree.sum(1, 1, N, n.index + 1, N) - ++time;
			if (index == 0)
				continue;
			tree.update(1, 1, N, n.index, 1);
			ans += index;
		}
		System.out.println(ans);
	}
}

---

두 인덱스끼리의 차이를 더해서 계산하면 되지 않을까? 싶었는데 안됐다. 생각해보니 인덱스가 변경되었다가 제자리로 찾아가는 경우는 반영되지 않았다. 예를들어 3 2 1의 경우 2는 한 번 바뀌지만 해당 값은 카운팅되지 않는다.

🌿틀린 코드

💡 풀이자 : 본인

package book_algoTEst;

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

public class test {
	public static class Node implements Comparable<Node>{
		int value;
		int index;
		Node(int value, int index){
			this.value = value;
			this.index = index;
		}
		@Override
		public int compareTo(Node o) {
			if(this.value == o.value) return this.index - o.index;
			return this.value - o.value;
		}
	}
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		StringTokenizer st = new StringTokenizer(br.readLine());
		Node[] A = new Node[N];
		for(int i = 0; i<N; i++) A[i] = new Node(Integer.parseInt(st.nextToken()),i);
		Node[] tmp = Arrays.copyOf(A, N);
		Arrays.sort(A);
		long result = 0;
		for(int i = 0; i<N; i++) {
			if(tmp[i].index < A[i].index) result += A[i].index - tmp[i].index;
		}
		System.out.println((int)result);
		br.close();
	}
}

---

Conclusion

• 어렵다.. 플레는 확실히 어렵다. 하지만 기본기가 탄탄하면 못 풀 문제는 아니었다.
• 트리 구조도 공부해봐야겠다.