[java] 문제 016 (백준 1377)

문제

버블 소트

 

교재 풀이

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
public class P1377_버블소트1 {
  public static void main(String[] args) throws IOException {
    BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
    int N = Integer.parseInt(reader.readLine());
    mData[] A = new mData[N];
    for (int i = 0; i < N; i++) {
      A[i] = new mData(Integer.parseInt(reader.readLine()), i);
    }
    Arrays.sort(A);//A배열 정렬 O(nlogn)시간 복잡도
    int Max = 0;
    for (int i = 0; i < N; i++) {
      if (Max < A[i].index - i) //정렬 전 index - 정렬 후 index 계산 값의 최대 값을 찾아 저장
        Max = A[i].index - i;
    }
    System.out.println(Max + 1);
  }
}

class mData implements Comparable<mData> {
  int value;
  int index;

  public mData(int value, int index) {
    super();
    this.value = value;
    this.index = index;
  }

  @Override
  public int compareTo(mData o) {//value 기준 오름차순 정렬
    return this.value - o.value;
  }
}

 

 

내 풀이) 24.6.6에 풀고 틀림

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

public class Main
{
	public static void main(String[] args) throws IOException{
	   // bool changed = false;
    //     for (int i=1; i<=N+1; i++) {
    //         changed = false;
    //         for (int j=1; j<=N-i; j++) {
    //             if (A[j] > A[j+1]) {
    //                 changed = true;
    //                 swap(A[j], A[j+1]);
    //             }
    //         }
    //         if (changed == false) {
    //             cout << i << '\n';
    //             break;
    //         }
    //     }
    //     => 위 소스에서 N은 배열의 크기이고, A는 정렬해야 하는 배열이다. 배열은 A[1]부터 사용한다.
    //     => 위와 같은 소스를 실행시켰을 때, 어떤 값이 출력되는지 구해보자.
    //         안쪽 반복문에서 스왑이 되면 -> chabnged가 true가 되는데, 스왑이 안 될 때?
    //         스왑이 안 될 때는 이미 다 오름차순으로 되어 있다는 소리 아닌가
    //             n이 50만이라 버블 소트로 구현하면 시간 초과
    //             기억나는 접근법 있음
    //                 한 번 반복할 때(바깥 반복문) 무조건 한 번밖에 왼쪽으로 안 움직임
    //                 즉 바깥 반복문 반복할 때, 정렬될 때까지 왼쪽으로 움직인 게 제일 많은 걸
    //                 전 인덱스와 정렬 후 인덱스를 비교해서 빼서 구하면 
    //                 그게 움직인 값이 되는 거지. 
        
    //     첫째 줄에 N이 주어진다.
    //         N은 500,000보다 작거나 같은 자연수이다.
    //     둘째 줄부터 N개의 줄에 A[1]부터 A[N]까지 하나씩 주어진다.
    //         A에 들어있는 수는 1,000,000보다 작거나 같은 자연수 또는 0이다.
    //             백만이 50만개라면 10의 6제곱 곱하기 10의 5제곱 정도니 합.. 의미 없나 
    //     입력
    //         5 n이고 
    //         10 a[1]
    //         1 a[2]
    //         5 a[3]
    //         2 a[4]
    //         3 a[5]
    //             입력은 10 1 5 2 3이고
    //             한 번 반복해서 1 5 2 3 10이 됨
    //             두 번 반복할 때 1 2 3 5 10이 됨
    //             세 번 반복할 때 스왑 안 일어남. 오름차순이라 이 때 i의 값이 3이 됨
    //     출력 
    //         3
    //     접근법
    //         기억나는 접근법 있음
    //             한 번 반복할 때(바깥 반복문) 무조건 한 번밖에 왼쪽으로 안 움직임
    //             즉 바깥 반복문 반복할 때, 정렬될 때까지 왼쪽으로 움직인 게 제일 많은 걸
    //             전 인덱스와 정렬 후 인덱스를 비교해서 빼서 구하면 
    //             그게 움직인 값이 되는 거지. 
    //     슈도 코드
    //         n을 입력받음
    //         a 배열을 선언하고
    //             크기는 n로 
    //             자료는 내 사용자 정의 자료형으로 
            
    //         for n번 돌면서 
    //             a에 입력받는 정수값과
    //             해당 index도 같이 입력하기
            
    //         정렬하기 -> sort 함수 이용
    //             sort를 이용하려면 comparator를 지정해줘야 함 
    //             comparator였는지, comparable이었는지 
    //             comparable을 이용하고, comparTo 함수를 오버라이딩해야 함 
                
    //         인덱스 차이를 저장하는 배열 ans 배열 만들고
    //         어떻게 정렬 전 인덱스와 정렬 후 인덱스를 빼지?
    //             정렬 전 인덱스는 a에 넣을 때 같이 저장되어 있지, 내 사용자 정의 자료형으로
    //             그럼 정렬 후엔 넣어진 index값과 현재 배열에 위치한 인덱스가 있을 것이고 
    //             그냥 그걸로 차이 구하면 됨
            
            
    //         자료형
    //             int value
    //             int index
    //             comparTo 함수를 오버라이딩
        
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        
        Node[] a=new Node[n];
        for(int i=0;i<n;i++){
            a[i]=new Node(sc.nextInt(), i);
        }
        
        Arrays.sort(a);
        
        Node[] ans=new Node[n];
        int max=0;
        for(int i=0;i<n;i++){
            ans[i]=new Node(a[i].value, a[i].index -i);
            
            if(max<ans[i].index){
                max=ans[i].index;
            }
            
            // value의 경운 순서대로 오름차순으로 ans에 입력될 거고
            // index의 경우, a에 넣을 때 남겨놓은 인덱스 값이 있다.
            //     그러니 이를 이용하자
            //     ans에 인덱스 저장할 땐, 뭐랄까 ... a의 인덳는 기존 인덱스다.
            //     내가 원하는 건 차이다. 정렬 후 인덱스 - 정렬 전 인덱스?
            //     왼쪽으로 이동하는 걸 카운트하는 거다.
            //     오른쪽으로 이동한 걸 카운트하고 싶다면,
            //     예로 10을 보자. 월랜 {10, 0}인데, 정렬 후엔 {10, 4}이다.
            //         즉 정렬 후 - 정렬 전은 4-0=0이고, 이는 오른쪽으로 이동한 값을 구하는 거다 
            //         그럼 정렬 전 - 정렬 후는? 0 - 4는 -4이고
            //         이게 맞네 
            //     정렬 전 인덱스는 a[i].index고, 정렬 후 인덱스는 반복문 변수 i일 것이다.
            //     즉 1의 경우 1,1 이었는데, 1,0으로 바뀜. 즉 정렬 전 - 정렬 후는 1-0은 1이 됨 
            //     이렇게 다 구한 다음 제일 큰 값을 답으로 출력하면 됨 
        }
        
        System.out.println(max+1);
                // 입력은 10 1 5 2 3이고
                // 한 번 반복해서 1 5 2 3 10이 됨
                // 두 번 반복할 때 1 2 3 5 10이 됨
                // 세 번 반복할 때 스왑 안 일어남. 오름차순이라 이 때 i의 값이 3이 됨
                // 3의 경우 2번 이동했음. 즉 정렬 전 - 정렬 후는 4 - 2=2가 됨 
                // 이 때 주의점은 기존 c++ 코드에선 2 다음 i가 3일 때 출력이 되는 점 고려해서 +1해야 함
        
	}

}

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){
        return this.value-o.value; // 값 기준 오름차순 정렬됨 
    }
    
}

 

