알고리즘 공부하기 [1. 배열]

배열, 단순하게는 인덱스로 관리를 하고, 처음에 크기를 설정한다.

배열 관련 알고리즘문제는 너무도 많이 나오기 때문에, 자세한 설명은 생략

 

1.Arrays 관련 기능

 

 - Arrays.toString(배열); -> 배열의 값을 String으로 출력해준다.

- arr1[1].indexOf("hi") -> hi or hi 말고 알파벳 하나일 경우, 해당 문자가 포함된 인덱스를 return 해준다.

ex. arr1[1] ="abcd"

1)arr1[1].indexOf("b") -> return 1

알파벳이 없다면, -1을 반환한다. 따라서, 해당 내 문자열 포함 여부는,

if(arr1[1].indexOf("g") >= 0) 이런식으로 검사를 한다.

 

- Arrays.sort, (Collections.reverseOrder을 사용하면 역순) -> 배열을 정렬해준다.

 

 

- Arrays.copyOf, Arrays.copyOfRange -> 배열을 복사하여, 신규 배열로 담을수있다. (완전 복제가 아닌, 일정 범위 복사 가능)

 

- Arryas.BinarySearch() -> sort 후에, search를 하게되면, 해당index값이 나온다. 없거나, sort를 하지않으면 음수가 나온다.

이때 주의할것은 크게 두가지 이다.

1. Sorted 된 배열에서 사용을 해야한다.

2. 음수에 대한 return이 무의미 하지않다, 음수는 해당 정렬이 되어있고 + 해당 찾고자하는 값이 없을때 정렬을 계산하여, 어떤 인덱스에 해당 값이 오면 좋을지를 알려주는 값이다.

 

해당 함수도, 잘 활용하면 코테에 녹일수 있는 메소드 이다.

 

 

그럼 이제, 실습을 해보자

https://programmers.co.kr/learn/courses/30/lessons/42748

코딩테스트 연습 - K번째수

 

우선 여기에서 추가로필요했던 개념은

List -> Array로 변환할때

int[] arr = list.stream().mapToInt(i->i).toArray() 정도이다.

 

 

 

우선 다음 문제 풀기전에, Arrays.sort의 기능에 대해 세부적으로 공부를 해보자.

물론 언급을 했듯이, Arrays.sort하면 내림,오름 차순으로 정렬이 가능하다. 그런데 만약에 사용자 정의하여 새로운 기준으로

정렬을 하고싶다면? 어떻게 해야할까?

여러가지의 방법이 있겠지만, 바로 Comparator의 compare을 오버라이딩 하여 재 정의하는 것이다.

세부 적으로 어떻게 동작하는 지 살펴 보자.

 

 

우선 해당 배열이 210,110,22 이런 원소들이 무정렬로 들어가있다고 하면, 단순히 Arrays.sort를 하게 되면,

주석 처리된 부분이 자동으로 실행되어 정렬이 된다.

따라서 110,210,22 가 되는것이다. Collections.reverseOrder()도 한번 재 정의하여 구현해보자

 

단순하다. 아까 주석처리한부분에서 return 에 대한 부분을 변경하면 된다.

 

그러면 좀 더 자세히 알아보자

 

이런식으로 print를 해보자.

일단 해당 compareTo를 하게 되면, 01,12,23,의 원소를 차례대로 비교하면서 값을 return 한다.

우선 CompareTo는 문자열 비교와, 숫자연산의 방식이 두가지 존재한다.

문자열의 경우에는 문자가 같은지를 비교, 숫자는 대소관계를 비교해준다.

 

1) 문자열 비교

문자열 비교(String)의 경우에는, 기준값.compareTo(대상값)으로 본다면

위의 경우는 String 의 경우이기때문에, 값의 비교를 잘 보면 120(기준 값) , 110의 경우 한글자씩 비교를 한다,

1은 처음 숫자인데 두개가 같고, 2와 1은 다르다, 따라서 해당 값의 차이인 1이 return된다.

이와 같은 원리로 123,999의 return 은 -8이되는 것이다.

 

return 이 음수이면 false, 양수이면 ture이기 때문에 해당값으로, 오름 차순이 정렬되는 것이다.

123,234 라면 음수가 리턴될 것이고.(1-2) switch가 일어나지 않기 때문이다.

 

자. 그러면 만약에 123, 12 의 경우에는 어떻게 될까?

해당 케이스는 단순히 텍스트로 정리를 해보면 123에 12가 포함이 되어있다. 따라서 해당 문자열의 길이의 차이가 return 된다.

 

이 개념을 가지고 실습 예제를 하나 풀어보자

https://programmers.co.kr/learn/courses/30/lessons/42746

코딩테스트 연습 - 가장 큰 수

해당 문제에서는 두개의 함정 요소가 있다.

1) 정답의 첫번째가 0일때 000으로 출력될수있는점 (정렬이 된 이후에)

2) 단순 내림 차순으로 정렬이 되면, 30,3 의 String 비교는 30의 문자열 길이가 더 길기때문에 330 보다 303이 더 크다고 return 된다.

-> 그래서 , 30.compareTo(3) 이게 아닌, (30+3).compareTo(3+30) 이 되게끔 해주어야 한다.

 

자,그러면  정답 소스 공개!

 

원리는 간단하다. Arrays.sort에, 두번째 인자로, 익명 클래스 즉 new Comparator을 선언해주고

reverseOrder나, 단순 오름차순이 아닌, 문자열 두개를 합친것에 대한 compareTo이 되게 끔 해주면 된다.

 

그리고 마지막에는 첫번째 원소가 0이라면, 뒤에도 무조건 0이니 return 0

아니라면 그냥 붙여서 return 해주면 된다.

 

마지막으로 풀어볼 문제

https://programmers.co.kr/learn/courses/30/lessons/42747#

코딩테스트 연습 - H-Index

배열의 h-index 문제이다.

해당 풀이법은 간단하다.

우선 배열을 정렬 하고, 해당 정렬 된 배열을 앞에서부터 검사한다.

총 배열의 길이 - 인덱스의 순차 번호가, 해당 숫자보다 작거나같다면 해당을 바로 출력한다

예를 들어서

[0,1,4,5] 이렇게 문제가 들어오면

1을 검사할때는 

4 - 1 <= 1 이 false가 되기때문에, 성립하지않고

4를 검사할때 4-2 <= 4 가 성립되기때문에, 해당 최대값은 2라고 할수있다. 다만 문제는 answer에 대한값의 최대값이 

덮어씌워지지않게 조심하는 것이다.

 

해당 위오ㅏ 같이 풀면 정답을 맞출수있다.

 

내가 조금 헤맷던 부분은 나는 당연히 1이 출력이되어야 할것같았다.

최대 인용 횟수는 1이기 때문에, 근데 그게 아니고 최대 숫자를 출력하는 것이기 때문에 해당 숫자 2가 출력이 되어야 하는 것이 맞다.

 

조금만 침착하게 문제를 읽고 푸는 습관을 기르자 ㅋ

 

무튼 배열관련 함수 및 개념 정리 + 튜토리얼 코테 문제 풀이 포스팅 끝!