백준 1432번 그래프수정 플래5
거꾸로 풀면 되는 이유
- 진출차수로 풀거나 저장시에 반대로 저장해서 (a->b 라면 b-a) 부터 해서 뒤에서 부터 뽑아내면서 뒤의 숫자부터 채워가는 방식으로 푸는 문제였다.
- 왜 앞에서 부터 순차적으로 작은 수를 채워가면 안되고, 뒤에서부터 큰 수를 채워가면 될까? 의문이 있어서 어제 하루 종일 고민했다.
- 여기서 숫자를 가장 작은 숫자를 뽑는것이 아니라 문제의 핵심은 작은 수 를 앞으로 몰아서 해당 index가 작은 수일 수록 앞으로 오는 것이 핵심이다.
- 앞에서부터 작은 수를 선택해 가며 채워버리면 더 작은 수에 해당하는 수가 더 뒤로 갈 수 있어 정답에서 벗어날 수 있다.
- 그렇기 때문에 뒤에서부터 채운다. 뒤에서부터 채우면
a가 b보다 크다면 a를 선택하게 된다. 그렇다면 c를 가장 앞으로 보내야 하는데 만약 a를 먼저 선택해서 나오는 경로의 경우가 b를 선택했을 때보다 c가 앞쪽에 나오는 경우라면 그 경로대로 쭉 따라가면 되고, 만약 b를 선택했을 때 더 c가 앞으로 갈 수 있는 경우라면 후에 b 경로로 갈아 타야 할 것이다. - 큰 수를 선택하면 이 같은 선택이 자동적으로 일어나는 이유는 a vs b 라는 상황은 b의 진입차수가 0임을 전제한다.
- 그렇기 때문에 b가 2보다 크다고 하면 (b가 2보다 작다면 b를 택할 이유가 없다. 작은 수일 수록 앞으로 가야한다) 언젠가의 2와 b의 경합 (혹은 2보다 큰수 vs b의 경함) 에서 더 큰 b를 선택하게 될 것이다.
- 이렇게 큰 수를 선택할 수록 작은 수가 비교대상이 되면서 더 작은 수들은 점점 앞으로 밀리게 된다.
반대로 앞쪽에서부터 수를 채워간다면 작은 수를 선택한다고 하면 (a선택) 
큰 수들이 계속 비교의 대상이 되고, 큰 수들이 뒤로 밀리는 꼴이다.
- 작은수가 앞으로 당겨지는 구조가 아니기 때문에 a보다 큰 b의 경우가 있을 경우 a를 선택하게 되고, 혹 b보다 작은 수들이 a 뒤에 포진하는 경우의 수라고 했을 때 b라는 경로를 선택할 방안이 없다. (가장 작은 인덱스를 가진 c가 b를 선택한 경로에서 더 앞에 옴에도 불구하고)
이해하는데 오래걸렸지만 생각해보면 단순한 문제였던 것 같다. 큰 수를 선택하면서 작은수를 앞으로 밀 수 있다. 작은 수를 선택하면서 큰 수를 뒤로 밀 수는 있어도 작은 수를 앞으로 당길 수는 없다.
번외. sort를 끝에서 부터 해야 하는 이유
-
이 문제에 적용 시킨 못했지만 sort를 끝에서부터 해야 하는 것을 이해했다.
-
혜진 선생님과조원 원영 도영쓰의 도움으로 이해했다. -
여기서 sort를 하는 대상은 집합으로 이해한다. (단순 독립적인 애들의 정렬 문제가 아니다. 집합으로 묶여 있는 애들이기 때문에 뒤에부터 정렬해야 한다. 예를 들어 숫자 1-5로 된 카드를 정렬하세요. 하면 앞에서부터 큰 수를 두면 된다. 각각 독립적인 객체니까)
-
이렇게 있을 때 3이 더 작으니 우리는 아래 집합을 선택하겠지만 결국엔 결과는 2번 인덱스의 위치가 더 앞에 있는 위의 집합이 사전순으로 더 앞서게 된다.
-
저 집합을 뒤에서 부터 선택하게 되면 뒤에일수록 큰 수가 나와야 하니까 위의 집합을 선택해야 한다.
-
묶음으로 있는 대상들을 정렬할 때는 sort를 뒤에서 부터 해야 하는데
- 예를 들어
이렇게 이름과 숫자로 묶음이 된 집합 이 있다고 하면 - sort를 하면 만약 앞에서부터 하면 1-> 2 -> 3 이지만 뒤를 기준으로 또 정렬을 한다고 하면 이것들이 다 바뀌어서 1 -> 3 -> 2가 된다.
- 뒤에서 부터 하면 1-> 3 -> 2가 된 상태에서 1 -> 2 (여기 순서보장, 앞에서 정렬된 순서) -> 3 이므로 1-> 2-> 3 이 된다.
- sort를 하면 stable한 특성 때문에 뒤를 기준으로 정렬해주고 앞을 정렬하면 된다는 것
- 예를 들어
-
기존에 풀었던 문제들 자바로 풀었다 (3)
백준 1432번 문제집 골드2
백준 9470번 Strahler 순서 위상정렬 골드3
백준 9470번 노드사이의 거리 DFS 골드5
spring, java학습