바위타는 두루미

문제 n개의 정수로 구성된 정렬 상태의 배열을 임의의 횟수만큼 회전시켜 얻은 배열이 입력으로 주어진다고 하자. 이 배열에서 특정한 원소를 찾는 코드를 작성하라. 회전 시키기 전, 원래 배열은 오름차순으로 정렬되어 있었다고 가정한다. 입력 : {15,15,19,20,25,1,3,4,5,7,10,14} , 5 출력 : 8 ( 배열에서 8번째 인덱스에 5가 있으므로) 접근법 이 문제를 보고 이진탐색을 생각했다면 매우 훌륭하다. 고전적인 이진탐색은 어떤 값 x가 왼쪽에 있는지 오른쪽에 있는지를 판단하기 위해 x를 배열의 중간 원소와 비교한다. 하지만, 이 문제는 배열이 회전된 상태라서 까다롭다. 두 배열을보자 배열 1 {10,15,20,0,5} 배열 2 {50,5,20,30,40} 이 두배열 모두 20이 가운데..

문제 Anagram 묶기: 철자 순서만 바꾼 문자열이 서로 인접하도록 문자열 배열을 정렬하는 메서드를 작성하라. 해결법 두 문자열이 철자 순서만 바꾼 문자열이라는 사실을 알아내려면 어떻게 할 수 있을까? 1. 정렬해서 같은 글자라면 Anagram일 것이다. 2. 나오는 철자들의 갯수를 세서 같은 갯수면 Anagram일 것이다. 첫번째 방식을 이용해서 해결이 가능할 것같다. 정렬한 값을 key로 문자열을 해쉬의 벨류로 가지는 해쉬를 관리함으로써 해결이 가능할 것이다. def getAnagrams(words): sortChars = {} for w in words: key = ''.join(sorted(w)) sortChars[key] = sortChars.get(key, []) + [w] result = ..

문제 0(false), 1(True), &(and), |(or), ^(xor)로 구성된 불린 표현식과 원하는 계산 결과가 주어졌을때 , 표현식에 괄호를 적절하게 추가하여 그 값이 원하는 결과값과 같게 만들 수 있는 모든 경우의 갯수를 출력하는 메서드를 구현하라. 접근법 1. 무식한 방법 표현식이 0^0&0^1|1이고 원하는 결과가 true인 경우를 생각해보자, countEval( 0^0&0^1|1, true)를 어떻게 쪼갤 수 있을까? countEval( 0^0&0^1|1, true) = countEval( 0^0&0^1|1 괄호가 1번 위치에 있을때 , true) + countEval( 0^0&0^1|1 괄호가 3번 위치에 있을때 , true) + countEval( 0^0&0^1|1 괄호가 5번 위치..