문제 파악
배열의 원소를 최소 횟수로 뒤집어 정렬된 배열을 만드는 문제이다. 배열의 최대 크기가 8이고 배열이 한 번 뒤집힐 때마다 다른 상태가 되며 정렬된 상태로 나아가야 된다는 점에서 착안해 배열의 현재 순서를 string으로 나타내 그래프의 노드로 표현하려고 했다.
이 과정에서 그래프의 순서를 뒤집는 경우의 수 를 따지면서 형변환과 인덱싱에 시간이 너무 많이 소요됐다.
문제 풀이
구현
기본적인 풀이 방식은 내 방식과 같았지만, map 자료형과 reverse 메서드를 이용해 효율적으로 구현하였다. map함수는 key값과 value를 가진 자료 구조로, count라는 메서드로 해당 key를 가진 원소가 있나 확인할 수 있다. map을 선언할 때 key와 value의 자료형을 써주는 데 ,컨테이너 그 자체가 key가 될 수 있기 때문에 이 문제에서 해당 수열을 방문했는지를 확인하는 것이 훨씬 간편해진다. reverse는 컨테이너의 특정 구간을 뒤집어 주는 메서드로 위 문제의 뒤집기 연산과 거의 같다.
최적화
위 방식으로 풀 경우 문제를 해결할 수 는 있지만 1000개라는 테스트 케이스를 시간 제한 안에 통과할 수 는 없다. 따라서 문제의 특징을 이용해 더 효율적인 설계를 해야하는데, 주어진 배열이 어떤 숫자를 가졌던 간에 배열의 원소들 간의 상대적인 대소 관계만 활용하면 한 번 만들어 놓은 최소 경로를 계속 사용할 수 있다는 점을 이용하면 된다.
또한 이 문제는 undirected 그래프기 때문에 시작 정점에서 도착 정점까지 가는 거리와 도착 정점에서 시작 정점까지 가는 거리가 같다.
도착 정점을 기준으로 각 숫자 배열 까지 도달하는 거리를 저장해 두고 주어진 배열에 대해 상대적인 대소 관계를 비교해 같은 형태로 수열을 바꿔준 뒤 저장해 둔 값을 불러오면 된다.
느낀점
map, reverse등 효율적인 자료 구조와 메서드의 활용.
비슷한 특징을 가진 문제들을 일반화 함으로서 중복될 수 있는 계산을 방지
