리스트에서 외부 움직임 제거하기

Question

시작 지점에서 끝 지점까지 방향 목록이 있다고 가정 해 봅시다. 불필요한 움직임을 제거하는 효율적인 방법은 무엇입니까? 전체 운동을 2 차원 배열로 그래프로 표시하지 않고도 가능합니까?

e.e. 방향 목록을 따라 진행할 때 두 위치가 서로 옆에 있으면 그 사이의 모든 움직임을 제거 할 수 있습니다 (위치간에 간격이 있으면 단축 할 수 없음). 예 : ... 남쪽, 동쪽, 북쪽 ...은 ... 동쪽 ...으로 축약 될 수 있지만 ... 동쪽, 동쪽, 북쪽 ...은 짧게 할 수 없습니다.

enum Dir 
    { 
     North, 
     South, 
     East, 
     West 
    }; 

Answer 1

enum Dir 
{ 
    North, South, East, West 
} 


static class RedundancyRemover { 

    internal static IList<Dir> RemoveRedundancy(IEnumerable<Dir> listOriginal)  { 

     List<LinkedListNode<Dir>>[] nodeHistory = new List<LinkedListNode<Dir>>[4]; 
     for (int i = 0; i < 4; i++) 
      nodeHistory[i] = new List<LinkedListNode<Dir>>(); 

     LinkedList<Dir> list = new LinkedList<Dir>(listOriginal); 
     LinkedListNode<Dir> curNode = list.First; 

     while (curNode != null) { 
      var curDirInd = (int) curNode.Value; 
      var nextNode = curNode.Next; 

      var oppHistory = nodeHistory[curDirInd^1]; 
      int oppHistCount = oppHistory.Count; 

      if (oppHistCount > 0) { 
       // Has pair - remove this node with its pair 
       list.Remove(curNode); 
       list.Remove(oppHistory[--oppHistCount]); 
       oppHistory.RemoveAt(oppHistCount); 
      } 
      else 
       nodeHistory[curDirInd].Add(curNode); 

      curNode = nextNode; 
     } 

     return list.ToArray(); 

    } 



} 

Answer 2

더 간단한 방법 :

enum Dir 
{ 
    North, South, East, West 
} 

static class RedundancyRemover 
{ 

    static IList<Dir> RemoveRedundancy(IList<Dir> list) { 
     int[] occurenceCount = new int[4]; 

     foreach (var dir in list) occurenceCount[(int)dir]++; 

     var newList = new List<Dir>(); 

     for (int i=0; i<4; i+=2) { 
      int v1 = occurenceCount[i]; 
      int v2 = occurenceCount[i+1]; 
      if (v1 > v2) 
       repeat(newList, (Dir)i, v1 - v2); 
      else 
      if (v1 < v2) 
       repeat(newList, (Dir)(i + 1), v2 - v1); 

     } 

     return newList; 

    } 

    private static void repeat(IList<Dir> list, Dir dir, int count) { 
     while (--count >= 0) list.Add(dir); 
    } 

}