[백준] 31003번 언젠가 정렬이 될 수 있으면 좋겠네(파이썬,python)

https://www.acmicpc.net/problem/31003

31003번: 언젠가 정렬이 될 수 있으면 좋겠네.

 

24/02/06 현재 난이도: 골드 1

쓰이는 알고리즘: 위상정렬, 그래프이론,약간의 그리디

내가 생각하는 난이도: 골드 2~ 3

남의 도움을 받았는가?: X

 

※ 위상정렬을 모른다면 위상정렬 알고리즘을 공부하고 풀기를 추천한다.

 

느낀점: 아이디어를 떠올려 위상정렬임을 깨닫기만 한다면 그렇게 어렵지는 않을것같다

단, 위상정렬임을 깨닫는게 쉽지 않았다

 

나의 1감:

우선 이 문제를 처음 봤을 때,  N의 범위가 3000이하이므로  O(N^2 *logN) 으로 그냥 앞뒤 비교하면서 gcd가 1이면 더 큰거를 뒤로 작은것을 앞으로 보내주기만 하면 풀리는거아니야? 라고 생각하고 코딩을 했다

 

테스트케이스를 가볍게 통과했다.

 

그렇게 나온 코드가 이거다.

 

 

결과는당연히... 틀렸습니다

이거를 보고 아 역시 골드1 문제가 이렇게 쉽게 풀릴 리 없지를 느끼고 반례가 뭐가 있을지 고민해 봤다

5

1 4 2 3 6 을 입력으로 줘 봤는데

생각해보면 답이 1 3 4 2 6 이 나와야한다. 그런데 저 코드대로라면 1 4 2 3 6 이 그대로 나온다.

당연하다 저 코드에서는 죽었다 깨어나도 2와 3의 위치를 바꾸지 않는다. 왜냐하면 2가 3보다 작기 때문이다.

어? 그렇다면... 뭐야? 이게 앞에 있는게 더 작더라도 바꿔야할 때가 있는거네... 라는 생각과 함께 나의 알고리즘이

완전히 깨졌다.

 

그리고 나서 한참을 생각했다.. 여기서부터가 생각하기가 그렇게 쉽진 않은 것 같다.

곰곰히 생각해보니 1 4 2 3 6 이 있으면

2와 6은 절대 4를 넘을 수 없고

6은 절대 2와 3을 넘을 수 없다.

그리고  절대 넘을 수 없다라고 위에서 정의한것이 아니라면 모두 넘을 수 있다 라는것을 깨달았다

아...? 이런 문제와 비슷한 줄 세우기 문제를 풀었던 기억이 떠올랐다,

이건 위상정렬이다 이래서 위상정렬이구나!가 머리에서 떠올랐다.( 이런걸 보니 확실히 알고리즘 문제경험이 실력과 직결 되는것 같다.)

 

그렇다면 O(N^2 * log(N))의 시간복잡도가 허용이 되니까(N은 3천 이하) 전부 돌면서 진입차수를 정해주면 되겠다 라는 생각을 하고

 

 

여기까지 코드를 써줬다 (처음에는 리스트안에 있는 숫자만큼 그래프크기를 만들어줄까도 고민했었지만 리스트안에 숫자가 10**9 까지 가능하므로 그건 안되고 리스트안에 숫자는 인덱스로만 접근해야겠다는 생각을 했다)

 

그 다음 heap이 빌 때까지 위상정렬을 돌려주면 게임이 끝나겠다 라고 생각했다

 

결과적으로 나의 마지막 코드는 이렇게 되었다

 

 

 

 

 

사실 나도 처음에 이렇게 깔끔하게 코드를 짜지 못했다.

블로그를 포스팅 하던중 설명을 하던중 잠깐만... 이거 더 간단하게도 되는데?

라고 생각하고 코드를 조금 더 다듬으며 최종적으로 이런 코드가 나오게 되었다.

 

 

  

아직 구현실력이 많이 부족하지만 더욱 열심히 연습하며 성장하자

긴 글 읽어주셔서 감사합니다!