Hoguz

문자열 s에 나타나는 문자를 큰것부터 작은 순으로 정렬해 새로운 문자열을 리턴하는 함수, solution을 완성해주세요.
s는 영문 대소문자로만 구성되어 있으며, 대문자는 소문자보다 작은 것으로 간주합니다.

대문자는 뒤로, 소문자는 앞으로 정렬하라는 뜻이다.

별 생각없이 선택정렬 연습 겸으로 해서 코드를 구성 했다.

for(int i = 0; i < s.length() ; i++) {

max_num = i;

for(int j = i ; j < s.length() ; j++) {

if((int)lst[j] > (int)lst[max_num]) {

max_num = j;

}

}

너무 간단한 거라 딱히 리뷰할 것도 없긴하다.

한가지 계속 얼탓던 부분이 바로 저 max_num 부분...

선택정렬이 제대로 유지되려면 최고 값 인덱스를 찾아서 이를 바꿔주면서 진행이 되야 하는데

저 부분을 기존에 i로 그대로 쓰니 제멋대로 진행이 됬다.

이래서 역시 코드는 직접 쳐봐야 안다..

/*

두 정수 a, b가 주어졌을 때 a와 b 사이에 속한 모든 정수의 합을 리턴하는 함수, 

solution을 완성하세요. 

예를 들어 a = 3, b = 5인 경우, 3 + 4 + 5 = 12이므로 12를 리턴합니다. */

알고리즘이나 기타 생각할 것도 따로 없고 그냥 풀면 된다

단순히 더하기만 하면 되기때문에 입력크기가 커도 큰 문제 없는듯.

딱 한가지 생각해봐야하는 건 두 수의 차에 따라서 누가 먼저 시작하느냐 그 정도 일뿐..

현재 도전중인 문제..

너무 많은 경우의 수가 있어서 쉽게 접근을 못하는중..

자괴감 느낀다.. 

# 너무 뻔하게 생각을 해서 그런가 안 풀린다.

1차 완성본.

기본 원리는 첫번째 row에서 1을 검색한다.

그리고 1이 연속되는지 확인 한 후 첫번째 인덱스(start), 끝나는 인덱스(end)를 확인 한다.

그리고 두번째 로우부터 이 인덱스 만큼 슬라이싱 된 리스트만을 확인한다.

이때 첫번째 로우에서 start-end+1 한 값, 즉 한변의 길이를 변수로 저장 한 후

두번째 row에서는 더 작은 값이 나오면 update 한다.(정사각형이므로)

lst = [[0,1,1,1],

       [1,1,1,1],

       [1,1,1,1],

       [0,0,1,0]];

lst2 = [[0,0,1,1],[1,1,1,1]];

위 두가지 경우에 한해서는 통과한다.

# 추가

이 문제가 어려운 이유는 무엇일까? 바로 안되는 경우가 발생 할 경우이다.

아마도, 이 문제를 처음 접하는 사람들은 거진 80-90%는 나 처럼 재귀적 형태로 접근 할 것이라 생각한다.

문제는 재귀적 접근을 하게 된다면 일단 매우 느리게 작동하고, 두번째로 안됫을 경우에 수습을 할라면 다시 처음부터 가야한다.

또한 이런식으로 문제를 풀라면 온갖 경우의 수를 다 생각한 다음 그 경우를 다 해결할 수 있는 코드를 짜야한다.

그렇기에 나온 방법이 동적 프로그래밍이다. 코드가 진행되면서 여태까지의 결과를 저장하는 식으로 간다. 

이렇게 짜게 된다면 굳이 다시 돌아갈 필요도 없고 안되는 경우를 따질 필요가 없다.

이러한 방식을 위에 문제에 적용한다면 이렇게 된다.

우선 최소한의 정사각형 사이즈는 몇일까? 2 * 2 , 즉 4이다.

그렇기에 2 * 2, 총 4칸을 보면 된다.

두번째로 4칸을 볼때 무엇을 봐야할까, 1의 갯수? 아니다. 0의 유무를 확인해야한다.

세번째, 그렇다면 이제 끝난것인가? 다음을 보자

1 1   0 1   0 0  0 0

1 1   1 1   1 0  0 0

위 네가지 경우 중 당연히 제일 왼쪽만이 2 * 2 정사각형이고 나머지는 아니다.

그런데 엄밀히 말하면 2번째, 세번째의 경우에는 아니라기 보단 1 * 1 의 정사각형이다.

그렇다면 다시 두번째로 돌아가서, 우리는 0의 유무를 확인해야만 하고 세번째에서 확인을 했는데 이것을 어떻게 기록해야 할까??

if, else if, else if로 다 돌려야 할까? 이렇게 가능하긴 할 텐데 코드도 복잡하고 암튼.. 그래 ㅎㅎ

포인터(현재 위치한 인덱스)를 제외한 나머지 3개의 최소값을 구하고 그 값에다가 +1 만 하면 된다.

이렇게 하면 굳이 0인지 아닌지도 구분할 필요도 없다(포인터는 구분해야한다 성능 향상을 위해)

위에서 첫번째는 2가 되고 이를 포인터에 기록한다!! (동적 프로그래밍에 핵심)

두번째는 1, 세번째도 1(엄밀히 말하면 패스), 네번째도 패스

# 여기서 포인터를 언급하고 넘어가자면 오른쪽 하단, 즉 (1,1) 위치에 있는 숫자를 포인터로 한다.

왜냐하면 앞서 언급했듯이 정사각형 최소 사이즈는 2*2 이므로 이를 리스트에서 확인하기 위해 굳이 0번째 로우부터 할 필요가 없기 때문이다.

0, 1, 1, 1 -> 이 줄부터 확인 할 필요없고

1, 1, 1, 1 -> 여기 이 줄부터 확인하면 된다. 그것도 저 빨간색부터!

0, 1, 1, 1

다시 원래대로 돌아와서... 최소값을 확인하고 거기에 무조건 1을 더해주면 된다.

1 1   0 1   0 0  0 0

1 2   1 1   1 0  0 0 

위에 얘들은 제일 왼쪽 애만 바뀌고 나머지는 안바뀐다.

그리고 이게 반복된다.

그럼 어느 순간 이런 애가 나타 날 것이다.

ex1)

