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

https://cote.inflearn.com/contest/10/problem/01-06

OnlineJudge

(위의 링크는 인프런 로그인 후, 해당 강의를 사지 않으면 접속이 되지 않습니다)

 

 

6. 중복문자제거

 

 

예시 입력 1 

ksekkset

예시 출력 1

kset

 

내가 푼 풀이 (Time: 147ms, Memory: 27MB)

1. 빈 캐릭터타입 리스트를 만들어서, 해당 리스트에 알파벳이 없을 경우에만 해당 문자를 넣어줬다.(중복문자 제거를 위해)

2. 해당 리스트를 순회하면서 StringBuilder에 넣어줬다.

import java.util.ArrayList;
import java.util.Scanner;

public class Main {

    public String solution(String str) {
        StringBuilder sb = new StringBuilder();
        char[] array = str.toCharArray();
        ArrayList<Character> list = new ArrayList<>();
        for (int i = 0; i < array.length ; i++) {
           if (!list.contains(array[i])) {
                list.add(array[i]);
            }
        }
        for (int i = 0; i < list.size(); i++) {
            sb.append(list.get(i));
        }
        return sb.toString();
    }

    public static void main(String[] args) {
        Main main = new Main();
        Scanner sc = new Scanner(System.in);
        String str = sc.nextLine();
        System.out.println(main.solution(str));

    }
}

 

 

강의 답안 (Time: 157ms, Memory: 27MB)

 

- indexOf()를 활용하면 중복 문자를 쉽게 확인 할 수 있다.

- 왜냐하면 indexOf()함수가 제일 처음으로 발견된 인덱스를 리턴하기 때문이다

- 그래서 분기처리할때 해당 인덱스랑 indexOf()로 나온 값이 일치할때만 리턴하면 된다

import java.util.Scanner;

public class Main {

    public String solution(String str) {
        StringBuilder sb = new StringBuilder();
        for(int i=0; i<str.length(); i++) {
        	if(str.indexOf(str.charAt(i)) == i) sb.append(str.charAt(i));
        }
        return sb.toString();
    }

    public static void main(String[] args) {
        Main main = new Main();
        Scanner sc = new Scanner(System.in);
        String str = sc.nextLine();
        System.out.println(main.solution(str));

    }
}

 

 

성능 비교 (GPT)

 

두 코드 조각은 중복되지 않는 문자들만을 남기는 기능을 수행합니다만, 성능 면에서 첫 번째 코드가 더 효율적입니다. 이유는 여러 가지가 있을 수 있습니다.

1. 시간 복잡도:
   • 첫 번째 코드는 중복을 제거하기 위해 O(n) 시간이 소요되고, 추가적으로 리스트에 중복 없는 문자들을 저장하기 위해도 O(n) 시간이 소요됩니다.
   • 두 번째 코드는 각 문자에 대해 indexOf를 호출하므로, 문자열의 길이가 N일 때, 최악의 경우 O(N^2)의 시간 복잡도를 가질 수 있습니다 - indexOf 메서드 호출을 할 때, 호출되는 횟수가 문자의 위치에 따라 선형적으로 증가한다. 따라서 최악의 경우, 문자열 내의 모든 문자에 대해 indexOf 호출을 수행하면 시간 복잡도는 근사적으로 O(1 + 2 + 3 + ... + N)으로 계산할 수 있다. 이는 등차수열의 합 공식을 이용하면 O(N^2)에 해당하는 복잡도가 된다. => for문 안에 있는 indexOf는 O(n^2)
2. 메모리 사용:
   • 첫 번째 코드에서는 중복 없는 문자들을 저장하기 위해 ArrayList를 사용하고 있습니다.
   • 두 번째 코드는 추가적인 데이터 구조를 사용하지 않고 문자열 내에서 탐색을 수행하므로, 메모리 사용이 더욱 효율적입니다.

따라서 첫 번째 코드가 두 번째 코드보다 효율적이며, 문자열 길이가 길어질수록 이 차이는 더 커질 수 있습니다.

----

 

GPT가 말하는대로 for문안에 indexOf()를 사용하면 O(n^2)가 되는게 맞는지 알아봐야할 것 같다.

 

 

참고 링크 :

https://blinders.tistory.com/82

indexOf vs for, 왜 indexOf로 해결되는거지?

https://www.inflearn.com/questions/411957/for-문-안에-indexof를-쓰면-시간복잡도가-어떻게-될까요

for 문 안에 indexOf를 쓰면 시간복잡도가 어떻게 될까요? - 인프런 | 질문 & 답변