기억보단 기록을

이 문제는 입력 받은 숫자 만큼 문자열을 한글자씩 반복하여 붙이는 작업을 요구하는 문제이다. 그렇기 때문에 StringBuilder를 사용하면 아주 편리하다. StringBuilder에 대해 잘 모른다면 아래 자세히 설명해 놓았으니 참고바란다.

ckprk.tistory.com/21?category=957523

아래는 내가 짠 코드이다 

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;

public class Main {

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		int n = Integer.parseInt(br.readLine());

		for(int t=0; t<n; t++) { //테스트케이스 수
			StringTokenizer st = new StringTokenizer(br.readLine());
			int r = Integer.parseInt(st.nextToken()); //r번 반복
			String str = st.nextToken(); //문자열
			StringBuilder sb = new StringBuilder(); //반복할 때마다 붙여넣기 위해 StringBuilder 사용

			for(int i=0; i<str.length(); i++) {
				for(int j=0; j<r; j++) {
					sb.append(str.charAt(i)); //문자열 첫번째자리부터 r번만큼 반복하여 sb에 붙여줘서 완성시키기
				}
			}
			bw.write(sb + "\n");
			bw.flush();
		}
	}
}

StringBuilder가 무엇인지, StringBuilder의 함수 append의 사용법을 알고 있다면 이 문제는 어렵지 않을 것이다.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;

public class Main {

	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st = new StringTokenizer(br.readLine());
		bw.write(st.countTokens() + "\n");
		bw.flush();
	}
}

이 문제의 핵심은 '42로 나눈 10개의 나머지들을 어떻게 비교할 것 인가'이다.

이런 경우 경우의 수를 배열에 모두 담고 나올때마다 카운팅을 하는 것을 나는 주로 사용한다.

즉, 어떤 수를 42로 나눌 경우 나올 수 있는 나머지는 0~41 이다 그러므로 배열 42개의 크기 만큼 만들어 나머지가 나올 때마다 해당 자리에 카운팅을 해주는 것이다. 

아래 내가 작성한 코드와 주석을 보면 바로 이해할 수 있을 것이다.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

public class Main {

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		int[] arr = new int[42]; //42로 나눴을 때 나머지는 42보다 작을 수 밖에 없으므로 0~41까지 배열을 할당하고 나머지가 발생하면 해당 자리 숫자에 카운트

		for(int i=0; i<arr.length; i++) { // 배열 0으로 초기화
			arr[i]=0;
		}

		for(int i=0; i<10; i++) {
			int num = Integer.parseInt(br.readLine());

			int remainder = num%42; // 42로 나눴을때 나머지를 받는 변수
			arr[remainder]++; //나머지가 발생하여 해당 자리 1증가
		}
		int count = 0;
		for(int i=0; i<arr.length; i++) { // 서로 다른 나머지 값을 카운팅
			if(arr[i]!=0) {
				count++;
			}
		}
		bw.write(count + "\n"); // 출력
		bw.flush();
	}
}

크게 어려울 건 없다

숫자를 받아서 각 자리 숫자를 다 더해주면 된다.

아래 나의 코드와 주석처리된 설명을 보면 금방 이해할 것이다.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

public class Main {

	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        
		int n = Integer.parseInt(br.readLine()); // 숫자의 개수
		String num = br.readLine(); //String 형으로 숫자를 먼저 받음
		int result = 0;
		for(int i=0; i<n; i++) {
			result+=Integer.parseInt(num.substring(i,i+1)); //각 자리를 숫자로 형변환하여 모두 더해줌
		}
		
		bw.write(result + "\n");
		bw.flush();
	}
}

내가 푼 방식은 이러하다 

99이하의 자연수는 모두 한수가 되므로 99이하의 양의 정수가 주어졌을 때는 한수의 개수가 그 양의 정수 값이 된다.

따라서 100이상의 수가 관건이다.

