프로그래머스(19)
-
[프로그래머스/python] 방문 길이
방문 길이 Summer/Winter Coding(~2018) 문제 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 지나간 길을 (좌표X, 자표Y, 방향) 으로 체크를 합니다. 예시로 (0,0) 에서 윗길은 (0,0,Up) 로 표현이 가능하며 (0,1,Down) 으로 두가지의 표현이 생깁니다. 이 두가지의 좌표를 매번 이동마다 집합에 추가를 합니다. 중복된 길의 경우 좌표가 집합에 추가되기 때문에 중복되는 길은 고려하지 않습니다. 풀이코드 def solution(dirs): answer = 0 tmp = [] for i in dirs: tmp..
2022.08.15 -
[프로그래머스/python] 후보키
후보키 2019 KAKAO BLIND RECRUITMENT 문제 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 조합과 집합을 사용하여 풀이를 진행했습니다. 이 문제를 들었던 생각은 유일성과 최소성을 잘 구현하면 되겠다고 생각했습니다. combinations 사용해서 후보키의 길이를 1부터 n열까지 올리면서 조합을 구했습니다. 조합의 값을 통해서 각 열에 있는 값들을 종합하여 겹치는 값이 있는지 집합을 썼습니다. 그럼 이제 유일성은 해결했습니다. 최소성의 경우 유일성에서 통과한 후보키 값을 n길이 조합이 유일성 검사하기 전에 체크합니다...
2022.08.10 -
[프로그래머스/python] 자물쇠와 열쇠
자물쇠와 열쇠 2020 KAKAO BLIND RECRUITMENT 문제 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 key의 돌기 부분을 lock 홈에 하나 씩 맞춰보고 맞지 않다면 90도 회전하면서 풀었습니다. key의 돌기를 따로 배열에 빼놓고 lock 홈을 따로 배열로 빼놨습니다. key의 돌기 중 한 개를 선택해서 lock 홈에 맞춰봅니다. 여기서 맞춰볼 때 key 돌기 배열 안의 요소는 전부 이동합니다. ( 돌기와 홈의 거리 만큼!) 맞춰볼 때 lock의 범위를 넘어가는 key의 돌기는 제외했습니다. 딱 맞는다면 lock과 ke..
2022.08.10 -
[프로그래머스/python] 순위 검색
순위 검색 2021 KAKAO BLIND RECRUITMENT 문제 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 해시맵과 이진탐색을 사용하여 풀이를 진행했습니다. 사실 처음에 풀 때 해시맵이 뭔지도 모르고 풀었기 때문에 한참 걸리고 틀리고 힌트를 얻어가며 풀어갔습니다. 문제 해결과정이 꽤 복잡했습니다. 일반배열로 풀고 "시간초과", 집합으로 풀고 시간을 절반 줄였으나 "시간초과", 쿼리 순환 밖에서 정렬해봤는데 "시간초과" 당했습니다. 문제를 보니 info 배열의 크기는 1 이상 50,000 이하입니다. 그렇다면 이중for문은 포기하고 ..
2022.08.10 -
[프로그래머스] 가장 먼 노드 (파이썬 python)
코딩테스트 - 그래프 - 가장 먼 노드 [Level3] 문제링크 : 가장 먼 노드 코딩테스트 연습 - 가장 먼 노드 6 [[3, 6], [4, 3], [3, 2], [1, 3], [1, 2], [2, 4], [5, 2]] 3 programmers.co.kr 문제풀이 그래프 문제입니다. 기존 BFS 풀이를 가지고 풀면 7,8,9 케이스에서 "시간 초과"를 만나게 됩니다. 그러기 위해서 그래프의 방법 중 "인접 행렬" 이 아닌 "인접 리스트"를 사용해야 합니다. list = [[0 for _ in range(n+1)] for _ in range(n+1)] 위 행렬 생성 코드 작성만 해놔도 시간 초과가 걸립니다. 인접 행렬의 경우 연결할 수 있는 모든 경우의 수를 체크를 하고 인접 리스트는 연결된 경우의 수만..
2022.06.10 -
[프로그래머스] 네트워크 - 파이썬 python
코딩테스트 - 깊이/너비 우선 탐색(DFS/BFS) - 네트워크 [Level3] 문제링크 : 네트워크 코딩테스트 연습 - 네트워크 네트워크란 컴퓨터 상호 간에 정보를 교환할 수 있도록 연결된 형태를 의미합니다. 예를 들어, 컴퓨터 A와 컴퓨터 B가 직접적으로 연결되어있고, 컴퓨터 B와 컴퓨터 C가 직접적으로 연결되어 있 programmers.co.kr 문제풀이 DFS 문제입니다. conected_check 배열에는 컴퓨터의 연결을 체크합니다. 연결 안 되어 있으면 False 되어있으면 True 연결 안되어 있는 컴퓨터의 경우 (connected_check == False) 이를 기점으로 dfs함수를 실행해 연결된 컴퓨터를 체크합니다. 기점과 연결된 컴퓨터를 conected_check에 tmp배열에 넣어 ..
2022.06.08