설명

        Node[] a=new Node[n];
        for(int i=0;i<n;i++){
            a[i].value=sc.nextInt();
            a[i].index=i;
        }

=> Node 객체를 생성 없이 접근해서 java.lang.NullPointerException가 뜸

 

• 이 코드 백준에 올리니 메모리 초과가 떴음.
  • 내 코드를 교재 정답과 비교하면 내가 불필요하게 ans[]를 만들어서 그런 것 같다고 느낌

 

• 다음 에러가 난 이유와 개념 설명

error: non-static variable this cannot be referenced from a static context
            a[i]=new Node(sc.nextInt(), 1);

1. 정적 메서드 내에서 인스턴스 변수나 메서드를 직접 참조할 수 없습니다.

정적 메서드는 클래스 레벨에서 호출되며 인스턴스를 생성하지 않아도 사용할 수 있습니다. 반면 인스턴스 변수나 메서드는 객체가 생성된 후에만 사용할 수 있습니다. 정적 메서드에서는 인스턴스 변수나 메서드에 직접 접근할 수 없습니다.

 

public class Example {
    int instanceVar = 10; // 인스턴스 변수

    public void instanceMethod() { // 인스턴스 메서드
        System.out.println("This is an instance method.");
    }

    public static void staticMethod() { // 정적 메서드
        System.out.println("This is a static method.");
    }

    public static void main(String[] args) {
        // 정적 메서드에서는 인스턴스 변수나 메서드를 직접 참조할 수 없음
        // instanceVar;  // 오류 발생
        // instanceMethod();  // 오류 발생

        // 인스턴스를 생성한 후에는 접근 가능
        Example example = new Example();
        System.out.println(example.instanceVar); // 접근 가능
        example.instanceMethod(); // 접근 가능
    }
}

 

네, 정적 메서드인 main에서 정적이 아닌 클래스 Node의 인스턴스를 생성할 수 있습니다. 그러나 여기서 발생한 에러는 다른 이유 때문입니다. 에러 메시지 "non-static variable this cannot be referenced from a static context"는 정적 클래스 내부에서 비정적 내부 클래스를 사용하려고 할 때 발생합니다.

원인 분석

당신의 코드에서 Node 클래스는 Main 클래스의 비정적 내부 클래스입니다. main 메서드는 정적 메서드이기 때문에 비정적 내부 클래스의 인스턴스를 생성할 수 없습니다.

비정적 내부 클래스는 외부 클래스의 인스턴스에 종속되기 때문에, 외부 클래스의 인스턴스가 존재하지 않는 정적 컨텍스트에서는 비정적 내부 클래스를 사용할 수 없습니다.

해결 방법

1. Node 클래스를 정적 내부 클래스로 변경합니다.
2. Node 클래스를 외부 클래스로 분리합니다.

해결 방법 1: Node 클래스를 정적 내부 클래스로 변경

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

public class Main {
    public static void main(String[] args) throws IOException {
    	//~~~
        Node[] a = new Node[n];
        for (int i = 0; i < n; i++) {
            a[i] = new Node(sc.nextInt(), 1);
        }
        //~~~
    }
    
    static class Node implements Comparable<Node> { // 정적 내부 클래스로 선언
  	// ~~~
    }
}

 

해결 방법 2: Node 클래스를 외부 클래스로 분리

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

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

class Node implements Comparable<Node> { // 외부 클래스로 선언
~~~
}