파고파고

해결 포인트✨ 1. 노란 격자의 수가 최대 2,000,000 개라고 주어졌는데, 가로가 세로보다 무조건 길거나 길이가 같기 때문에 많이 돌아봤자 1,000,000 번보다 많이 돌지 않는다. 따라서 갈색 격자의 수와 노란 격자의 수가 매칭될 때까지 단순히 for문을 돌리는 것으로 코드를 짰다. 2. 반복문 range 에서 노란격자가 하나인 경우가 계산되지 않기 때문에 따로 처리해줬다. 코드✨ def solution(brown, yellow): width= 0 height= 0 if yellow == 1: return [3, 3] else: for i in range(1,yellow): if yellow%i==0: width = yellow//i height = i if brown == width*2+hei..

해결포인트✨ 1. 가능한 모든 단어사전의 순서가 어떻게 되는지 파악하는 것이 가장 중요했다. (길이, 알파벳 등) 2. 앞자리부터 시작해, 해당 단어 이전에 존재할 수 있는 단어 개수를 구해 반복적으로 더해주었다. (가령 AEI의 순서를 구한다고 한다면, A 이전에 존재할 수 있는 단어 수 (0), AE 이전에 존재할 수 있는 앞자리가 A인 단어 수 (1*(5^0+5^1+5^2+5^3)), AEI 이전에 존재할 수 있는 앞자리가 AE인 단어 수(2*(5^0+5^1+5^2)) 를 더했다.) 3. 이전 단어 수 뿐 아니라 해당 단어도 고려해야 하기 때문에, 각 단계에서 1을 더 더해주어야 한다. 코드✨ import itertools def solution(word): word_lst = ["A","E","I..

해결 포인트✨ 1. 처음에 수의 앞자리와 그 뒷자리를 비교하는 걸 chance를 소진할 때까지 반복하도록 짜면 되겠다고 생각했는데, 시간복잡도가 너무 커 효율성 테스트를 통과하지 못했다. 2. 수 각 자리를 담은 리스트에서 인덱스를 찾아 pop 하는 걸 반복한 것이 시간복잡도를 잡아먹는 것을 발견했다. (원래 pop은 O(1)만 걸린다고 생각했는데, 맨 끝자리를 pop하는 게 아니라, 지정해준 인덱스를 pop할 때는 리스트를 훑어야 하기 때문에 O(n)이 걸린 것이 원인이었다.) 3. 논리는 마찬가지로 유지하되, stack을 활용하는 것으로 코드를 수정했다. 각 자리 수의 인덱스를 따로 저장하거나 수를 삭제하는 과정에서 리스트를 추가적으로 훑을 필요가 없어져 효율성테스트를 통과했다! 코드✨ def sol..