[백준] 9093번 단어 뒤집기

URL

www.acmicpc.net/problem/9093

9093번: 단어 뒤집기

 

문제

문장이 주어졌을 때, 단어를 모두 뒤집어서 출력하는 프로그램을 작성하시오. 단, 단어의 순서는 바꿀 수 없다. 단어는 영어 알파벳으로만 이루어져 있다.

 

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있으며, 문장이 하나 주어진다. 단어의 길이는 최대 20, 문장의 길이는 최대 1000이다. 단어와 단어 사이에는 공백이 하나 있다.

 

출력

각 테스트 케이스에 대해서, 입력으로 주어진 문장의 단어를 모두 뒤집어 출력한다.

 

문제 해석

java로 문제를 푸는 건 처음이라 입출력 함수, 변수 선언, 문자열 관련 함수 등 모르는 부분이 많아서 구글링을 해가면서 문제를 풀었다.

 

문제를 해결해가는 과정은

1. 테스트 케이스의 개수 T 입력

2. T의 갯수만큼 for문 실행

 2-1. 문장 하나 입력 후 저장

 2-2. 공백을 기준으로("\\s"로 입력) 문장 split 한다.

 2-3. split 한 단어의 수만큼 for문을 수행

  2-3-1. 한 단어에서 맨 뒤를 기준으로 한 단어씩 저장한다.

 2-4. 한 단어를 뒤에서부터 모두 출력했다면 공백 문자를 이어서 저장한다.

 2-5. 해당 문장 출력

을 기준으로 잡았다.

 

제출 코드

import java.io.*;

public class Main{
	
public static void main(String[] args) throws IOException
	{
		InputStreamReader ir = new InputStreamReader(System.in); //스트림 생성
		BufferedReader br = new BufferedReader(ir);
		
		String strAry;
		String[] words;
		
		int T =Integer.parseInt(br.readLine()); //integer는 최대한 지양\
		
		//연산
		for(int i=0;i<T;i++) {
			strAry = br.readLine();
			words = strAry.split("\\s");
			strAry="";
			
			for (String wo : words ){
				for(int k=wo.length()-1;k>=0;k--) {
					strAry += (wo.charAt(k));
				}
				strAry += " ";
			}
			
			System.out.println(strAry);
		}
		
	}
}

 

채점 결과

메모리 - 256176KB

시간 - 1204ms

 

초반에는 메모리 초과가 났지만 

String [] 문자열 -> for문 안에서 재사용하여 String 사용

String [][] word -> for문 안에서 재사용으로 1차원 배열로 수정

결과값 문자열 -> 입력 저장 문자열을 재사용

integer 자료형 -> int형으로 수정

단어에서 한 글자씩 추출할 때 char to String 과정 생략

 

위의 과정을 하나씩 적용해가면서 메모리 사용량을 줄였고,

여러 번의 시도 끝에 겨우 정답이 나왔다.

 

 

development

위의 방법은 메모리, 시간 모두 효율이 좋지 않다.

이 문제를 해결하는 다른 방법으로 reverse함수를 활용하는 것과 stack을 활용하는 방법이 있다.

 

reverse 함수

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

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		
		int a = Integer.parseInt(in.readLine());
		
		String str = "";
		for(int i=0; i<a; i++) {
			str = in.readLine();
			
			String[] arr = str.split(" ");
			for(int j=0; j<arr.length; j++) {
				StringBuffer buf = new StringBuffer(arr[j]);
				System.out.print(buf.reverse() + " ");
			}
			System.out.println();
		}
	}
}

 

출처 - bluemoon-clover.tistory.com/48

메모리 - 63220KB

시간 - 1524ms

 

메모리 사용량은 크게 줄었지만 시간은 오히려 늘어났다.

코드의 전체적인 흐름은 제출 코드와 유사하지만, 한 단어를 뒤집어서 출력하는 부분이 다른 것을 볼 수 있다.

 

InputStreamReader의 StringBuffer 클래스 함수인 reverse()를 사용하면서 for문을 하나 없앴고, 

정답 문자열을 따로 저장하지 않고, 바로 출력하였다.

 

