코딩테스트 입문 - 문자열 밀기 ( find, 글자 더하기 )

 

엄청 어려운 건 아니었는데

 

문법정리를 위해

왔습니다.

 

---

 

흠 사실 한 칸씩만 밀면 된다고 생각했다.

근데 생각해 보니

o를 때는 건 안 어려운데

그걸 맨 앞에 붙이는 게...

어.. 째 하는 거지?

 

 

막막해졌다.

 

인지 씨를 찾았다.

하나씩 정직하게 밀면

시간초과가 날 수 있다고 했다.

그렇게 푸는 문제가 아니라는 뜻

 

밀기만 하면 되다 보니

이 문제는

같은 단어를 두 개 붙이고 find로 그 단어를 찾으라고 했다.

 

단어 두 개를 붙여..?!

 

단어를 두개 붙이면

밀어서 만들었던 글자들이 전부 들어가게 된다.

 

신기신기

 

 

일단 만들어봤다.

 

.. 긁적..

 

 

이유에 대해 물었다.

 

정말이었다.

원래는

hellohello

의 경우 오른쪽으로 하나 밀면 답이 나오는데

지금 내식대로 하면 4번째부터 나와서 4가 출력된다.

 

이게 왜 이러냐면

AA를 만들어놓고 인덱스를 뒤로 옮기는 건

맨 앞에 글자를 떼서 맨 뒤로 붙이는 행동

즉 우리가 생각하는 반대 행동이다.

 

그럼 어떡하지?!

 

B를 옮기면 된다고 한다.

 

B를 두 번 붙여보자

ohellohell

같은 식으로 풀어보면 한 칸만 이동하면 답이 나온다.

 

즉

A랑 B랑 같은 글자이고,

원래 단어를 찾으면서

원래글자에서 몇 글자 당겼는지 세는 것이다.

 

그래서!

맞는 글자에서 틀린 글자를 세는 게 아니라

틀린 글자에서 맞는 글자를 찾는 게

맞게 된다.

 

 

만약에 B+B 를 생각 못할 경우

A의 전체길이에서 pos 값을 빼주면 된다.

사실 이러면 문제가 또 하나 발생하는데,

 

한 칸도 안 밀었을 땐 pos가 0인데 빼줘서

A길이가 나오는 초유의 사태가 발생한다.

 

pos가 0이면 그냥 출력하도록 해주는 예외처리가 필요하다.

---

 

 

세상에

다른 사람들 문제 보고 알았는데

 

더 간단하게 푼 사람이 있었다.

못 바꾸면 출력 때 -1을 출력하라고 했는데,

string::npos가 상수화 하면 -1이라고 한다 ㅎㅎㅋ

wow!!

 

신기신기

 

이런 건 금방 외우겠지..ㅎㅎ