강사님과 다른 방식으로 풀었는데 확인 부탁드립니다.

자바(Java) 알고리즘 문제풀이 입문: 코딩테스트 대비

6. 중복문자제거

작성

195

public class Main7 {
  public static String solution(String str) {
	  String answer="";
	  //문자를 카운트한다.
	  //문자가 2개 이상일 경우 그 문자를 지운다.
	  ArrayList<Character> list = new ArrayList<>();
	  for(char a : str.toCharArray()) {
		  if(!list.contains(a)) {
			  list.add(a);
		  }
	  }
	  for(char a : list) {
		  answer += a;
	  }
	  return answer;
  }
  public static void main(String[] args){
	
    Scanner in=new Scanner(System.in);
    String str = in.nextLine();
    
    System.out.print(solution(str)); 
  }
}

문제는 통과했지만 시간복잡도?에 대해 궁금한 것이 있어서 질문드립니다.

제가 한 방법은

1.ArrayList<Character> list를 생성

2.주어진 문장 str을 toCharArray()로 변환.

3.for each문을 실행해 주어진 문장을 한글자씩 list에 담지만 list.contains()를 사용하여 list에 문자가 있다면 제외.

4.마지막으로 String 변수에 저장해 출력.

이런 방식으로 풀었는데 저는 for문을 2번 사용했고 강사님은 for문을 1번 수행했습니다.

만약에 시간제한이 있는 문제라면 제 방식은 문제가 있는걸까요? 시간복잡도에 대해 잘 알지못해서 질문드립니다.

중복문자제거 java 코테 준비 같이 해요!

답변 1

김태원

지식공유자

안녕하세요^^

아래 코드처럼 첫 번째 for문에서 스트링도 완성하면 더 좋은 코드가 될 것 같습니다.

import java.util.*;
public class Main{
  public static String solution(String str) {
	  String answer="";
	  //문자를 카운트한다.
	  //문자가 2개 이상일 경우 그 문자를 지운다.
	  ArrayList<Character> list = new ArrayList<>();
	  for(char a : str.toCharArray()) {
		  if(!list.contains(a)) {
			  list.add(a);
			  answer+=a;
		  }
	  }
	  return answer;
  }
  public static void main(String[] args){
	
    Scanner in=new Scanner(System.in);
    String str = in.nextLine();
    
    System.out.print(solution(str)); 
  }
}

wcsjinn

시간복잡도로 따지면 그냥 for문을 두개 썼다고 크게 성능이 떨어지진 않는걸로 압니다.

일단 강사님이 달아주신 방법이 조금 더 효율적이지만, 질문자님 코드도 for문을 각각 따로 두번도는거라서 시간복잡도에 크게 영향이 가지않을거에요. 왜냐하면 문자열의 길이(n이라고 가정)만큼 즉 O(n)만큼만 돌기때문입니다.

하지만 for문안에 for문이 있는 2중 반복문을 쓰게되면 n만큼 돌면서 다시 안에서 n만큼 돌기때문에 n x n 즉 O(n^)만큼 돌아서 시간복잡도가 커지게됩니다. 일단 제가 알고있는선에서 답변 남겼는데 자세한것은 시간복잡도에대해 따로 공부해보시면 좋을 것 같습니다.

인프런 커뮤니티 질문&답변

강사님과 다른 방식으로 풀었는데 확인 부탁드립니다.