일의자리 숫자, 십의자리 숫자, 백의자리 숫자를 각각 구해서 일의자리 숫자-십의자리 숫자 = 십의자리 숫자-백의자리 숫자를 해주면 한수의 조건이 된다.

아래 내가 코딩한 것을 보면 이해가 될 것이다.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

public class Main {

	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		int n = Integer.parseInt(br.readLine());
		int count=0;
		int d1, d2;
		
		
		if(n<100) {
			bw.write(n + "\n");
			bw.flush();
		}
		else {
			for(int i=100; i<=n; i++) {
				d1 = (i%10)-((i/10)%10); //일의자리 숫자에서 십의자리 숫자를 뺀 값
				d2 = ((i/10)%10)-((i/10)/10); //십의자리 숫자에서 백의자리 숫자를 뺀 값
				if(d1==d2) {
					count++;
				}
			}
			count+=99; //100보다 작은 수는 모두 한수
			bw.write(count + "\n");
			bw.flush();
		}
	}
}

자바에서 String 하면 문자열이 떠오를 것이다.

String str1 = "Hello";

String str2 = " World";

라고 한다면 두개의 객체가 생성되어 각각 하나의 문자열을 가진다.

그리고 이 문자열을 더하는 행위를 했을 때, 또 다른 객체를 생성하여 받아야한다.

String str = str1+str2; //"Hello World" 이렇게 되는 것이다.

이러한 행위는 메모리 할당과 메모리 해제를 발생시키기 때문에 성능이 저하된다.

그래서 대안으로 StringBuilder 가 있는 것이다.

StringBuilder는 새로운 객체를 만들어 줄 필요 없이 하나의 객체에 기존의 문자열을 덧붙이는 방식을 사용하기 때문에 부하가 적으며 상대적으로 속도도 빠르다.

따라서 긴 문자열을 더하는 상황이 발생한다면 StringBuilder를 사용하면 효과적이다.

그러면 StringBuilder의 메소드를 살펴보면서 사용 방법을 소개하겠다.

▶ append - 문자열 추가

StringBuilder sb = new StringBuilder();
sb.append("Hello").append(" World");
System.out.println(sb);

Hello World

▶ delete - 문자열 제거

StringBuilder sb = new StringBuilder();
sb.append("Hello").append(" World");
System.out.println(sb);
		
sb.delete(2, 4); //2번자리에서 4번자리 전까지 (2,3번 자리 문자 제거)
System.out.println(sb);

Hello World
Heo World

▶ deleteCharAt - 특정 문자만 제거

StringBuilder sb = new StringBuilder();
sb.append("Hello").append(" World");
System.out.println(sb);
		
sb.deleteCharAt(5);
System.out.println(sb);

Hello World
HelloWorld

▶ setCharAt - 특정 위치 문자 변경

StringBuilder sb = new StringBuilder();
sb.append("Hello").append(" World");
System.out.println(sb);
		
sb.setCharAt(0, 't');
System.out.println(sb);

Hello World
tello World

▶ insert - 문자열 삽입

StringBuilder sb = new StringBuilder();
sb.append("Hello").append(" World");
System.out.println(sb);
		
sb.insert(5, "!"); //매개변수로 받은 인덱스 위치부터 문자열 삽입
System.out.println(sb);

Hello World
Hello! World

▶ reverse - 문자열 반전

StringBuilder sb = new StringBuilder();
sb.append("Hello").append(" World");
System.out.println(sb);
		
sb.reverse();
System.out.println(sb);

Hello World
dlroW olleH

▶ setLength - 문자열 길이 조절

현재 문자열 길이보다 짧게 설정하면 그 길이 이외의 문자열은 제거됨

현재 문자열 길이보다 길게 설정하면 공백으로 채워짐

StringBuilder sb = new StringBuilder();
sb.append("Hello").append(" World");
System.out.println(sb);
		
sb.setLength(7);
System.out.println(sb);

