Blind

[python] 프로그래머스 - 무지의 먹방 라이브(2019 KAKAO BLIND RECRUITMENT)

🤔문제 해결 Lv4 | 우선순위 큐? 가장 처음 생각난건 역시 1초씩 전부 돌아보자!! 하지만 역시나 시간초과 발생 😂🤣 음식을 한꺼번에 뺄순 없을까 생각해서 가장 적은 음식의 수만큼 사이클을 돌기로 했다. 예를 들어 음식이 [ 5,5,3,3,6 ] 이라면 3만큼 한꺼번에 돌아주는 것이다. 음식이 3만큼 있고, 전체 길이가 5 이므로, 15초 뒤에는 [ 2,2,0,0,3 ] 이 된다고 상상만!!! 직접 빼주고 하면 시간 초과 다음은 2만큼 있고, 전체 길이가 3 이므로 (0은 취급 안함), 6 초 뒤에는 [ 0,0,0,0,1 ] 역시 상상만 하자 위의 방법 처럼 한꺼번에 빼주는데 가장 적은 음식은 어떻게 꺼내냐하면 바로 힙큐를 쓰자. 힙큐에 음식의 양과 해당 음식의 번호를 차례로 넣으면 가장 작은 음식을..

[python] 프로그래머스 - 블록 게임(2019 KAKAO BLIND RECRUITMENT)

🤔문제 해결 Lv 4 | 시뮬레이션? 먼저 지울 수 없는 블록과 지울 수 있는 블록으로 나눴다. 동그라미 친 블록은 지울 수 있는 블록 board 의 맨위 왼쪽부터 차례로 탐색한다. 블록을 만나면 위에 동그라미 친 블럭인지 확인하고, 맞다면 지울 수 있는지 확인한다. 지울 수 있다면 지워주고, 지울 수 없다면( 지울 수 있는 블록이긴 한데 위에가 막혀서 아직 못지움) 임시 리스트에 저장. 다음 블록들을 지우는 것을 성공할 때마다 임시저장한 블록들도 지울 수 있는지 같이 체크해서 지워준다. 💨 문제는 크게 어렵지 않지만, 어떻게든 풀 수 있을 것이다. 시간이 오래걸리겠지만... 💻소스 코드 blocks = { 1: [[ (1, 0), (1, 1), (1, 2) ], [(0, 1), (0, 2)]] , 2:..

[python] 프로그래머스 - 외벽 점검(2020 KAKAO BLIND RECRUITMENT)

🤔문제 해결 Lv 3 | 정답률: 0.6% 주어진 값의 크기가 크지 않기 때문에 완전탐색으로 해결이 가능하다. 먼저 친구를 순열로 만든다. ex) [1,2,3] 이면 [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1] 외벽이 원형이므로 앞과 뒤가 이어져 있다고 생각해야 한다. 취약점도 첫번째 취약점을 먼저 갈것인가 두번째 취약점을 먼저 갈것인가... 순서를 정해서 가야한다. - 첫번 째 테스트케이스의 취약점([1, 5, 6, 10])을 배열(n=12)로 나타내면 [0, 1, 0, 0, 0, 1, 1, 0, 0, 0, 1, 0] 위의 경우는 첫번째 취약점(1)이 가장 먼저 나오는 경우 - 다음 취약점 2가 가장 먼저 나오는 경우는 0,1을 맨뒤로 옮겨주면 된다. ..

[python] 프로그래머스 - 블록 이동하기(2020 KAKAO BLIND RECRUITMENT)

🤔문제 해결 1. Lv3 | BFS 심화 2. BFS를 돌릴 q와 방문체크할 visited리스트를 준비한다. (1) q는 deque를 이용. 로봇의 좌표 4가지 (x1,y1,x2,y2)와 현재의 거리 d 를 넣는다. (2) visited에는 로봇의 좌표만 넣는다. 3. BFS를 돌린다. (1) 먼저 끝점에 도달했다면 바로 멈춰주고 거리를 출력한다. (2) 그렇지 않다면 로봇이 세로인경우와 가로인경우를 나누고, 상하좌우 움직일 수 있는 지 체크한다. (3) 로봇이 세로인 경우 오른쪽 이동이 가능하면 오른쪽 회전도 가능하다. 마찬가지로 왼쪽이동이 가능하면 왼쪽으로 회전도 가능하다. (4) 가로도 마찬가지 (5) 이동이나 회전이 가능하면 visited리스트를 확인해 방문한적이 없으면 q와 visited에 넣어..

[python] 프로그래머스 - 가사 검색(2020 KAKAO BLIND RECRUITMENT)

🤔문제 해결 1. Lv4... | 트라이 자료구조 2. 트라이 자료구조를 구성한다.( 쉽게 말하자면 dict안에 dict안에 dict안에 dict.... 구조 ) 대략 위의 그림과 같은 형태로 구성하게 된다. 맨 앞의 숫자는 길이가 5인 단어, 6인 단어 다음 f로 시작하는 단어 4개, r로시작하는 단어 4개, o로 시작하는 단어3개, d로 시작하는 단어 1개... 가 있다는 의미 4. 찾는다... 만약 'fro??' 을 찾는다고 하자 (1) 길이가 5 인 곳으로 들어간다 (2) 거기서 f 로 들어간다. cnt에는 f로 시작하는 단어가 4개있다는 것을 저장한다. (3) r 로 들어간다. cnt에는 r로 시작하는 단어가 4개 있다는 것을 저장한다. (4) o 로 들어간다. cnt에는 o로 시작하는 단어가 ..

[python] 프로그래머스 - 자물쇠와 열쇠(2020 KAKAO BLIND RECRUITMENT)

🤔문제 해결 1. lv3 | 완전탐색? 2. 자물쇠 주위를 1과0이 아닌 다른 숫자로 채워준다. ( 열쇠의 길이 - 1 만큼 ) 3. 열쇠를 새롭게 만들어진 자물쇠 위에 놓고 2중 for문으로 전부 겹쳐가며 탐색한다. ( 자물쇠를 열쇠의 크기만큼 잘라서 열쇠와 자물쇠를 비교) ( 노란색: 원래자물쇠, 초록색: 새롭게 채워놓은 빈공간, 파란색: 열쇠 4. 열소의 돌기(1)와 자물쇠의 구멍(0)이 만나면 카운트 +1, 열쇠의 돌기(1)와 자물쇠의 돌기(1)가 만나면 탈락, 열쇠의 구멍(0)과 자물쇠의 구멍(0)이 만나면 탈락, 자물쇠의 모든 구멍(0)이 열쇠의 돌기(1)로 채워져야 한다. (즉, 파란영역 안의 자물쇠가 모든 구멍(0)을 가지고 있어야한다) 5. 자물쇠 전체의 구멍의 숫자와 열쇠의 돌기가 자물..