문제분석
- 선수 과목의 수강을 고려하여
모든 각 과목들의 이수가 가능한 최소 학기를 구하라 - ( 한 학기에 들을 수 있는 과목 수는 제한없음 )
- ( 모든 과목은 매 학기 항상 개설됨 )
입력 조건
- 첫째 줄 : 과목 수 N(1≤ N≤1000) 선수 조건 수 M(0≤M≤500000)
- 둘째 줄~ : A B (선수과목 수강과목)
- ( 1≤A<B≤N )
출력 조건
- 1번부터 N번까지 이수 가능한 최소 학기를 출력 (각 과목은 공백으로 구분)
#1
Main
- 6번 반복
- a = 1;
- result = find( 1부터6까지 )
- while ( result != 0)
- a ++;
- find( result );
- answer에 a넣기
선수과목 찾기 함수(find)
(매개변수로 과목, 배열을 넣어)
- result = 0;
- 4번 반복
- 배열[i][1] == 과목
- result = Math.max(result, 과목)
- 배열[i][1] == 과목
- result 반환
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sub = new Scanner(System.in);
int x = sub.nextInt();
int y = sub.nextInt();
int[][] subject = new int[y][2];
for(int i=0; i<y; i++) {
subject[i][0] = sub.nextInt();
subject[i][1] = sub.nextInt();
}
String answer = "";
for(int i=0; i<x; i++) {
int a = 0;
int result;
do {
a++;
result = find(subject, i);
} while (result != 0);
answer += i!=x-1 ? a + " " : a;
}
System.out.println(answer);
}
public static int find(int[][] arr, int subject) {
int result = 0;
for(int i=0; i< arr.length; i++) {
result = arr[i][1] == subject ? Math.max(result, subject) : result;
}
return result;
}
}이렇게 코드를 완성 했는데..
콘솔창에서 내 입력값을 안 받아준다
인텔리제이 설정 상의 문제인가 싶어 기본 코드를 입력해봤는데 걔는 받아줌..
뭐가 문제지? -> 무한 루프가 돌아서..
-
result = find(subject, i);
- 해당 코드가 이상함 -> 무한루프
입력값에 변화없이 재귀함수를 쓴 멍청이..😱- result = find(subject, result); 으로 수정
-
result = Math.max(result, 과목)
- 과목 가져와서 다시 과목 보내기 🤐 -> 무한루프
- result = Math.max(result, 선수과목) 으로 수정
- 근데 생각해보니.. max 값을 구한다고 되는 게 아님..
#2
일단 위의 오류사항? 반영..
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sub = new Scanner(System.in);
int x = sub.nextInt();
int y = sub.nextInt();
int[][] subject = new int[y][2];
for(int i=0; i<y; i++) {
subject[i][0] = sub.nextInt();
subject[i][1] = sub.nextInt();
}
String answer = "";
for(int i=1; i<x+1; i++) {
int a = 0;
int result = i;
do {
a++;
result = find(subject, result);
} while (result != 0);
answer += i!=x ? a + " " : a;
}
System.out.println(answer);
}
public static int find(int[][] arr, int subject) {
int result = 0;
for(int i=0; i<arr.length; i++) {
result = arr[i][1] == subject ? arr[i][0] : result;
}
return result;
}
}
- 일단 예제 1 성공..
- 예제 2 실패
- 지금 코드는 마지막으로 언급되는 과목 5만을 고려하기 때문에
1 2 2 1 2 1 를 결과로 출력
- 지금 코드는 마지막으로 언급되는 과목 5만을 고려하기 때문에
#3
Main
- 배열(answer)를 과목수 크기로 만들어 -> 모든 값이 1
- 조건 수만큼 반복
- a = 1; // 아랫줄에서 과목명 말고 선수과목을 넣었으니까
- result = subject[i][0](선수과목명); // 그냥 과목명을 넣을 경우, 한 과목에 선수 과목이 두 개 존재할 경우 두 경우를 분리해서 탐색하는 게 불가능함
- do while (result가 0일 때까지)
- a++
- result = find( result )
- answer의 subject[i][1]인덱스에 있는 값과 a를 비교해서 큰 값 넣기
- answer를 문자열로 치환 후 출력
선수과목 찾기 함수(find)
(매개변수로 과목, 배열을 넣어)
- result = 0;
- 조건 수만큼 반복
- 배열[i][1] == 과목
- result = arr[i][0](선수과목)
- 배열[i][1] == 과목
- result 반환
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sub = new Scanner(System.in);
int x = sub.nextInt();
int y = sub.nextInt();
int[][] subject = new int[y][2];
for(int i=0; i<y; i++) {
subject[i][0] = sub.nextInt();
subject[i][1] = sub.nextInt();
}
int[] answer = new int[x];
String end = "";
for(int i=0; i<y; i++) {
int a = 1;
int result = subject[i][0];
do {
a++;
result = find(subject, result);
} while (result != 0);
answer[subject[i][1]-1] = Math.max(answer[subject[i][1]-1], a);
}
for(int i=0; i<answer.length; i++) {
end += answer[i] == 0 ? 1 + " " : answer[i] + " ";
}
end = end.substring(0, end.length() - 1);
System.out.println(end);
}
public static int find(int[][] arr, int subject) {
int result = 0;
for(int i=0; i<arr.length; i++) {
result = arr[i][1] == subject ? arr[i][0] : result;
}
return result;
}
}
과목이 많을수록 시간 복잡도가 쭉쭉 늘어나는 코드긴 해.. 😭
#4
재귀함수
- 함수 내부에서 자신을 참조(호출)하는 함수
- 필수 조건 : 재귀 함수 내부에 재귀의 탈출조건이 있어야 함
- 참고한 블로그
내가 한 건 재귀가 아니라 냅다 반복한 거였음..
import java.util.Scanner;
public class Main {
static Scanner sub = new Scanner(System.in);
static int x = sub.nextInt();
static int y = sub.nextInt();
public static void main(String[] args) {
int[][] subject = new int[y][2];
for(int i=0; i<y; i++) {
subject[i][0] = sub.nextInt();
subject[i][1] = sub.nextInt();
}
int[] answer = new int[x];
String end = "";
for(int i=0; i<y; i++) {
int result = find(subject, subject[i][1]);
answer[subject[i][1]-1] = Math.max(answer[subject[i][1]-1], result);
}
for(int i=0; i<answer.length; i++) {
end += answer[i] == 0 ? 1 + " " : answer[i] + " ";
}
end = end.substring(0, end.length() - 1);
System.out.println(end);
}
public static int find(int[][] arr, int subject) {
for(int i=0; i<y; i++) {
if (arr[i][1] == subject) {
return 1 + find(arr, arr[i][0]);
}
}
return 1;
}
}- 재귀를 제대로 만들어보았으나...
- 여전히 시간초과로 실패
#5
ArrayList
- 배열을 기반으로 한 컬렉션
- 데이터를 추가, 삭제 시 내부에서 동적으로 배열의 길이를 조절
- ArrayList - 나의 기술 블로그
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
public class Main {
static Scanner sub = new Scanner(System.in);
static int x = sub.nextInt();
static int y = sub.nextInt();
static List<Integer>[] presubject = new ArrayList[x];
public static void main(String[] args) {
for(int i=0; i<x; i++) {
presubject[i] = new ArrayList<>();
}
for(int i=0; i<y; i++) {
int subj = sub.nextInt();
int ject = sub.nextInt();
presubject[ject-1].add(subj-1);
}
int[] answer = new int[x];
String end = "";
for(int i=0; i<x; i++) {
answer[i] = find(i, answer);
end += answer[i] + " ";
}
end = end.substring(0, end.length() - 1);
System.out.println(end);
}
public static int find(int subject, int[] answer) {
if (answer[subject] != 0 ) return answer[subject];
int maxN = 1;
for(int pre : presubject[subject]) {
maxN = Math.max(maxN, 1+find(pre, answer));
}
return maxN;
}
}- 진짜.. 힘겹게 맞췄다..
ArrayList<>를 사용해서 과목 인덱스에 각각의 선수 과목을 넣어줌..- 선수 과목이 여러 개인 경우를 고려하여
List<Iteger>[]선언
-> Integer 리스트 요소 각각에 ArrayList를 넣어줬다는 의미
- 선수 과목이 여러 개인 경우를 고려하여
- ArrayList에 대한 개념은 따로 더 자세히 정리할 예정
- 결과적으로, 성공!
I will give it my all (๑•̀o•́๑)ง