[코드트리 조별과제] 4주차 - 객체 정렬 / 재귀 학습

4주차에는 Novice Mid 부분 중 객체 정렬과 재귀에 대해 학습했다.

---

정렬된 숫자 위치 알아내기

유형	문제 경험치	난이도
Novice Mid / 정렬 / 객체 정렬	50xp

[문제링크]에서 문제를 참고하자.

다익스트라 알고리즘을 접해 관련 문제를 풀다보면, 객체 정렬에 대한 내용이 나오곤 한다.
이를 상기시키고자 다시 한번 객체 정렬에 대해 학습했다.

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

class Line implements Comparable<Line>{
	int point;
	int num;
	public Line(int point,int num) {
		this.point = point;
		this.num = num;
	}
	
	public void SetPoint(int point) {
		this.point = point;
	}

	public int compareTo(Line line) {
		if(this.point == line.point) {
			return this.num - line.num;
		}
		return this.point - line.point;
	}
}

public class Main {
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int n = Integer.parseInt(st.nextToken());
		
		int[] arr = new int[n];
		Line[] listSort = new Line[n];
		st = new StringTokenizer(br.readLine());
		
		for(int i=0; i<n; i++) {
			int point = Integer.parseInt(st.nextToken());
			arr[i] = point;
			listSort[i] = new Line(point, i+1);
		}
		
		Arrays.sort(listSort);
		boolean[] visited = new boolean[n];
		
		for(int i=0; i<n; i++) {
			for(int j=0; j<listSort.length; j++) {
				if(!visited[j] && arr[i]==listSort[j].point) {
					System.out.print(j+1+" ");
					visited[j]=true;
					break;
				}
			}
		}	
	}
}

---

원점으로부터의 거리

유형	문제 경험치	난이도
Novice Mid / 정렬 / 객체 정렬	30xp

[문제링크]에서 문제를 참고하자.

사실 객체 정렬은 계속 하다보면 익숙해지기에 딱히 쓸 코멘트가 없다.

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

class Line implements Comparable<Line>{
	int x;
	int y;
	int num;
	public Line(int x,int y,int num) {
		this.x = x;
		this.y = y;
		this.num = num;
	}

	public int compareTo(Line line) {
		if(Math.abs(line.x)+Math.abs(line.y) != Math.abs(this.x)+Math.abs(this.y)){
			return (Math.abs(this.x)+Math.abs(this.y)) - (Math.abs(line.x)+Math.abs(line.y));
		}
		return this.num - line.num;
		
	}
}
public class Main {
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		
		Line[] list = new Line[n];
		StringTokenizer st;
		
		for(int i=0; i<n; i++) {
			st = new StringTokenizer(br.readLine());
			int x = Integer.parseInt(st.nextToken());
			int y = Integer.parseInt(st.nextToken());
			list[i] = new Line(x,y,i+1);
		}
		
		Arrays.sort(list);
		
		for(Line line : list) {
			System.out.println(line.num);
		}
	}
}

---

재귀함수를 이용한 별 출력 2

유형	문제 경험치	난이도
Novice Mid / 재귀함수 / 값을 반환하지 않는 재귀함수	30xp

[문제링크]에서 문제를 참고하자.

재귀의 특징과 작동 방식에 대해 다시 한번 짚고 넘어갈 수 있던 문제이다.

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

public class Main {
	static int n;
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		n = Integer.parseInt(br.readLine());
		
		repeat(n);
	}
	public static void repeat(int cnt) {
		if(cnt==0) {
			return;
		}
		
		for(int i=0; i<cnt; i++) {
			System.out.print("* ");
		}
		System.out.println();

		repeat(cnt-1);
        
		for(int i=0; i<cnt; i++) {
			System.out.print("* ");
		}
		System.out.println();
	}
}

---

재귀함수를 이용한 최댓값

유형	문제 경험치	난이도
Novice Mid / 재귀함수 / 값을 반환하는 재귀함수	30xp

[문제링크]에서 문제를 참고하자.

이 내가 푼 문제 풀이는 사실 조금 잘 못 푼 풀이라고 생각한다.
그렇기에 이 내용은 해설 코드도 함께 첨부한다.

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

public class Main {
	//재귀 문제
	static int n;
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		n = Integer.parseInt(br.readLine());
		int[] arr = new int[n];
		StringTokenizer st = new StringTokenizer(br.readLine());
		for(int i=0; i<n; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}
		
		System.out.println(repeat(arr,n-1,0));
	}
	public static int repeat(int[] arr,int cnt, int ans) {
		if(cnt<0) {
			return ans;
		}
		if(ans < arr[cnt]) {
			return repeat(arr,cnt-1,arr[cnt]);
		}
		else {
			return repeat(arr,cnt-1,ans);
		}
	}
}

굳이 굳이 if문을 덕지덕지 쓴 모습이다...

해설

import java.util.Scanner;

public class Main {    
    public static final int MAX_N = 100;
    
    public static int[] arr = new int[MAX_N];
    
    // a번째 까지 인덱스의 숫자 중에 가장 큰 값을 반환합니다.
    public static int maxValue(int a) {
        if(a == 0)
            return arr[0];
    
        return Math.max(maxValue(a - 1), arr[a]);
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        // 변수 선언 및 입력:
        int n = sc.nextInt();

        for(int i = 0; i < n; i++)
            arr[i] = sc.nextInt();

        System.out.print(maxValue(n - 1));
    }
}

해설 코드가 훨씬 깔끔하고 잘 짰다고 볼 수 있다.
재귀도 종종 풀며 익혀야 할 것 같다.

---