본문 바로가기
반응형

Algorithm41

후보키 [프로그래머스] 문제풀이 이건 일단 "어떤 컬럼을 써서 후보키를 만드는지" 가 관건이다. 어떤 컬럼을 사용해야 하는지 모르기 때문에 더할 컬럼들 (0번 컬럼 + 1번 컬럼 등)의 후보를 만드는게 첫번째다. 또한 중복이 없어야 하며, 더하는 컬럼의 순서가 중요하지 않다. (0번 컬럼 + 1번 컬럼) 을 이용해 키를 만들어 구분하나 (1번 컬럼 + 0번 컬럼) 을 만들어 구분하나 똑같다. index 값을 이용해 더할 컬럼의 후보를 만들어 준다. com_len = len(relation[0]) from itertools import combinations # 중복이 없는 후보군들 반환 하기 위한 combination 임포트 com_list = [] index_list = [i for i in range(com_len)] fo.. 2021. 11. 25.
순위 검색 [프로그래머스] 문제 풀이 정리 문제 설명 보고 개쉽네ㅋ 하고 입장했다가 대가리 깨진 문제다. 일단 문제자체는 어렵지 않다. 조건에 맞는 score들만 가져와서 개수를 센다. 끝 :) 그렇게 안일하게 보고 코드를 짤 경우 for loop *4 의 지옥을 보고 어...? 이거 괜찮은가? 하면서 돌리게 된다. 물론 그럼 시간 초과 난다. (테스트는 통과하지만 효율성에서 막힌다.) 그럼 두번째 방법으로 생각 한 것이 json처럼 depth 구분이 있게끔 만들어서 조건에 맞는 애들만 좀 쉽게 관리하자! → dictionary 형태로 key:value 로 만들어 관리 but, 마지막 depth 의 score_list에서 특정 값이상의 숫자 개수를 반환하는데 있어서 효율성 탈락 자, 그럼 score_list에서 빠르게 꺼낼 방법을.. 2021. 11. 22.
주식 가격 [프로그래머스] 코드 def solution(prices): answer = [] prices = list(reversed(prices)) for index, price in enumerate(prices): if len(answer) == 0: answer.append(index) else: flag = False for i in range(index-1, -1, -1): if prices[i] < price: answer.append(index-i) flag = True break if not flag: answer.append(index) answer = list(reversed(answer)) return answer 문제 풀이 스택/큐 문제라는데 어떻게 써야할지 감이 안잡혔다. (지금도...) 첫번째 시도에선 .. 2021. 11. 17.
문자열 압축 [프로그래머스] 코드 def solution(s): answer = len(s) for n in range(1, len(s)//2+1): count = 1 temp_sentence = "" for index in range(0, len(s), n): prev_s = s[index:index+n] next_s = s[index+n:index+(2*n)] if prev_s == next_s: count+=1 else: if count != 1: temp_sentence += str(count)+prev_s else: temp_sentence += prev_s count = 1 # print(temp_sentence, len(temp_sentence)) if answer > len(temp_sentence): answer =.. 2021. 11. 14.
삼각 달팽이 [프로그래머스] 쉬운 문제인데 집중력이 약해서 그런지 딴짓하느라 못풀었다. 어려운건 각 조건이 만족할때 방향을 바꿔야 하는데 그부분이 어려웠다. 처음에 떠올린건 더이상 아래방향으로 못내려갈때까지 내려간다. 그 후 왼쪽으로 더이상 왼쪽방향으로 못갈때까지 움직인다. 그후 대각선 위로 대각선 위로 움직인다. 움직일 방향에 숫자가 있다면 아래로 1-2-3을 반복한다. 아래, 왼쪽, 대각선 위가 숫자로 차있다면 멈춘다. 문제는 4번 과정에서 아래, 왼쪽, 대각선을 검사할때 index error(out of bound)가 발생했다는 점이다. 그래서 row+1, column+1 이 n을 넘지 않을때로 제한하는 로직을 추가했다. n ≥3 일때 잘 돌아갔지만 n ≤ 2 일때 돌아가지 않는 문제가 발생했다. 4번 로직을 지우고 새로운 로.. 2021. 11. 5.
n^2 배열 자르기 [프로그래머스] 문제 풀이 정리 문제를 머리속에 집어넣어놓고 풀진 않고 언젠간~ 하면서 지내다가 회사에서 점심 먹고 쉬는와중에 끄적이다 풀었다. (진짜 아무 생각없이 써보다가!) 문제 움짤을 보면 좀더 이해하기 쉽지만 다시 써보자면 입력으로 주어지는 n 숫자 ⇒ n * n 행렬을 만든다. 숫자를 채워넣는다. (위 움짤처럼) 행렬을 1*n^2의 배열로 재배치한다.(한줄로 쭈르륵 줄세운다고 보면 된다.) 입력으로 주어지는 left ~ right 까지의 index에 써진 숫자를 반환한다. 얼핏 생각하면 1~4 단계를 구성해 숫자를 채워넣은뒤, 행렬을 차례대로 지나면서 써져있는 숫자를 반환하면 될 것 같지만 문제에서 주어지는 n의 숫자가 매우 컸다. (n이 커지면 n*n행렬을 만든뒤 숫자를 쓰는 것도 시간이 오래걸릴것...) .. 2021. 10. 30.
전력망을 둘로 나누기 [프로그래머스] 문제 넋두리 나는 문제를 set으로 풀려고 했다. 계획은 이랬다. 특정 node(ex.wires[0][0]) 를 left set에 넣는다. wires중 하나를 제거한다. 잘라진(하나가 제거된) wires 배열을 루프돌면서 left set에 wire[0], wire[1]이 존재한다면 left에 추가 한다. 루프가 끝난시점에 left에 담긴 node 와 그렇지 않은 node set 간의 갯수 차이를 리턴 2-4번 (n-1)번 반복 하면서 차이가 제일 작은 값을 answer로 저장 그런데 자꾸 틀렸다. 틀린 이유를 못찾았는데 예상하기로는 left set에 담기는 조건이 wire[0] 이나, wire[1]이 left set에 존재하는지 여부 였는데, (⇒ if wire[0] in left or wire[1] i.. 2021. 10. 9.
예상 대진표 [프로그래머스] 문제 풀이 예전엔 안 풀리던 문제가 이제는 '음~ 너무 쉽고~' 정도로 풀리는 것 같아서 기분이 좋다. 이 문제는 저렇게 말할 정도로 쉬웠기 때문에 설명을 생략할까 하다가 적어본다. (아니 사실은 쉽게 풀어서 기분좋게 글쓴다.) 문제 조건에 써있듯이 부전승이 없다. 게다가 2^n 승의 참가자가 존재한다 = 그럼 무조건 어디선가 만난다. 그림으로 보자. 우리가 주의 깊게 봐야하는건 left와 right를 나누는 저 경계선이다. 저 경계선을 기준으로 left / right 나뉜다면 무조건 n번 경기를 한다. 만약 선수 a,b가 경계보다 작거나, 클경우엔? 경계선을 다시 그려준 뒤, 해당 경계에서 left / right인지 검사, 나뉜다면 n-1번 경기 아니면 다시 경계선 그리기... 이렇게 반복하는 걸 우린.. 2021. 9. 23.
dfs 유형의 문제 [프로그래머스 & leetcode] 프로그래머스에서 풀었던 문제가 마침 leetcode에서 비슷하게 출제되어 푸는김에 같이 정리하는게 나을듯하다. dfs란? 그림으로 보자면, 마지막 노드까지 전부 확인한 뒤, 이동하는 것을 볼 수 있다. 문제를 보자 문제 설명 n개의 음이 아닌 정수가 있습니다. 이 수를 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다. 예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들려면 다음 다섯 방법을 쓸 수 있습니다. 1+1+1+1+1 = 3 +1-1+1+1+1 = 3 +1+1-1+1+1 = 3 +1+1+1-1+1 = 3 +1+1+1+1-1 = 3 사용할 수 있는 숫자가 담긴 배열 numbers, 타겟 넘버 target이 매개변수로 주어질 때 숫자를 적절히 더하고 빼서 타겟 넘버를 만드는 방법의 수를 ret.. 2021. 9. 20.
반응형

티스토리툴바