stack

import java.io.*;
import java.util.Stack;
 
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); // reader 생성
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out)); // writer 생성
        Stack<Character> stack = new Stack<Character>(); // Stack 생성
        String input = ""; // String 입력받을 변수 선언
 
        String nStr = br.readLine();
        int n = Integer.parseInt(nStr);

        for (int i = 0; i < n; i++) {
            input = br.readLine();
            input += "\n"; // 마지막을 의미할 개행문자 하나를 추가
            StringBuilder sb = new StringBuilder(""); // char들을 더할 StringBuilder 생성
 
            for (int j = 0; j < input.length(); j++) {
                if (input.charAt(j) == ' ' || input.charAt(j) == '\n') { // 띄어쓰기를 만난 경우
                    while (!stack.isEmpty()) { // stack이 빌 때 까지
                        sb.append(stack.peek()); // stack의 가장 윗 값을 sb에 더하고
                        stack.pop(); // stack을 비운다
                    }
                    // stack이 모두 비고 마지막이 아니면 띄어쓰기도 더한다.
                    // 마지막에 띄어쓰기나 줄바꿈이 안붙게 추가
                    if (input.charAt(j) == ' ') {
                        sb.append(input.charAt(j));
                    }
 
                } else { // 문자인 경우스택에 집어넣는다
                    stack.push(input.charAt(j));
                }
            }
            bw.write(sb.toString() + "\n"); // 그렇게 모인 sb를 출력하고
        }
        br.close();
        bw.flush();
        bw.close();
        // reader와 writer를 닫는다
    }

}

출처 - takeknowledge.tistory.com/46

메모리 - 77148KB

시간 - 848ms

 

메모리와 시간 모두 크게 줄어든 것을 볼 수 있다.

 

입력 버퍼와 출력 버퍼를 모두 생성하였고, 

import java.util.Stack를 통해 Stack 자료구조를 사용했다.

 

 

입출력 버퍼

// reader 생성
BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); 

// writer 생성
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        
// reader 닫기
br.close();

// writer 닫기
bw.flush();
bw.close();

 

 

Stack 생성

 Stack<Character> stack = new Stack<Character>();

<> 안에 사용할 자료형을 입력

 

한 번에 한 줄을 모두 읽고,

문장의 한 글자씩 비교하여 공백 문자일 경우와 일반 문자일 경우를 구분하였다.

일반 문자일 경우 스택에 집어넣고,

공백 문자일 경우 결과값에 ' '를 저장한다.

 

 

Stack 관련 함수

stack.isEmpty() - 스택이 비어있는지 확인(1 : 값이 존재, 0: 값이 없음)

stack.push() - 스택에 값 입력

stack.peek() - 가장 최근에 보관한 값 단순 참조

stack.pop() - 가장 최근에 보관한 값 꺼내고 반환

stack.search() - 매개변수 값이 몇 번째 보관한 요소인지 출력

 

 

StringBuilder

 

StringBuilder는 concat 또는 + 를 대신하기 위해 사용한다.

위의 2가지를 사용했을 경우 기존 값을 버리고 새로운 값을 할당하기 때문에 속도가 느려지게 된다.

 

StringBuilder 주요 메소드

메소드	설명
sb.append(값)	StringBuffer, StringBuilder 뒤에 값을 붙인다
sb.insert(인덱스, 값)	특정 인덱스부터 값을 삽입한다
sb.delete(인덱스, 인덱스)	특정 인덱스부터 인덱스까지 값을 삭제한다
sb.indexOf(값)	값이 어느 인덱스에 들어있는지 확인한다
sb.substring(인덱스, 인덱스)	인덱스부터 인덱스까지 값을 잘라온다
sb.length()	길이 확인
sb.replace(인덱스, 인덱스, 값)	인덱스부터 인덱스까지 값으로 변경
sb.reverse()	글자 순서를 뒤집는다

c언어에서 문자열 다룰 때 시간을 많이 잡아먹었던 기능들인데

java에서는 클래스를 이용하면 된다는 점에서 사용하기 편리한 것 같다.