글 읽기 - 자바로 해결 어떻게 하나요..ㅠㅜ

leejy19908036 6년 전 0

버블소트 과정에서 보여지는 규칙 찾아서 구현을 했는데...ㅠ 시간초과 때문에 ㅠㅜ

자바로는 어떻게 해결할까요..?

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

public class Main{
	public static void main(String args[]) throws IOException{

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int cnt=Integer.parseInt(br.readLine());
		int [] arr = new int[cnt]; //정렬전
		int [] sortArr = new int[cnt]; //정렬후
		
		for(int i=0; i<cnt; i++){ 
			arr[i] = Integer.parseInt(br.readLine());
			sortArr[i] = arr[i];
		}
		
		Arrays.sort(sortArr); 
		int n =0;
		//비교 
		for(int i=1; i<cnt; i++){
			for(int j=i-1; j>=0; j--){
				if((arr[i] != sortArr[i]) && (arr[i] == sortArr[j]))
					n++;
			}
		}
		System.out.println(n);
	}
}

djm03178 6년 전 0

자바라서 안 되는 것이 아니라 어느 언어로도 이 방법으로는 시간복잡도가 O(N^2)이라서 풀 수 없습니다.

시간복잡도에 대한 힌트를 드리자면, 정렬하는 데에만 O(NlogN)이면 되고, 그 후 그 '규칙'을 이용해서 답을 찾는 데에는 O(N)이면 충분합니다.

leejy19908036 6년 전 0

댓글 감사합니다..규칙을 찾았는데 이를 C++은 Vector를 이용했는데 어떤걸 이용해야되는지 잘모르겠어요 ㅠ

djm03178 6년 전 0

구체적으로 C++로 어떻게 짜셨는지 코드를 보여주신다면 자바로 바꾸는 방법도 생각해볼 수 있습니다.

leejy19908036 6년 전 0

제가 짠게 아니라..ㅜ 인터넷에서는 C++로 이런식으로 구현을 했더라고요..

자바로는 어떻게 해결을 해야되는건지 감이 안잡힙니다..

#include <cstdio>

#include <algorithm>

#include <vector>

using namespace std;

int main() {

    int n;

    scanf("%d",&n);

    vector<pair<int,int>> a(n);

    for (int i=0; i<n; i++) {

        scanf("%d",&a[i].first);

        a[i].second = i; // original

    }

    sort(a.begin(),a.end());

    int ans = 0;

    for (int i=0; i<n; i++) {

        // original - changed

        if (ans < a[i].second - i) {

            ans = a[i].second - i;

        }

    }

    printf("%d\n",ans+1);

    return 0;

}

djm03178 6년 전 0

pair를 직접 구현하시면 됩니다. Java가 기본 라이브러리로 제공해주지는 않는 듯 합니다.

대략 이런 식으로 만드시면 됩니다.

import java.util.ArrayList;
import java.util.Comparator;
import java.util.Scanner;

// Pair 클래스 정의
class Pair {
	public int num, index;
	
	public Pair() {
	}
	
	public Pair(int num, int index) {
		this.num = num;
		this.index = index;
	}
}

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int n, i;
		n = sc.nextInt();
		
		ArrayList<Pair> p = new ArrayList<Pair>(n);
		for (i = 0; i < n; i++)
			p.add(new Pair(sc.nextInt(), sc.nextInt()));
		
        // 정렬
		p.sort(new Comparator<Pair>() {
            
            // 정렬 메서드. C++의 pair<int, int>와 같은 규칙으로 정렬
			public int compare(Pair p1, Pair p2) {
				if (p1.num == p2.num)
					return Integer.compare(p1.index, p2.index);
				else
					return Integer.compare(p1.num, p2.num);
			}
		});
		
		for (i = 0; i < n; i++)
			System.out.println(p.get(i).num + " " + p.get(i).index);
	}
}

leejy19908036 6년 전 0

와..정말 감사합니다...

친절하게 알려주셔서 정말 감사해요!!

원하는 형태의 클래스 만들기
ArrayList 활용
Comparator의 활용

알고있다고 생각한 개념들을 활용도 못한점 반성하고 아는게 아는게 아니였네요..

정말 많이 배우고 감사드려요!!

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

문제

문제

출처

ICPC

자바로 해결 어떻게 하나요..ㅠㅜ

leejy19908036 6년 전 0

djm03178 6년 전 0

leejy19908036 6년 전 0

djm03178 6년 전 0

leejy19908036 6년 전 0

djm03178 6년 전 0

leejy19908036 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말