해당 문제는 기출과 아주 유사하다고 한다.
문제의 유형은 그래프 알고리즘인데 그래프는 두 노드 사이의 관계가 있는 경우 에지로 연결하여 표현하는 추상적이고 일반적인 자료구조이다. 트리는 사이클이 없는 그래프이고 연결리스트는 하나의 경로로 이루어진 트리이므로 가장 단순한 형태의 그래프가 된다.
결론적으로 싸이클을 빨리 찾아 주기를 계산하고 주기를 이용하여 위치를 구해야 된다.
문제는 다음과 같다.
가장 주의해야할 것은 시작 위치, 한시간에 한번 이동하는 것 이 두 가지이고, 풀이방식에서 시작위치와 그래프 인덱스가 굉장히 헷갈린다. 실제 시험 때는 시간이 없으므로 바로 숫자들을 받아적고 그대로 계산해야 시간을 더 절약할 수 있지 그래프를 하나하나 다 그릴 수 없다는 생각이 들었는데 그래프를 그리는 것이 더 헷갈리지 않고 정확도가 올라가지 않을까 하는 생각이 들었다.
풀이방식은 이동횟수 % 주기 값의 인덱스에 위치한 값이다.
예시에 대한 풀이를 정리해보면 다음과 같다.
솔직히 이 문제를 처음보고 저런 공식을 생각해내기 힘들고 조금만 꼬거나 변형하여 출제해도 급박한 상황에서 빠르고 정확하게 풀기는 쉽지 않을 것 같다.
아무튼 결론적으로 생각해보면 그래프만 그려서 빨리빨리 답을 내는 것이 가장 정확하고 그나마 빠르지 않을까 하는 생각이 든다.
그럼 주어진 5개의 문제에 대해 그대로 적용해서 풀어보면 다음과 같은 결과가 나온다.
2번 같은 경우 실수를 했는데 나머지 연산 결과를 그대로 답으로 쓴 경우다. 실전에서 이러한 실수를 한다면 그 날 하루 멘탈잡기가 상당히 힘들 것이다. 그러니 정신똑바로 차리고 푸는 연습을 하여 실전에서도 실수하지 않도록 할 것이다.
