본문 바로가기

문제 풀기/코딩인터뷰

[코딩인터뷰 완전정복] 1.1 중복이 없는가

문자열이 주어졌을 때, 이 문자열에 같은 문자가 중복되어 등장하는지 확인하는 알고리즘을 작성하라.

 

해법1

- 문자열의 처음부터 한 문자씩 순회하며

자료구조(스텍, 큐 등)에 입력된 문자열을 저장한뒤

새로운 문자를 확인 할 때마다 자료구조를 순회하며 중복되는 문자가 있는지 확인한다.

public bool IsDuplicate(char[] str){
   var inputStack = new Stack<char>();
   foreach(var ch : str){
      foreach(var stackChar : inputStack){
         if(ch==stackChar) return true;
      }
      inputStack.add(ch);
   }
   return false;
}

 

해법2

- 입력문자의 갯수만큼의 크기를 가진 char 배열을 생성한다.

하나의 문자와 배열의 공간 1개를 매핑시켜 해당 문자가 들어오면 플레그를 올려준다.

플레그가 올라간 문자가 입력되면 중복.