Hello World
Hello W

import java.util.*;
public class Main
{
	public static void main(String[] args) {
	    Scanner sc = new Scanner(System.in);
	    int n = sc.nextInt();
	    int result=1;
	    for(int i=1; i<=n; i++){ //1부터 n까지
	        result*=i;           //하나씩 곱해서 result에 저장
	    }
	    System.out.println(result);
	}
}

문제를 보고 '너무 간단하잖아? 배열 만들어서 넣고 sort함수 써서 정렬하고 출력하면 되겠네' 라고 생각하고 정답 비율을 보았는데 흠칫했다. 약간의 불안을 안고 코딩을 시작했다.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {

	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	    BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
	    
	    int n = Integer.parseInt(br.readLine());
	    int[] arr = new int[n];
	    
	    for(int i=0; i<arr.length; i++) {
	    	arr[i] = Integer.parseInt(br.readLine());
	    }
	    Arrays.sort(arr);
	    
	    for(int i=0; i<arr.length; i++) {
	    	bw.write(arr[i] + "\n");
	    	bw.flush();
	    }
	}
}

이것이 나의 코드였다. 결과는 당연히(?) 시간초과... 아니 왜?! sort함수 말고 다른 방법이 있단 말인가?

그래서 찾아보았다. 당연히 다른 방법이 있었다. Collections.sort 였다. 하지만 ArrayList를 사용해야했다. 그것은 나에게 문제가 되지 않았다 바로 수정하였다.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.Collections;

public class Main {

	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

		int n = Integer.parseInt(br.readLine());
		ArrayList<Integer> list = new ArrayList<Integer>();

		for(int i=0; i<n; i++) {
			list.add(Integer.parseInt(br.readLine()));
		}
		Collections.sort(list);

		for(int i=0; i<n; i++) {
			bw.write(list.get(i) + "\n");
			bw.flush();
		}
	}
}

결과는 역시(?) 시간초과... 대체 왜이러는 걸까... 다른사람들은 Collections.sort 함수 사용해서 정답처리되었다는데 ...

다시한번 살펴보았다. StringBuilder를 사용하는 것을 볼 수 있었다. 사실 난 StringBuilder를 잘 쓰지 않고 있었다. 그래서 생각해내지 못했던 것 같다. 조만간 StringBuilder에 대해 자세한 설명을 포스팅 해보겠다.

마지막으로 StringBuilder를 사용한 나의 코드이다.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;

public class Main {

	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		int n = Integer.parseInt(br.readLine());
		ArrayList<Integer> list = new ArrayList<Integer>();

		for(int i=0; i<n; i++) {
			list.add(Integer.parseInt(br.readLine()));
		}
		Collections.sort(list); // 오름차순으로 정렬

		for(int e : list) { //for each문 사용. 
			sb.append(e).append("\n"); //ArrayList 각 요소 하나하나 StringBuilder 객체 sb에 담고 개행처리
		}
		System.out.println(sb); //sb에 담은 문자열 모두 출력
	}
}

* Collections.sort() 은 Timsort이다. Timsort 의 경우 반복 합병 및 삽입정렬 알고리즘을 사용하는데, 이렇게 두 가지가 섞여있는 정렬 알고리즘을 hybrid stable sorting algorithm 이라고 하는데, 합병정렬(Merge Sort)의 경우 최선, 최악 모두 O(nlogn) 을 보장하고. 삽입정렬(Inser tsort)의 경우 최선의 경우는 O(n) , 최악의 경우는 O(n2) 이다.

​ 즉, 합병정렬의 최악의 경우와 삽입정렬의 최선의 경우를 짬뽕한 알고리즘이 Timsort 라는 것이다. 실제로 파이썬이나 기타 정렬 알고리즘에서 가장 많이 쓰이는 알고리즘이기도 하다.

시간복잡도 O(n) ~ O(nlogn) 을 보장한다는 장점이 있다고 한다.