글 읽기 - JAVA 자꾸 틀렸다고 나옵니다. 고수님들의 조언 구합니다..

pts119 6년 전 0

안녕하세요 고수님들..

제가 이 문제를 최대힙 방식을 통해서 구현을 해 봤는데요,

어디가 틀렸는지 도통 모르겠습니다 ㅜㅜ

한번 조언 부탁드리겠습니다~!!

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

class Heap {
    int index;
    int value;
    
    public Heap(int value){
    	this.value += value;
    }
	public Heap(int index, int value) {
		this.index = index;
		this.value += value;
	}
}

public class Main {
	Heap[] heap;
	
	// 우선순위 큐 : 힙정렬로 진행하는 것이 퍼포먼스 제일 좋음
	Main() throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        
        // N : 인원, M : 비교횟수
        String inputStr = br.readLine();
        int N = Integer.parseInt(inputStr.split(" ")[0]);
        int M = Integer.parseInt(inputStr.split(" ")[1]);
        heap = new Heap[N+1];	// Heap정렬
        for(int i=0; i<N+1; i++){
        	heap[i] = new Heap(i+1, 0);	// heap변수 초기화
        }
        for(int i=0; i<M; i++){
        	String nextStr = br.readLine();
            int stuA = Integer.parseInt(nextStr.split(" ")[0]);
            int stuB = Integer.parseInt(nextStr.split(" ")[1]);
    	   heap[stuA-1].value += stuB;
        }

    	// 1. 최대힙 만듦.
        for(int i=(N-1)/2; i>=0; i--){
        	insertHeap(i, N);
        }
        // 2. 루트노드 제외 & 배열크기 줄임
        for(int i=N-1; i>=0; ){
        	sb.append(heap[0].index+ " ");
        	if(i <= 0)	break;
            swapArr(0, i);
            i--;
            insertHeap(0, i);
        }
        
    	System.out.println(sb.toString());
	}
	
	void insertHeap(int cur, int nodeQty){
        while(cur < nodeQty){
            int leftIndex=(cur*2) + 1;
            int rightIndex=(cur*2) + 2;
            int pointer;  // 힙배열 포인터
            // 불완전 이진트리일 경우일 수 있으므로 leftIndex는 '>' 로만 조건 줌.
            if(leftIndex > nodeQty && rightIndex >= nodeQty)   break;  // 자식 인덱스가 노드 인덱스보다 많을 수 없다.

            pointer = cur;  // 이 공식이 다음 if문을 거치고 나서도 true라면, 해당 루트노드는 정렬이 다 끝난 것.
            if(leftIndex <= nodeQty && heap[pointer].value < heap[leftIndex].value){
                pointer = leftIndex;
            }
            if(rightIndex < nodeQty && heap[pointer].value < heap[rightIndex].value){
                pointer = rightIndex;
            }
            if(cur==pointer)    break;

            swapArr(cur, pointer);  // 부모, 좌/우 자식노드들 중 제일 작은 값이 부모노드로 가게 위치변환
            cur = pointer;
        }
	}
	
	void swapArr(int cur, int pointer){
        Heap temp;     // 배열 swap을 위한 임시변수
        temp = heap[cur];
        heap[cur] = heap[pointer];
        heap[pointer] = temp;
    }
	
	public static void main(String[] args) throws IOException {
		new Main();
	}

}

chogahui05 6년 전 0

최대 힙이라..

어떤 기준으로 정렬하셨나요? 이거 순서가 있어서요. 위상 정렬로 풀긴 풀어야 하는데요.

어떤 사람 a를 세웠습니다. 그러면 a 뒤에 서야 하는 사람들은

들어오는 간선이 하나씩 지워지나요?

pts119 6년 전 0

아 위상정렬로 풀어야 하는건가요 생각도 못해봤어요.. ㅎ

제가 푼 방식은 a, b 학생이 있을 때, a가 b보다 앞에 있다면 a의 우선순위를 1 증가시키게 했습니다.

그리고 후에 또 a가 다른 학생과 비교를 해서 또 a가 다른 학생보다 앞에 서 있게 되면 우선순위를 또 1 증가시키게 했구요,

그래서 우선순위가 매겨진 학생들을 최대 힙을 이용해서 내림차순 정렬을 시킨 것입니다..

한마디로 말씀하신것 처럼 간선으로 연결된 LinkedList개념으로 풀지를 않았어요 ㅎ

chogahui05 6년 전 0

아.. 그렇군요.

근데 그렇게 풀면 이런 TC에서는 어떻게 나오나요?

pts119 6년 전 0

결과가 개판으로 나옵니다 ㅋㅋㅋ

제가 잘못생각한것 같으니 위상정렬로 해서 다시 풀어보겠습니다 ㅎ

/* 결과 : 9 1 4 2 7 6 5 8 3 10 */

pts119 6년 전 0

감사합니다. 도움 주신 덕분에 해결했습니다.

위상정렬과 스택을 하드코딩으로 구현 해 보아서 결국 맞았습니다 ㅋ 덕분에 공부 많이 되었습니다

다시 한번 감사드려요~!

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

JAVA 자꾸 틀렸다고 나옵니다. 고수님들의 조언 구합니다..

pts119 6년 전 0

chogahui05 6년 전 0

pts119 6년 전 0

chogahui05 6년 전 0

pts119 6년 전 0

pts119 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말