개발자 노트

문제 설명 구현 문제. 문제를 잘 읽고 이해해서 말하는 대로 구현하라. 예제도 매우 잘 나와있어서 정말 잘 읽어보고 알고리즘을 작성하면 된다. 읽은 내용 바탕으로 설명하자면, 1. K A K A O ↑ K문자는 사전에 있으므로 다음 A로 넘어간다 2. K A K A O ↑ KA는 사전에 없다. 따라서 KA를 사전에 등록하고 K의 인덱스 번호를 출력. 3. K A K A O ↑ A부터 다시 시작. A는 사전에 있으므로 다음 K로 넘어간다. (1~2과정 반복) 4. K A K A O ↑ AK는 사전에 없으므로 사전 등록, A의 인덱스 번호를 출력한다. 5. K A K A O ↑ K는 사전에 있으므로 다음 A로 이동 6. K A K A O ↑ 2.에 의해 KA또한 사전에 있다. 다음 O로 넘어간다 7. K A..

문제 설명 문제에서 그림과 함께 잘 설명되어 있기에 pass 봐야할 것이라면 잘린 쇠막대기의 총 수를 구하라 '()'가 레이저. arrangement가 최대 10만이기에 시간초과 주의 접근 딱 보면 뭐 어떻게 해야하는거야... 싶은 문제다. 그래서 나는 문제를 단순화해서 생각해봤다. 단순화할 때 유념해야할 것은 '()'가 레이져, 잘린 갯수 구하는 문제라는 것. case 1. ()만 주어질 경우 잘린 쇠막대기가 없으므로 0 case2. (()) 잘린 쇠막대기가 레이저에 의해 2개가 된다. case3. ((())) 잘린 쇠막대기가 레이저에 의해 4개가 된다. case4. (()()) 잘린 쇠막대기가 레이저에 의해 3개가 된다. case5. ((()())) 잘린 쇠막대기가 레이저..

문제설명 https://programmers.co.kr/learn/courses/30/lessons/17678 셔틀 버스가 9시부터 시간간격 t로 n회온다. 사람들은 이 셔틀버스를 타기 위해 00시01분부터 23시 59분 사이에 줄을 선다. 이때, 어떻게 줄을 서야 가장 타이트하게 회사로 가는 차를 탈 수 있을지(막차를 타고 갈 수 있을지) 시간을 찾는 문제이다. 시간은 1분 단위이다. 접근 문제 이해에 따른 목표값 찾기 문제를 이해하는데만 20분이 걸렸다. 문제를 정확히 이해했다면 결국엔 언제 줄을 서야 막차를 타고 갈 수 있는지에 대한 문제이므로 마지막 차에 타려고 줄을 섰을 때는 2가지 경우로 나눌 수 있다. 1)마지막 차가 도착했을 때 대기줄 인원이 버스의 정원을 초과했을 경우 이땐 가장 마지막에..

문제설명 스택 및 이차원배열을 물어보는 문제 접근 바구니는 단순히 stack만을 이용하면 되고, 이차원 배열에서 뽑을 인형을 잘 두는게 포인트. 이차원 배열도 세로로 스택으로 보기 위해 각열에서 top을 미리 찾은 다음 뽑을 때마다 +1 씩 해주는 방식으로 접근했다. 왜냐하면 아래로 갈 수록 값이 증가하니까.(이 부분에서 디버깅하는데 10분 소요했다. (전체 풀이시간 30분)) 구현 def solution(board, moves): n = len(board) tops = [0 for _ in range(n)] #값이 있는 index for c in range(n): for r in range(n): if board[r][c] != 0: tops[c] = r break answer = 0 basket = ..

문제설명 https://programmers.co.kr/learn/courses/30/lessons/64063 문제 이해하는 것은 쉬운 편이나 어떻게 접근할 것인지 결정하는게 어려운 문제 1번방에 배정받은 사람이 있고 1번 방을 배정받기 원한다면 2번방을 배정해줘야 한다. 2번방에도 사람이 있다면 다음 사람이 없는 방인 3번방으로 배정. 예외도 없다. 방이 모두 5개있고 5번방을 2번 요청하는 경우는 input으로 주어지지 않는다고 적혀있다. 접근 1.UnionFind 딱 UnionFind가 생각나는 문제. 1~3번방에 사람이 있다면 결국 하나의 그룹을 이룬다고 생각할 수 있다. 그 이유는 1) 문제의 목표는 번호 x가 주어질 때 다음 방 배정을 찾는 것이다. 2) 번호가 1,2,3일 때 다음 방 배정은..

문제설명 트라이로 접근하는 것. 전화번호 중 동일한 접두어가 존재하면 NO를, 존재하지 않으면 YES를 반환한다. 접근 TRI 이용 완전탐색으로 접근하지 않는 이유 완전탐색으로 접근하면 시간복잡도는 엄청나다. 매 테스터케이스마다 N개의 전화를 N!번 비교하여 min(P1,P2)만큼 비교해야 하므로 O(T*N*N!*P)이다. (T는 테스트케이스 수, N은 전화번호 수 P는 전화번호의 자리 수) 따라서 최악의 경우 연산량은 50*10000*10000!*10이 된다. tri접근시 공간복잡도 고려 0~9까지 10개의 수 표현을 10개 표현해야하므로 10^104byte(int선언 기준)가 된다. 256MB를 넘지만, 미리 10개를 다 선언하지 않고 있을 때마다 선언하면 공간복잡도는 많이 줄어든다. n이 10000..

문제설명 간단히 말하여 높이가 서로 다른 탑들이 주어졌을 때 탑 꼭대기 왼쪽방향에 해당 탑보다 큰 탑이 존재하면 해당 탑의 번호를(1부터 시작), 없으면 0을 출력한다. 문제를 이해하는데 있어 중요한 내용은 1.탑의 높이는 중복없음. 2.탑의 수는 50만이하 탑의 높이는 1억이하이다. 접근 아이디어가 곧바로 떠오르지 않아 예제를 통해 어떻게 접근할 지 결정하고자 했다. 예제 : 6 9 5 7 4 1.6기준 왼쪽에 탑이 없으므로 0출력 2.9기준 6은 낮으므로 또 0 출력 3.5기준 9가 높으므로 9의 번호인 2번 출력 4.7기준 왼쪽에 있는 5는 낮으나, 9가 만나 2추력 5.4기준 7을 만나 그 번호인 4출력. 위를 봤을 때 관심의 대상이 되는 빌딩기준 왼쪽에 더 큰 빌딩이 있는지 봐야하는데 단계가 지..