hyeoneee's blog

전형적인 투포인터 알고리즘 문제이다

중요한건 ;ㅅ;

문제를 읽고 투포인터 알고리즘 문제라는 것을

깨달아야 한다는 것이다 ^_^,,,,,,

따흑,,,

이것도 처음엔 문제 이해가 안갔다 @_@

왜이렇게 문제 이해가 어려운것인지,,,,,흑,,,,

결국 이문제도 간단하게 설명하자면

정렬된 길이 n의 A배열과 길이 m의 B배열이 입력으로 주어졌을 때
A[i]+B[j]=X를 만족하는 (i, j)쌍의 개수를 구하는 문제
이다.

이문제는 어떻게 투포인터 알고리즘으로 구현했냐하면

가장 중요한건

작은 (왼쪽~) 은 i로 정의

큰값부터 줄어드는 (오른쪽 ) 은 j로 정의

한다는 것이다!

A

B

이렇게 투포인터를 만들어주고

각각 끝점 값을 더해줘서

값이 크면~ j를 옮기고

작으면 i를 한칸 옮겨준다.

투포인터 알고리즘을

이해하기 좋은 문제인거 같다

다행히 이문제는

쌤의 설명이 바로~ 이해가 갔다

그럼이만

뿅!

아나그램 문제 풀기

우선 아나그램이 뭔지를 알아야 한다

아나그램이란 ? 문자를 재배열 하여 다른단어로 바꾸는 것이다.

이 문제를 검색하면서 찾아보니

구글 면접에서도 나왔던

아니면 it 기술 면접에 종종 나오는 질문인거 같다.

다음 예제로 문제를 보면,

abcab 가 (S1)

aabbcbbaa (S2)에

aabbc / cbbaa

이렇게 두부분 존재한다.

그래서 답은 2이다.

이문제를 처음에는 잘못 이해 했는데

선생님의 말을 들으니 이해가 갔다

결국 물으려고 하는 것은 이것이다.

S2문자열을 S1문자열의 길이로 끊어서 앞에서 부터 보는데,

그중에 아나그램이 몇번 있을 수 있냐 ?

그래서 S2에서 1~5번째 문자열을보고 아나그램인지 보면된다.

그다음 2~6번재 문자열을 보고

이것도 전에 풀었던 결국 투포인터 알고리즘이랑 비슷하다.

그다음에 아나그램인지를 판별하는것은

결국 아나그램을 판단하는것은

해당 문자열이 몇버 나왔는지를, 카운트하는 배열을 만들어서

그 카운트 배열만큼 숫자가

다 같게 있으면

결국은 아나그램인 것이다.

그걸 구현한 소스는 이것이다.

처음엔 카운트 배열을 구현하는것도 어려웠다.

그런데 선생님이 구현한걸 보니

결국 각각 문자열이 가지고 있는 숫자가? 있으니깐

그 배열의 인덱스에 카운트를 증가 시켜줬다. 

(아마 내가 기억하기로 아세키 코드값인걸로 기억한다 ~_~/ 맞겠지 )

그런데 여기서 구현 할때는

1. S1의 카운트 배열을 먼저 생성

2. S2의 카운트배열을 S1의 길이만큼만 생성  ****아주 중요 ****

해서 비교해준다

그리고 나서 S2의 카운트 배열을 앞에를 빼주고 뒤에를 더해준다 ~

(투포인터 개념!!)

이런식으로 해줘야 시간복잡도가 맞지

안그러면 시간초과! 그래서

이부분이 아주~ 중요하당!

그리고 나서 S1의 카운트 배열과 S2의 (S1길이까지만의) 카운트 배열을

서로 비교해서

같으면 COUNT를 하나 높여준다~

@_@ 첫날 알고리즘 수업인데

그래도 올초에 잠깐 공부하다 만

개념이 나와서

조금은 반가웠고

그래서 이해가 좀 수월했다

앞으로 남은 2주 열심히 해야겠당!

블로그에도 꼬박꼬박 정리이 ~~~

그럼 이만

뿅!