[Coding Interview] 문자열 관련 문제

 

 

문제 : s1, s2 문자열이 주어졌을 때 s2가 s1을 회전시킨 결과인지 판별하는 코드를 작성하시오. 예를 들어 s1이 codinginterview 라면 s2는 ginterviewcodin이다.   조건 : 자바의 contains 메소드는 1번만 사용한다.   똑똑한 풀이 :  가장 먼저 든 생각은 "길이가 같은가"이다. s1 과 s2 의 길이가 1이라도 차이가 있다면 회전한 결과가 아니기 때문이다. s2는 s1을 회전시킨 결과이기 때문에, s2를 한 번 더 이어붙이 s2s2의 중간에는 s1이 무조건 들어가게 된다. 예를 들어 s1이 "abcd" 이고 s2가 "dabc" 라면 s2s2 는 "dabcdabc" 가 된다. s2s2 를 만들고 s2s2.contains(s1) 이렇게 코딩하면 단번에 s2가 s1을 회전시킨 결과인지 알 수 있다.   바보같은 풀이 :  길이가 같다면, 나는 s2의 문자열을 for 문으로 처음부터 끝까지 돌면서 s1의 첫번째 글자(c)를 찾았다. 첫번째 글자를 찾으면 그 뒤부터 s1(처음부터)과 s2(찾은 문자부터)의 문자를 하나씩 비교해가며 서로 틀린 부분이 없는지 비교했다. 만약 틀린 부분이 있으면 s2는 다시 먼젓번 단계로 돌아가 s1의 첫번째 글자를 찾는다. 모두 맞는 부분이 나올 때까지 그리고 s2의 마지막 문자까지 계속 s1의 첫번째 글자를 찾는다. 이렇게 하면 풀릴 줄 알았는데 생각해보니 java contains 메소드를 한 번도 사용하지 않았다. 사실 contains 메소드의 내부적으로 이런 식의 구현이 이루어지고 있는거라면 나는 s2의 length 만큼 contains 메소드를 호출한 게 된다(...)

 

문제 : MxN 크기의 matrix 를 90도 회전시킨 결과를 출력하시오.   조건 : 추가 matrix 나 array 등의 buffer 를 사용하지 못한다.   key idea : 생각해보면 아래 그림과 같이, 동일한 조건에 의해 좌표가 이동한다. 단순히 각 좌표 각각에 알맞는 값만큼 좌표값을 바꿔주기만 하면 된다. 크기가 커져도 똑같이 적용된다. 문제는 추가적인 buffer 를 사용하지 못하기 때문에 다른 곳에 옮길 수 없어서, 문제를 해당 matrix 내에서 해결해야 한다는 점이다. 일반적인 swap method 로 (위의 그림에서) 1과 3을 바꿨다고 하자. 그럼 3과 4를 바꿀 때는 어떻게 할까? swap 절차를 늘리면 된다. 이를 테면 temp = one one = two two = four four = three three = temp 이런식으로. 나에겐 참으로 무릎을 딱 치게 만든 기막힌 발상이었다.