문제 설명 가로, 세로 길이가 n인 정사각형으로된 체스판이 있습니다. 체스판 위의 n개의 퀸이 서로를 공격할 수 없도록 배치하고 싶습니다. 예를 들어서 n이 4인경우 다음과 같이 퀸을 배치하면 n개의 퀸은 서로를 한번에 공격 할 수 없습니다. 체스판의 가로 세로의 세로의 길이 n이 매개변수로 주어질 때, n개의 퀸이 조건에 만족 하도록 배치할 수 있는 방법의 수를 return하는 solution함수를 완성해주세요. 제한사항 퀸(Queen)은 가로, 세로, 대각선으로 이동할 수 있습니다. n은 12이하의 자연수 입니다. 입출력 예 n result 4 2 접근 - N-Queen은 유일한 백트래킹 문제에 해당 - 모든 경우의 수를 count 하면서, 필요없는 부분을 가지치기한다. - 백트래킹은 n이 작을 때(..

이건 못 풀어서 다른 분 풀이를 참고하였다. # 프로그래머스 우수 풀이 참고 def solution(board): ss = {} answer = 0 for y, line in enumerate(board): for x, v in enumerate(line): if v == 0: continue ss[(x,y)] = s = min( ss.get((x-1,y), 0), ss.get((x,y-1), 0), ss.get((x-1,y-1), 0) ) + 1 answer = max(answer, s ** 2) return answer 배운 점 python dictionary의 get()메소드를 배울 수 있었는데, get()의 첫번째 인자는 key로, 두 번째 인자는 value가 된다. 이 때, key값이 dicti..

접근 복잡해 보이지만, 문제의 요구조건을 차례로 구현 하면 해결할 수 있습니다.. 단, 하나의 함수에 모든 것을 해결하려하면 복잡했기 때문에 3개의 함수로 분리하여 요구사항을 코드로 작성합니다. 문제 요구 사항 1. 입력이 빈 문자열인 경우, 빈 문자열을 반환합니다. 2. 문자열 w를 두 "균형잡힌 괄호 문자열" u, v로 분리합니다. 단, u는 "균형잡힌 괄호 문자열"로 더 이상 분리할 수 없어야 하며, v는 빈 문자열이 될 수 있습니다. 3. 문자열 u가 "올바른 괄호 문자열" 이라면 문자열 v에 대해 1단계부터 다시 수행합니다. 3-1. 수행한 결과 문자열을 u에 이어 붙인 후 반환합니다. 4. 문자열 u가 "올바른 괄호 문자열"이 아니라면 아래 과정을 수행합니다. 4-1. 빈 문자열에 첫 번째 문..

접근 1. 주어진 것을 정리 : 노드(컴퓨터)의 갯수, 비방향성, 연결선 2. 첫 시도: key(컴퓨터) - value (key와 연결된 컴퓨터) 구조의 dictionary 작성 시도 -> 못품 ㅎ ㅠ 3. dfs로 접근 : 이미 방문한 노드를 체크하기 위해 visited 리스트 생성 -> 원소는 모두 0으로 채우고, while문으로 0이 나오지 않을 때 까지 체크 4. 현재 방문중인 노드(컴퓨터)와 연결된 컴퓨터를 **모두** 찾기 위해 dfs 스택 선언 5. dfs 스택에 append될 조건은, 아직 방문하지 않은(visited[i]==0) 동시에(and) 현재 방문중인 노드와 연결 돼(computers[curr][i]) 있을 때 풀이 1) 반복문 사용 def solution(n, computers)..

접근 - 아래처럼 set() 형식으로 저장했다. (아이디, 이름, 메시지) (uid1234, Muzi, 님이 들어왔습니다.) (uid4567, Prodo, 님이 들어왔습니다.) (uid4567, -, 님이 나갔습니다.) (uid4567, Prodo, 님이 들어왔습니다.) (uid4567, Ryan, -) - Enter, Leave의 경우만 결과값에 반영된다 -> "Change"는 분기 처리 포인트 1. 중간에 이름이 바뀌는 경우를 고려하는 것이 가장 중요한 포인트다. 2. 이름은 바뀔 수 있지만, uid는 고정값이기 때문에 이것을 key로, 변하는 이름을 value로 잡았다. (딕셔너리 성질에 의해, 채팅방을 나간 후 이름이 변하는 경우를 곧바로 커버할 수 있다. uid는 동일하기 때문에 변경된 이름만 ..

정리 1. 글자 하나만 차이나는 단어를 찾아 리스트에 append (코드 작성) 2. 제한사항에서 데이터의 길이가 길지 않은 것을 확인할 수 있다. 시간복잡도가 조금 높아져도 통과할 수 있으므로 삼중 반복문도 try 해봐도 된다. - queue를 매번 업데이트 해줘야한다. - 왜냐하면, 어떤 단어를 기준으로 연관된 단어를 찾을 때마다 queue가 매번 달라질 것임. - 그렇기 때문에 각 연관 단어를 담을 temp_q를 만들어 iter마다 초기화 해줘야한다. => 난 그 초기화 작업이 없다. 주의할 점 1. 어떤 단어와 한 글자만 차이나는 단어가 꼭 하나란 법은 없다. -> 여러개인 경우가 분명 존재함을 인지 2. tmp_q (임시 queue)의 필요성을 인지할 것 실패한 풀이 마지막 테스트케이스에서 실패..

포인트 리스트 내 원소는 모두 같다. 타겟 넘버를 맞추는 방법이 ** 몇가지** 인지만 알면 된다. 전형적인 재귀 문제로, dfs를 이용하여 풀 수도 있지만, itertools라이브러리의 product메소드를 사용하여 pythonic한 코드를 작성할 수도 있다. 풀이 1) product, 곱집합 from itertools import product def solution(numbers, target): temp = [(i, -i) for i in numbers] result = [1 for i in product(*temp) if sum(i) == target] return len(result) temp 를 출력하면 temp = [(i, -i) for i in numbers] print(temp) >>>..

풀이 rest 리스트 가장 앞의 원소(기준 원소)와 뒤의 원소들을 비교 자신보다 크거나 같은게 나올 때 까지 계속 비교 (count += 1) 기준 원소보다 크거나 같은게 나오면, rest 리스트 슬라이싱 try ~ except 구문으로, IndexError 회피 progresses = [93,30,55] speeds = [1,30,5] import math def solution(progresses, speeds): rest = [math.ceil((100 - p)/s) for p,s in zip(progresses, speeds)] count, i = 1, 1 answer = [] while rest: try: if rest[0] >= rest[i]: count += 1 i += 1 else: res..