자바(Java) 알고리즘 문제풀이 입문: 코딩테스트 대비(문자열_단어 뒤집기)

 

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

OnlineJudge

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

 

4. 단어 뒤집기

 

 

예시 입력 1 

3
good
Time
Big

예시 출력 1

doog
emiT
giB

 

 

내가 푼 풀이 (Time: 114ms, Memory: 26MB)

- for 문으로 문자열을 거꾸로 돌려서 StringBuilder에 붙여줬다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {

    public String solution(String str) {

        StringBuilder sb = new StringBuilder();
        for (int i = str.length() - 1; i >= 0 ; i--) {
            sb.append(str.charAt(i));
        }
        return sb.toString();
    }

    public static void main(String[] args) throws IOException {
        Main main = new Main();
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int num = Integer.parseInt(br.readLine());
        for (int i = 0; i < num; i++) {
            String str = br.readLine();
            System.out.println(main.solution(str));
        }
    }
}

 

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

- StringBuilder의 reverse()함수를 사용했다!

 

- String이라는 객체가 있음에도 불구하고 StringBuilder를 왜 만드는지 구글링해보세요!

- String더하기 연산이나 String의 replace()함수는 새로운 객체를 계속 만들어져서 메모리가 올라가기 때문에 생겼다.

- StringBuilder는 추가한다거나 삭제한다거나 대체한다거나 해도, 처음 만들어진 객체 하나로 하기 때문에 메모리 낭비도 없고, 무겁지도 않아진다

- 하지만 reverser()함수는 문자열 전체를 뒤집는것이기 때문에, 특정 문자만 교환해서 뒤집기 위해서는 아래 방식을 사용해야한다.

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

public class Main {

    public ArrayList<String> solution(int n, String[] str) {

        ArrayList<String> answer = new ArrayList<>();
        for (String x : str) {
            String tmp = new StringBuilder(x).reverse().toString();
            answer.add(tmp);
        }

        return answer;
    }

    public static void main(String[] args) {
        Main main = new Main();
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        String[] str = new String[n];
        for (int i = 0; i < n; i++) {
            str[i] = sc.next();
        }
        for (String x : main.solution(n, str)) {
            System.out.println(x);
        }
    }
}

 

강의 답안 2 (Time: 160ms, Memory: 27MB Lang: Java)

- 꼭 외워야 하는 알고리즘이다

- 특정 조건에 맞는것만 뒤집어라 했을때는 아래 방식을 사용해야 한다.

- 짝궁끼리 뒤집는 방법이다.

- 바꾸고 나서 lt와 rt는 하나 씩 증가, 감소하면 된다.

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

public class Main {

    public ArrayList<String> solution(int n, String[] str) {

        ArrayList<String> answer = new ArrayList<>();

        for (String x : str) {
        	// 1. 문자열을 문자 배열로 만들어준다.	
            char[] s = x.toCharArray();
            // lt는 시작 문자, rt는 맨끝 문자.
            // lt와 rt를 하나씩 바꿔주기 위한 변수 초기화이다.
            int lt = 0, rt = x.length()-1;
            // lt가 rt보다 작을때만 바꿔주다가, 같아지면 while문을 멈춰주면 된다.
            while (lt < rt) {
                char tmp = s[lt];
                s[lt] = s[rt];
                s[rt] = tmp;
                // lt는 증가, rt는 감소
                lt ++;
                rt --;
            }
            // 문자열 리스트에 넣어줘야하니까 문자를 문자열로 형변환한다.
            // 객체. 이 아니라 클래.으로 valueOf에 접근한다.
            // valueOf는 static으로 선언된 클래스 메소드다
            String tmp = String.valueOf(s);
            answer.add(tmp);
        }
        return answer;
    }

    public static void main(String[] args) {
        Main main = new Main();
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        String[] str = new String[n];
        for (int i = 0; i < n; i++) {
            str[i] = sc.next();
        }
        for (String x : main.solution(n, str)) {
            System.out.println(x);
        }
    }
}