uk's study

#유형 : 브루트포스, 큐

#난이도 : 골드5

# 큐를 사용하면 생각보다 편하게 접근할 수 있던 문제

# 큐에 1~9를 미리 넣어놓고 헤드부터 poll하면서 num % 10 한 만큼 반복문을 돌려 더하면 된다.

아래의 로직을 잘 생각하면 해결할 수 있다.

# 주의해야할 점은 int 형으로 하면 범위문제로 long으로 접근

for(int i=0; i<num%10; i++)

{

     Arr[idx] = num * 10 + i;

}

Ex) 1 -> 1*10 + 0 = 10

Ex) 2 -> 2*10 + 0 = 20

Ex) 2 -> 2*10 + 1 = 21 

. . . 

# 이 클래스들은 모두 문자열을 저장하고 관리하는 클래스이다.

1) String

String 클래스와 StringBuilder, StringBuilder 클래스의 차이점은 String은 불변하고(immutable), StringBuffer는 가변하다는(mutable) 점이다.

String 객체는 new 연산을 통해 생성되면 할당된 메모리 공간이 변하지 않는다. 따라서 + 연산자 또는 concat같은 메소드를 통해 기존에 생성한 String 객체에 다른 문자열을 추가해도 기존 문자열에 새로운 문자열을 붙이는 것이 아닌 새로운 String 객체를 new로 생성하여 새로운 메모리 공간을 할당받아 연결된 문자열을 저장한다.

즉 String 클래스 객체는 Heap 메모리 영역(가비지 컬렉션이 동작하는 영역)에 생성하여 한번 생성된 객체의 내용을 변화시킬 수 없다. 따라서 많은 연산을 수행하면 계속하여 객체를 만드는 오버헤드가 발생하므로 성능이 떨어진다는 단점이 있다. 하지만 객체가 불변하기 때문에 단순하게 읽는 연산에서는 다른 클래스보다 빠르게 읽을 수 있다는 장점이 있다.(불변하기에 멀티스레드 환경에서 동기화 신경쓸 필요가 없다)

2) StringBuilder, StringBuffer

StringBuilder와 StringBuffer는 가변적이다. 즉 문자열 연산에 있어서 클래스를 한번만 만들고(new), 연산이 필요할 때 크기를 변경시켜서 문자열을 변경한다. 따라서 문자열 연산이 많을 때 사용하면 좋다.

StringBuilder,StringBuffer클래스는 String클래스와 다르게 동작한다. 만약 문자열 연산 등으로 기존 객체의 공간이 부족하게 되는 경우, 기존의 버퍼 크기를 늘리며 유연하게 동작한다. 그리고 StringBuilder와 StringBuffer 클래스가 제공하는 메서드는 서로 동일하다. 

그렇다면 두 클래스 간의 차이점은 무엇일까. 차이점은 StringBuffer는 멀티쓰레드환경에서 synchronized키워드가 가능하므로 동기화가 가능하다. 즉, 동기화의 차이이다. 따라서 StringBuffer는 thread-safe하다. StringBuilder는 동기화를 지원하지 않기 때문에 멀티쓰레드환경에서는 적합하지 않다. 대신 StringBuilder가 동기화를 고려하지 않기 때문에 싱글쓰레드 환경에서 StringBuffer에 비해 연산처리가 빠르다.

**정리하자면 

String클래스는 불변 객체이기 때문에 문자열 연산이 많은 프로그래밍이 필요할 때 계속해서 인스턴스를 생성하므로 성능이 떨어지지만 짧은 문자열을 더할 경우, 조회가 많은 환경, 멀티쓰레드 환경에서 성능적으로 유리하다.

StringBuffer클래스와 StringBuilder클래스는 문자열 연산이 자주 발생할 때 문자열을 추가하기 위한 append() 메서드에 대해서 StringBuffer는 String 보다 월등한 성능을 가지고 있고, 문자열이 변경가능한 객체기 때문에 성능적으로 유리하다.

StringBuffer와 StringBuilder의 차이점은 동기화지원의 유무이고 스레드에 안전한지 여부 관계를 따지지 않는, 동기화를 고려하지 않는 환경에서 StringBuilder가 성능이 더 좋고, 스레드에 안전한 프로그램이 필요한 때, 개발 중인 시스템의 부분이 스레드에 안전한지 모를 경우, 즉 동기화가 필요한 멀티쓰레드 환경에서는 StringBuffer를 사용하는 것이 유리하다.

문자열을 추가하기 위한 append() 메서드에 대해서 StringBuffer는 String 보다 월등한 성능을 보인다. 하지만 toString()메서드에 대해서는 오히려 String객체 생성을 하는 내부적인 처리 때문에, StringBuffer가 String 보다 더 많은 자원을 소모한다.

그에 비하여, String 클래스는 StringBuffer 와 비교하여 인스턴스화를 통하여 객체를 생성할 때 상대적으로 적은 자원을 소모하며, toString() 메서드를 통하여 String 객체로 바꿀 필요가 없다. 이 때문에 StringBuffer 는 하나의 문자열에 대하여 다른 문자나 문자열 추가가 여러 번 행해지는 곳에서 유리하며, 단 한번의 문자열 추가에 대해서는 StringBuffer를 사용하는 것은 오히려 독이다. 

**간단요약**

1. 읽기용 & 공유용도 문자열을 사용 => String

2. 문자열 수정 & 멀티 스레드 환경 => StringBuffer

3. 문자열 수정 & 싱글 스레드 환경 => StringBuffer

#유형 : 스택

#난이도 : 실버4

# ( 와 )  들어올 때 케이스를 나누어서 구현하면 된다. ( 는 앞에 무엇이 있던 스택에 넣을 수 있고, )는 앞에 ( 가 없거나 스택이 비어있다면 넣을 수 없다.

#유형 : 스택

#난이도 : 실버 4

# 스택의 기본 문제, 명령 종류와 조건에 따라 구현하면 된다.

#유형 : 수학, 분할 정복, 재귀

#난이도 : 실버 1

# A,B,C의 값이  2,147,483,647 이하이기 때문에, 단순하게 for문을 돌리면 시간복잡도가 너무 답이 없다. 

여기서 분할 정복의 바탕인 재귀를 사용한다면 어떻게 될까?

2^31이 약 2,147,483,647 이기 때문에, 2,147,483,647 번 돌리는 반복문 댓긴 재귀 방식을 활용하면 31번의 연산으로 퉁칠수 있다.