2,2

2,1 -> 1은 포인터라 아직 동적 할당이 안된 상황

이 의미는 무엇일까 즉, 1로 둘러쌓여져 있던 애들이란 뜻이다.

1, 1 ,1

1, 2, 2

1, 2, 1 

ex1) 의 경우를 넓게 보면 바로 위에 처럼 된 상황인 것이다. 그렇기에 ex1)은 동적 할당으로 3이 된다. 포인터를 제외한 나머지 3개에서 최소값을 찾고 거기에 1을 더해주기 때문에.

마지막으로 위에 4*4 예시를 단계별로 표현하고 마무리 하겠다..

0, 1, 1, 1 

1, 1, 1, 1 -> 최소값이 0이라 +1 해도 어차피 1인 상황

0, 1, 1, 1

0, 1, 1, 1 

1, 1, 2, 1

0, 1, 1, 1

0, 1, 1, 1 

1, 1, 2, 2

0, 1, 1, 1

0, 1, 1, 1 

1, 1, 2, 2

0, 1, 2, 1

0, 1, 1, 1 

1, 1, 2, 2

0, 1, 2, 3

/*array의 각 element 중 divisor로 나누어 떨어지는 값을 오름차순으로 정렬한 배열을 반환하는 함수, solution을 작성해주세요.

divisor로 나누어 떨어지는 element가 하나도 없다면 배열에 -1을 담아 반환하세요.

제한사항

arr은 자연수를 담은 배열입니다.

정수 i, j에 대해 i ≠ j 이면 arr[i] ≠ arr[j] 입니다.

divisor는 자연수입니다.

array는 길이 1 이상인 배열입니다.

*/

꼼수? 로 풀었다...

알고리즘 자체는 어렵지 않다. 단지 내가 고민했던 것은 결과들이 순서대로 나오게 하는 것, 정렬 때문에 조금 고민하였으나

다른 풀이들을 보면 크게 고민안한것 같다.

제일 신박했던 풀이는

 return Arrays.stream(array).filter(factor -> factor % divisor == 0).toArray();

람다식 활용 ㄷㄷ... 

올바른 괄호를 찾는 문제. statck 개념을 알고 있다면 회문, 괄호 찾는 문제 등은 쉽게 풀 수 있다.
핵심적은 부분은 
1. 처음엔 ( 왼쪽 볼록 괄호가 와야 한다는 점

2. ) 오른쪽 볼록 괄호가 오면 기존에 있는 ( 왼쪽 볼록 괄호 하나를 없애야 한다는 점.
이렇게 해서 리스트에 size가 0이어야 한다.

(왜냐면 짝에 맞다면 모두 지워졌으니까)

하지만 내가 풀이한 방법은 list를 import 해야 하는데

다른 사람들의 풀이의 경우 단순히 숫자를 count 하여 계산해냈다.

앞뒤를 뒤집어도 똑같은 문자열을 팰린드롬(palindrome)이라고 합니다.
문자열 s가 주어질 때, s의 부분문자열(Substring)중 가장 긴 팰린드롬의 길이를 return 하는 solution 함수를 완성해 주세요.

예를들면, 문자열 s가 abcdcba이면 7을 return하고 abacde이면 3을 return합니다.

getMiddle메소드는 하나의 단어를 입력 받습니다. 단어를 입력 받아서 가운데 글자를 반환하도록 getMiddle메소드를 만들어 보세요. 

단어의 길이가 짝수일경우 가운데 두글자를 반환하면 됩니다.

예를들어 입력받은 단어가 power이라면 w를 반환하면 되고, 입력받은 단어가 test라면 es를 반환하면 됩니다.

기본적인 문제, 길이를 읽고, 짝수 홀수를 확인하고, 인덱스로 자른다.

파이썬과 다른게 있다면 파이썬은 문자->리스트-> 슬라이싱 이렇게 하면 되지만

자바의 경우에는 substring메서드를 이용하면 된다.