당니의 개발자 스토리
1-G 본문
내 풀이(http://boj.kr/37bf9df65f56423bac450aeb1601ca9d) - 맞음
공유 소스 보기
www.acmicpc.net
1-G
백준 9996번 문제를 풀어보겠습니다.
이런 식으로 출력해야되는 문제죠.
첫번째, 이 문제를 봤을 때 예시 코드 자체가 한 글자로 되어있다고 한 글자만 무조건 들어온다라고 생각을 해서 이걸 기반으로 로직을 짜면 안 돼요.
이 문제에서 이 와일드카드(wildcard), 그러니까 에스터리스크를 기반으로 해서 이 앞과 뒤가 무조건 한 글자라고 명시가 되어 있나요? 아니죠.
예시 코드, 그러니까 문제에서 주어지는 예시는 한 글자인지도 몰라도 문제에서 조건을 보시고 조건에 이게 한 글자만 들어오는지 아닌지를 확인을 하셔야 돼요.
그럼 이제 이걸 어떻게 풀어야 될까?
자 일단 제가 용어 하나 알려드릴게요.
각각 접두사와 접미사 라고 해요. 영어로는 접두사를 prefix, 접미사를 suffix 라고 하는데 이따가 변수명 할 때 보일 거예요.
일단은 접두사 부분을 뽑고 접미사 부분을 뽑아서 주어지는 문자열에 이 부분만 비교를 하면 되지 않을까요?
여러분 뭐가 생각나야 될까요? 제가 문자열 함수는 별거 없다라고 했죠?
교안에서 문자열 함수 중 find, substr, reverse는 외워두시라고 했죠.
substr은 특정 위치에서 크기만큼의 문자열을 추출합니다. 그리고 크기를 넣지 않는다면 위치로부터 문자열 가장 끝자리까지 문자열을 추출해요.
이렇게 들어온다고 했을 때, *의 index를 찾아서 substr(0, 2) 즉, 2개를 뽑아냅니다. 즉, 크기는 이 별표를 찾은 위치가 들어가는 거죠.
그리고 만약 이렇게 들어온다고 했을 때, *의 인덱스가 3이죠. 그걸 그대로 두 번째 인자로 넣으면 접두사 부분을 찾을 수가 있습니다.
그럼 접미사 부분은 이 *의 위치의 + 1한 위치의 인덱스만 substr의 인자로 전달해주면 됩니다. 그럼 알아서 끝까지 추출해줍니다.
잠깐 코드를 보도록 하겠습니다.
제가 아까 설명했던 로직이
이렇게 된 걸 볼 수 있습니다.
문제는 이게 main 로직입니다. 이건 뭐냐면,
우리는 이렇게 뽑혀져 나온 접두사와 접미사의 길이만큼만 확인을 하면 되죠.
그러니까 예를 들어서 이렇게 되어 있다고 쳐도 우리한테 중요한 거는 주어진 문자열의 앞과 끝이죠. 이 앞과 끝이 같은 지만 비교하면 되는 거죠.
여러분 그럼 이 부분은 왜 있을까요? 여러분 쉬운 문제는
그냥 이 정도 로직만 가지고도 풀려요. 그런데 지금 같은 문제는 반례 때문에 if 문을 추가한 겁니다.
만약에 저 else 문 안의 로직까지만 짜잖아요. 그럼 어떻게 될까요?
ab*ab 라는 패턴이 주어졌을 때, 입력 값이 ab이면 이게 맞다("DA")고 떠요. 사실은 abab여야 맞는 거죠.
왜냐면 추출한 문자열의 길이 만큼 검사를 하는 건데, 접두사 접미사 둘 다 2만큼 검사할 거고, ab는 길이가 2니까 맞다고 나오겠죠.
즉, 이 접두사와 접미사를 더한 사이즈보다 크면 NE(틀림)이 됩니다.
그래서 항상 문제를 풀 때는 반례가 있나 없나 체크를 하시는 거예요. 반례의 기준이 되는 거는 size가 될 수도 있고 최대값, 최소값 입니다. 보통은 이렇게 세 가지인데 이거는 제가 문제를 풀면서 감을 익히도록 설명을 드릴 겁니다.
그건 이제 제가 문제를 풀면서 반례를 찾는 노하우를 천천히 알려드릴 테니까 일단 이 문제에서는 반례를 찾았어야 합니다.
