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

 

 

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

OnlineJudge

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

 

12. 암호

예시 입력 1 

4
#****###**#####**#####**##** 

예시 출력 1

COOL

 

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

1. replaceAll()함수로 특수문자를 1과 0으로 바꿔준다.

2. str을 7자리씩 떼서 list에 담아준다.

3. list를 순환하면서 아스키 넘버로 바꾼 뒤, String으로 형변환(cast)한다.

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

public class Main {

    public String solution(int num, String str) {

        str = str.replaceAll("#", "1");
        str = str .replaceAll("[*]", "0");
        ArrayList<String> list = new ArrayList<>();
        for (int i = 0; i < num; i++) {
            int startIdx = i * 7;
            list.add(str.substring(startIdx, startIdx + 7));
        }

        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < list.size() ; i++) {
            int ascii = Integer.parseInt(list.get(i), 2);
            String tmp = String.valueOf((char) ascii);
            sb.append(tmp);
        }
        return sb.toString();
    }

    public static void main(String[] args) {
        Main T = new Main();
        Scanner sc = new Scanner(System.in);
        int num = Integer.parseInt(sc.next());
        String str = sc.next();
        System.out.println(T.solution(num, str));
    }
}

 

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

 1. substring으로 잘라준걸 바로 replace로 변경한다.

2. StringValueOf()안써도 (char)만 해도 아스키코드가 알파벳으로 변경된다.

3. 2진수를 10진수로 변경할때는 Integer.parseInt()를 사용하면 된다.

4. str에 7를 잘라서 재할당한다.

import java.util.Scanner;

public class Main {

    public String solution(int num, String str) {
        String answer = "";
        for (int i = 0; i < num; i++) {
            String tmp = str.substring(0, 7).replace('#', '1').replace('*', '0');
            int ascii = Integer.parseInt(tmp, 2);
            answer += (char) ascii;
            str = str.substring(7);
        }

        return answer;
    }

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

 

 

성능 비교

주요 차이점은 다음과 같습니다:

1. 문자열 치환:

• 첫 번째 코드 조각은 replaceAll()을 두 번 사용하여 '#'을 '1'로, '*'을 '0'으로 대체합니다. 이 과정에서 대체가 이루어질 때마다 새 문자열을 생성합니다.
• 두 번째 코드 조각은 직접 replace()를 사용하여 '#' 및 '*' 문자를 대체합니다. 기존 문자열을 직접 수정하므로 더 효율적입니다.

2. ArrayList 대 직접 연결:

• 첫 번째 코드 조각은 ArrayList를 사용하여 중간 이진 서브 문자열을 저장하고 이들을 변환하고 추가하는 반면,
• 두 번째 코드 조각은 중간 데이터 구조 없이 'answer' 문자열에 변환된 문자를 직접 추가합니다.

3. 문자열 조작:

• 첫 번째 코드 조각은 substring()를 사용하여 입력 문자열에서 7자씩 서브 문자열을 추출하고 ArrayList에 저장합니다. 이로 인해 추가적인 메모리 및 문자열 조작 작업이 필요합니다.
• 두 번째 코드 조각은 반복적으로 str.substring(0, 7)를 사용하여 입력 문자열에서 7개의 문자를 추출하고, 그런 다음 str = str.substring(7)를 사용하여 해당 문자를 제거합니다. 중간 저장 공간을 사용하지 않습니다.

알고리즘 성능 측면에서:
두 번째 코드 조각은 중간 서브 문자열을 생성하고 ArrayList에 저장하는 작업을 피함으로써 메모리 사용이 더 효율적일 것입니다.두 번째 코드 조각은 문자열 조작을 보다 직접적으로 처리하므로 특히 큰 입력에 대해서 더 나은 성능을 제공할 수 있습니다.

 

일반적으로, 두 번째 코드 조각이 보다 효율적인 접근 방식을 가지고 있어 보입니다.

 

replace() vs replaceAll() 성능 

 

• replace(): 정규식을 사용하지 않고 단순 문자열 대체를 수행하기 때문에 일반적으로 replaceAll()보다 더 빠른 성능을 보입니다.
• replaceAll(): 정규식을 사용하여 문자열을 대체하기 때문에 복잡한 패턴에 대해 치환이 이루어지며, 이로 인해 replace()에 비해 성능이 느릴 수 있습니다.

 

substring()함수의 메모리 낭비

 

• Java에서 substring()을 호출할 때 생성되는 문자열은 새로운 문자열 객체로 Heap 메모리 영역에 저장됩니다. 이렇게 하는 이유는 원래 문자열의 부분 문자열(substring)을 나타내기 위해 메모리 공간을 새롭게 할당해야 하기 때문입니다.
• 원래 문자열의 substring() 연산은 해당하는 인덱스 범위만큼의 문자를 복사하여 새로운 문자열을 생성합니다. 따라서 기존 문자열의 내용을 공유하면서도 새로운 문자열 객체를 만들어 사용하게 됩니다. 이는 문자열 연산 시 원본 문자열의 내용을 보존하면서 부분 문자열을 다룰 수 있도록 해줍니다.

 

참고 링크 :

https://developer-talk.tistory.com/690

[Java]특정 위치의 문자 변경하는 방법

 

 https://yeonyeon.tistory.com/294

[Java] replaceAll 대신 replace 사용하기

https://velog.io/@m1naworld/Java-replace-vs-replaceAll

[Java] replace() vs replaceAll()

https://codingdog.tistory.com/entry/java-replaceAll-메서드-그냥-쓰면-어떤-오버헤드가-걸릴까요

java replaceAll 메서드 : 그냥 쓰면 어떤 오버헤드가 걸릴까요?

 

https://hianna.tistory.com/527

[Java] 10진수 <-> 2진수, 8진수, 16진수로 변환하기

https://developer-talk.tistory.com/663

[Java]문자열에서 특수 문자 제거하는 방법