Day.13 알고리즘 학습 (회문 문자열)속 toUpperCase

내일배움캠프에서 제공하는 알고리즘 강의의 목차를 기준으로 같은 내용의 알고리즘의 문제를 푸는 방식이나 강의에서 주는 문제를 Python이 아닌 Java를 이용하는 방식을 사용해서 문제를 접근하고, 해결하려고 노력하고 있다.

 

항상 문제를 접근할 때, 문제를 해결하기 위해 어떤 논리적인 생각을 해야하며, 이 속에는 알고리즘과 관련된 혹은 기본 베이스가 어떤 것이 있을까?  생각하며 문제에 접근하고자 한다.

 

항상 알고리즘 문제를 풀 땐, 옆에 종이와 펜을 필수로 둔다.

 

주어진 문제를 분석하다 보면 필요한 내용들을 종이에 적고, 논리적인 부분들을 직접 해보면서 문제에 접근하다보디 시간이 많이 걸리긴하는데, 문제를 이해하고 해결하면 만족한다...

 

 

금일 해결한 문제는 다음과 같다

 

1. LinkedList의 끝에서 K번째 값 출력

2. 순차탐색

3. 더하거나 빼거나

 + 회문 문자열

 

기존에 1~3번은 2주차 강의 숙제 부분을 이용해서 Python 혹은 Java로 구현했으며, 회문 문자열은 알고리즘 강의를 통해 문제를 해결했다.

 

1번 문제 같은 경우엔 내부적으로 제공하는 함수들을 사용해서 풀이하다 보니 별 어려움이 없었다.

 

2번은 주어진 배열에 그 값이 있는지 없는지를 search하는 조건의 문제였는데, 이 역시 큰 어려움은 없었다. 

순차 탐색(Sequential Search)는 말 그대로 주어진 여러개의 데이터 속에서 내가 원하는 데이터를 찾는 방법인데, 이 방법이 이진탐색이나 다른 탐색처럼 기준을 둬서 검색하는 방식이 아니라 순차적으로 데이터의 요소들을 확인하며 원하는 값을 찾는 방식이다. 

 

따로 데이터를 정렬할 필요가 없으며 정렬 되지 않은 데이터 속에서 사용 가능하다.

그래서 데이터의 갯수에 따라 최악의 경우 시간 복잡도는 O(N) -> (내가 찾고자 하는 데이터가 마지막에 있으면)이다.

 

주어진 문제에서 찾고자 하는 값이 있으면 주문가능, 없으면 주문 불가능 이런 식으로 데이터의 유무를 확인할 수 있었는데, 내가 구현한 방식은 count 를 통해 이 값이 있는지, 없는지를 우선 확인하고, 값이 있다면 count를 증가하고 선언한 배열에 저장해 최종적으로 이 배열의 요소 값이 1이면 주문 가능, 없으면 주문 불가능이라는 로직을 구현해서 문제를 해결했다.

 

3번은 재귀함수를 통해 경우의 수를 계속해서 count 하는 방식으로 문제에 접근을 했어야 했다. 

예를들어 5개의 숫자가 있다면 한 요소와 요소간 합 또는 차를 이용해 만들 수 있는 모든 경우의 수를 생각했어야 했다

그래서 이 방식을 이용해 만들 수 있는 숫자의 경우의 수는 2^(n-1) 여기서 n은 숫자의 개수 

 

재귀 호출을 통해 문제를 해결하려 했고, 중간중간 잘 모르거나 이해가 힘들었던 부분은 강의를 참고하며 문제를 풀었다. 

 

마지막으로 회문 문자열

 

회문 문자열은 앞에서 읽을 때나, 뒤에서 읽을 때, 같은 문자열을 회문 문자열이라 말하는데,

주어진 문자열이 회문 문자열이면 yes, 아니면 NO를 출력하는 프로그램을 구현하려고 한다. 이때 대소문자를 구분하지 않는다고 한다.

 

맨 처음에는 어떤 방식을 통해 접근하지? 라는 생각을 해보았는데, 생각보다 간단했다.

결국 앞 뒤가 똑같은지, 다른지를 확인하면 되는 문제이고, 어디까지 확인을 해야하는 범위, 이 범위 설정이 핵심이라고 해도 과언이 아니기 때문이다.  

예시를 통해 생각을 해보면 예를들어서 입력받은 문자열의 크기가 5라고 가정해보자

 

결국 중앙을 기준으로 첫번째 요소와 맨 마지막 요소, 그다음 두번째 요소와 마지막 전의 요소 이런 방식으로 비교만 하면 되니까 중앙이 기준이 된다. 그래서 주어진 문자열의 길이/2 까지만 반복문을 실행하면 된다.

 

반복문을 실행함과 동시에 문자열의 요소를 비교해줘야 하는데, 보통 문자열에서 요소를 자를 때 많이 사용한다

charAt의 로직

(어떻게 동작하는지는 직접 charAt을 타고 들어가서 확인하는게 빠를 것 같다...)

 

charAt을 통해 문자열 첫 요소와, 마지막 요소를 비교한다.

또한 이 문제에서 주어진 조건이 대 소문자를 구분하지 않는 것이었는데, 이는 toUpperCase()를 이용했다.

 

toUpperCase()?

이 메소드는 주어진 문자열을 모두 대문자로 변환한다.

toLowerCase()

주어진 문자열을 모두 소문자로 변환

 

이 두 방법 외에도 equalsIgnoreCase() 메소드를 활용할 수 있는데, 이 메소드 대 소문자 구분 없이 비교할 때 사용된다.