개발 공부~

[정렬] 장난꾸러기 .java 본문

코딩테스트/기타

[정렬] 장난꾸러기 .java

머밍 2024. 11. 10. 09:47

설명

새 학기가 시작되었습니다. 철수는 새 짝꿍을 만나 너무 신이 났습니다.

철수네 반에는 N명의 학생들이 있습니다.

선생님은 반 학생들에게 반 번호를 정해 주기 위해 운동장에 반 학생들을 키가 가장 작은 학생부터 일렬로 키순으로 세웠습니다.

제일 앞에 가장 작은 학생부터 반 번호를 1번부터 N번까지 부여합니다. 철수는 짝꿍보다 키가 큽니다.

그런데 철수가 앞 번호를 받고 싶어 짝꿍과 자리를 바꿨습니다.

선생님은 이 사실을 모르고 학생들에게 서있는 순서대로 번호를 부여했습니다.

철수와 짝꿍이 자리를 바꾼 반 학생들의 일렬로 서있는 키 정보가 주어질 때 철수가 받은 번호와 철수 짝꿍이 받은 번호를

차례로 출력하는 프로그램을 작성하세요.

입력

첫 번째 줄에 자연수 N(5<=N<=100)이 주어진다.

두 번째 줄에 제일 앞에부터 일렬로 서있는 학생들의 키가 주어진다.

키(높이) 값 H는 (120<=H<=180)의 자연수 입니다.

출력

첫 번째 줄에 철수의 반 번호와 짝꿍의 반 번호를 차례로 출력합니다.

예시 입력 1 

9
120 125 152 130 135 135 143 127 160

예시 출력 1

3 8

 

출력해설 : 키 정보 152가 철수이고, 127이 철수 짝꿍입니다.

 

내 풀이

 처음 풀 때는 단순히 철수와 짝이 자리를 바꾼 그 번호를 출력하는 줄 알았는데

예시 출력을 보면 이게 아님을 알 수 있었다...

문제가 이해 안돼서 예시를 여러번 풀어보니 알았다

 

 

입력받은 키 배열(둘이 바꿈)과 오름차순 정렬(선생님이 원한 줄세우기) 에서 다른 부분을 찾으면 된다먼저 다른 값이 철수의 번호이며 다음 다른 값이 짝의 번호이다

 

 

clone() - 깊은 복사

 

  • 얕은 복사 (Shallow Copy): 원본 배열의 참조만 복사하기 때문에, 복사된 배열의 요소를 수정하면 원본 배열에 영향을 끼침
  • 깊은 복사 (Deep Copy): 배열의 각 요소를 새롭게 복사하여 별도의 메모리 공간을 할당하기 때문에, 복사된 배열을 수정해도 원본 배열에는 영향을 미치지 않음

 

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;


public class Main {

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();

        int[] arr = new int[n];

        for (int i = 0; i < n; i++) {
            arr[i] = sc.nextInt();
        }
        
        int ch = 0;//철수
        int jjak = 0;//짝
        //배열 복사
        int[] sorted = arr.clone();
        Arrays.sort(sorted);//원래 배열 복사을 오름차순 정렬
        
        for(int i = 0; i < n; i++) {
            if(arr[i] != sorted[i]) {//같지 않으면
                if(ch == 0) ch = i+1;//번호는 1번부터 시작
                else jjak = i+1;
            }
        }
        System.out.println(ch + " " + jjak);

    }
}

 

 

다른 풀이

정답을 배열이 아니라 먼저 넣은 값이 철수기 때문에 리스트로 구현한 코드이다

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;


public class Main {
	public ArrayList<Integer> solution(int n, int[] arr) {
		ArrayList<Integer> answer  = new ArrayList<>();
		int[] tmp = arr.clone();//깊은 복사
		Arrays.sort(tmp);//오름차순 정렬
		for(int i = 0; i < n; i++) {
			if(arr[i]!=tmp[i]) answer.add(i+1);//번호는 1부터 시작
		}
		
		
		return answer;
	}

    public static void main(String[] args) {
    	Main T = new Main();
        Scanner sc = new Scanner(System.in);
        
        int n = sc.nextInt();
        
        int[] arr = new int[n];
        for(int i = 0; i < n; i++) arr[i] = sc.nextInt();
        
        for(int x : T.solution(n,arr)) System.out.print(x + " ");
        
    }
}

 

 

💡💡

오름차순 정렬을 하면 더 쉽게 풀 수 있는 문제였다

'코딩테스트 > 기타' 카테고리의 다른 글

[정렬] 이분검색 .java  (0) 2024.11.10
[정렬] 좌표 정렬 .java  (0) 2024.11.10
[정렬] 중복 확인 .java  (4) 2024.11.09
[정렬] Least Recently Used .java  (2) 2024.11.09
[정렬] 삽입 정렬 .java  (0) 2024.11.06