본문 바로가기
반응형

algorithm82

문자열 압축 [프로그래머스] 코드 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.
Intersection of Two Arrays II [leetcode] 문제 풀이 설명 어려운 문제는 아니였다. 그래도 역시 생각보다 오래 고민했다. 한 시간 안되게? 일단 교집합이라고 문제 제목이 나와있기 때문에 단순히 교집합으로 풀어야 겠다 생각하면 안된다. 무구한 삽질을 이미 다른 문제를 통해 경험해 봤기 때문에 python이 제공하는 set 연산을 하면 안된다는걸 알고 있다. 첫번째 케이스의 경우 set 연산으로 수행할 경우 [2,2] 가 아니라 [2]로 나오게 된다. → 교집합 연산을 위해서는 리스트가 아니라 집합으로 먼저 바뀌어야 하고 그럼 [1,2,2,1] → [1,2] 로 중복이 제거 나는 이렇게 풀었다 (코드를 보면 알겠지만) 크기가 작은 리스트의 숫자를 꺼낸다. 해당 숫자가 다른 리스트에 들어있는지 판단한다. 들어 있다면 해당 숫자를 크기가 큰쪽에서 제거한.. 2021. 9. 18.
입실 퇴실 [프로그래머스] 프로그래머스 7주차 문제이다. 입실과 퇴실이 반복되는 방에서 어떤 경우에도 반드시 만날 수 밖에 없는 손님을 카운트 하는 문제였다. 어떤 경우에는 만나고, 어떤 경우에는 안만나는 상황은 알고리즘 적인 상황이 아니니 분명 무슨 경우의 수가 있을 것이라 가정하고 풀었다. 공책에 몇번 써가면서 내가 세운 규칙은 입실과 퇴실중 입실먼저 수행한다. 방이 비어있는데 입실과 퇴실이 같다면 아무도 만나지 않고 나간다. 퇴실[0]과 입실[last]가 다르다면 입실 먼저! 퇴실[0]와 입실[last]가 같다면 입실 수행후 퇴실 번호가 없을때까지 퇴실만 수행 입실이 비어있다면 반복을 종료! 로 세우고 문제를 풀었다. 손님들 끼리 만나는 경우 meet_matrix 라는 행렬을 만들어 "O"로 표시, 자기 자신은 만남의 카운트.. 2021. 9. 15.
복서 정렬하기 [프로그래머스] 저번 4주차 때와 마찬가지로 딕셔너리 소팅 문제로 접근해 풀었다. python dictionary sort 정리 (sort by key & value) python dictionary sort 정리 (sort by key & value) 매번 헷갈리고 알고리즘 문제 풀때마다 찾아보길래 이번 기회에 블로그에 적음으로 찾는 수고를 덜고자 한다. 프로그래머스에서 이번에 위클리 챌린지라고 leetcode에서 하는것 처럼 매주 문제 hoonzi-text.tistory.com 각 복서 마다 속성들 몇번 이겼는지 ⇒ win_count 자기보다 무거운 사람과 싸워서 이겼는지 ⇒ weight_count 몇번 선수인지 ⇒ index 자기 몸무게는 몇인지 ⇒ weights[index] 등을 dictionary로 저장하고 해.. 2021. 9. 7.
반응형

티스토리툴바