Python

[python] 프로그래머스 - N-Queen

🤔문제 해결 Lv3 | 백트래킹, DFS 규칙은 체스말의 좌우, 위아래, 대각선 모두 겹치지 않게 하는 것이다! 하지만 모든 규칙을 하나하나 체크하면 효율성 마지막에서 시간초과가 발생한다! 위아래 규칙: visited 리스트를 만들어서 세로(열) 한칸에 하나씩만 들어갈 수 있게 한다. 좌우 규칙: 한번 말을 놓으면 무조건 다음 행으로 넘어간다. 대각선 규칙: 말을 놓을 준비를 하고, 그 자리의 왼쪽 위대각선과, 오른쪽 위대각선에 말이 있는지 체크! 마지막 행까지 말을 둘 수 있으면 성공! 💨 💻소스 코드 def solution(n): answer = 0 chess = [[0] * n for _ in range(n)] # 체스판 visited = [0] * (n + 1) # 세로칸 방문 체크 # 조건에 일..

[python] 프로그래머스 - 도둑질

🤔문제 해결 Lv4 | DP "인접한 집은 털 수 없다" 까지는 크게 어려운 문제가 아니지만 "마을이 원형으로 되어 있다" 에서 한번 더 생각하게 하는 문제!! -> 0번째 집을 터는 경우( 마지막 집을 털지 못한다 )와 0번째 집을 안터는 경우 두가지로 나눌 수 있다. 먼저 0번집을 털 경우! 0번집에 들렀을 때 가장 많은 돈을 가져오는 경우는 0번집을 턴다. dp[0] = money[0] 1번집에 들렀을 때 가장 많은 돈을 가져오는 경우는 1번집을 터는 경우지만 우리는 1번집을 반드시 털었다고 가정했으므로 인접한 2번집은 털 수 없다. dp[1] = 0 2번집에 들렀을 때: 인접한 1번집이 아닌 0번집 또는 -1번집(2번일 때는 없다) 중 돈을 많이 가져왔던 집에서 온다. dp[2] = money[i..

[python] 프로그래머스 - 여행경로

🤔문제 해결 Lv3 | DFS 간단한 DFS 문제인줄 알았지만 조금 복잡한 문제이다. 그냥 풀면 테스트케이스 1,2번이 틀리게 된다. 이유는 중간에 길이 끊어지면 안되기 때문.예를 들어 이런 테스트 케이스가 있다고 했을 때 - ( 예외 케이스 ) 위와 같이 두가지 경로가 나올 것이다. 문제에서는 오름차순대로 진행하라고 했지만 B를 먼저가게 된다면 모든 티켓을 이용할 수 없기 때문에 답이 되지 않는다. 여기서 D까지 갔다가 길을 못찾고 A로 다시 돌아가야 하는데 어떻게 할까 고민하던중 길이 끊어진 D가 마지막이겠다 라고 생각해서 경로를 거꾸로 넣기로 했다. 길이 끊어져 있는 answer에 D를 저장하고, D가없어지면 B도 끊어진다. answer 에 B를 저장한다. 하지만 A는 B가 없어도 C가 있기 때문에..

[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] 프로그래머스 - 야근 지수

🤔문제 해결 Lv3 가장 큰 값을 조금 씩 줄여나가야 하는 문제! - 우선순위 큐를 이용했다. 우선순위 큐는 리스트에서 pop()을 하게 되면 가장 작은 값이 나오게 된다. 여기서는 가장 큰 값을 꺼내야 하므로 각각의 값을 음수로 힙큐에 넣어 줬다. 가장 작은 값(사실은 가장 큰 값)을 꺼내서 1씩 더해준다. 그리고 다시 힙큐에 넣어준다. 테스트 케이스 1번을 풀이 해 보자. 4, [4, 3, 3] 위 그림의 첫째줄은 처음 힙큐에 넣었을 때이다. 다음 줄부터는 1시간씩 지날 때 마다의 힙큐의 상황이다. -4가 제일 작으므로 -4를 꺼내서 1을 더해주고 다시 넣는다. -3을 꺼내서 1을 더해주고 다시 넣는다. 또 -3을 꺼내서 1을 더해주고 다시 넣는다. 마지막으로 -3을 꺼내서 1을 더해주고 다시 넣는다..