코딩 인터뷰 완전 분석 1.1. 중복이 없는가

문제 이해

- 같은 문자가 중복되어 등장하는지 확인하라

- 자료구조를 추가로 사용하지 않고 풀 수 있는 알고리즘을 고민하라 

 

해결 전략

- 배열을 사용해서 문자를 저장해서 중복을 확인한다. 

- 배열을 사용하지 않으려면, 문자열을 정렬한 후 이웃하는 문자 중 같은 문자가 있는지 확인한다.

-> 문자열을 정렬할 때는, 문자열을 char형 배열로 변환해서 정렬한 후, 

    다시 char형 배열을 문자열로 변환한다.  

 

구현

1) 배열 사용

import java.util.*;
public class Main {	
	public boolean solution(String s){
	
	   int[] arr = new int[30];
	   
	   for(int i=0; i<s.length(); i++){
	       int pos = s.charAt(i)-97;
	       arr[pos] += 1;
	   }
	   
	   for(int i=0; i<26; i++){
	       if(arr[i] >= 2){
	           return true;
	       }
	   }
	     
	   return false;
	}

	public static void main(String[] args){
		Main T = new Main();
		Scanner kb = new Scanner(System.in);
		String str=kb.next();
		System.out.println(T.solution(str));
	}
}

2) 배열 사용 X

import java.util.*;
public class Main {	
	public boolean solution(String s){
	
	   char[] stringToChar = s.toCharArray();
	   Arrays.sort(stringToChar);
	   String sortedStr = new String(stringToChar);
	   
	   for(int i=0; i<sortedStr.length()-1; i++){
	       if(sortedStr.charAt(i) == sortedStr.charAt(i+1)){
	           return true;
	       }
	   }
	     
	   return false;
	}

	public static void main(String[] args){
		Main T = new Main();
		Scanner kb = new Scanner(System.in);
		String str=kb.next();
		System.out.println(T.solution(str));
	}
}

 

피드백

- Java에서 문자열을 정렬할 때는, 문자열을 배열로 변환해서 정렬한 후,

  다시 문자열로 변환해야 한다.