space of spadework

https://programmers.co.kr/learn/courses/30/lessons/43238 def solution(n, times): answer = 0 left = min(times) right = max(times) * n while left = n: break if checked >= n: answer = mid right = mid - 1 elif checked < n: left = mid + 1 return answer

https://programmers.co.kr/learn/courses/30/lessons/42583 문제 조건 +) 문제에 빠져있는 조건이 있어 계속 틀렸다. "트럭은 1초 다리 1칸씩 전진한다"는 조건을 추가해야 한다. from collections import deque def solution(bridge_length, weight, truck_weights): answer = 0 truck_weights = deque(truck_weights) inBridge = deque([0]*bridge_length) weight_sum = 0 while truck_weights or sum(inBridge) > 0: answer += 1 getOut = inBridge.popleft() weight_sum..

https://programmers.co.kr/learn/courses/30/lessons/42586 def solution(progresses, speeds): answer = [] progresses.reverse() speeds.reverse() # progresses 자체를 stack으로 본다. sec = 0 temp_ans = 0 while progresses: if progresses[-1] + speeds[-1] * sec >= 100: progresses.pop() speeds.pop() temp_ans += 1 else: if temp_ans != 0: answer.append(temp_ans) temp_ans = 0 sec += 1 answer.append(temp_ans) return..

https://programmers.co.kr/learn/courses/30/lessons/42587?language=python3 - 1차 풀이 (flag 사용) from collections import deque def solution(priorities, location): answer = [] stack = deque([i for i in range(0, len(priorities))]) priorities = deque(priorities) while priorities: flag = 0 for priority in priorities: if priority > priorities[0]: flag = 1 break else: priorities.popleft() answer.append(sta..

알고리즘 문제를 풀다보면 흔히 list보다 deque(double ended queue)가 훨씬 빠르다고 한다. deque의 popleft()는 배열의 첫번째 데이터를 꺼내는 것으로 O(1)의 시간복잡도가 걸린다. 그 이유가 무엇인지 궁금하여 찾아보았다. deque는 원형 큐를 확장하여 손쉽게 구현할 수 있다. 다음과 같이 초기화 가능하다. class Deque: rear = 0 front = 0 MAX_SIZE = 100 deq = list() def __init__(self): self.rear = 0 self.front = 0 self.deq = [0 for i in range(self.MAXSIZE)] 이렇게 rear, front 변수를 활용하여 linkedlist와 비슷한 방식으로 삽입, 삭제시..

https://programmers.co.kr/learn/courses/30/lessons/42584 ## use deque from collections import deque def solution(prices): answer = [] prices = deque(prices) sec = 0 while prices: sec = 0 p = prices.popleft() for price in prices: sec += 1 if price < p: break; answer.append(sec) return answer ## use stack def solution(prices): answer = [0] * len(prices) stack = [] # index가 들어갈 stack for i, price i..

Python 2: sys 패키지에서 max값을 제공한다. sys.maxint로 정수 최대값을 구할 수 있다. 이 최대값을 초과할 시 int->long으로 자동전환 된다. Python 3: python3에서 int와 long의 구분이 없어져 int은 unbound다. 만약 word size를 구하고 싶다면 sys.maxsize를 사용한다. PEP 237: Essentially, long renamed to int. That is, there is only one built-in integral type, named int; but it behaves mostly like the old long type. 결론: Python에서 int의 범위는 고려할 필요가 없다. 출처: https://stackoverfl..

queue인 것에서 알 수 있듯이 push, top, pop 메소드가 있으며, 일반 queue에서는 FIFO 구조로 저장하는 선형 자료구조인데 반해, prioirty queue의 비선형 자료구조로 우선순위가 가장 높은 데이터를 가장 먼저 삭제한다. 우선순위는 MAX, MIN으로 지정하기 나름이다. 구현 방식으로는 배열, 연결 리스트, 힙 등이 있다. 보통 최악의 경우라도 가장 나은 성능을 보이는 heap이라는 자료구조로 구현된다. 원소들을 넣고 정렬할 때 heap sort를 사용한다. heap은 완전 이진 트리 구조인데, BST(Binary Search Tree)와 달리 중복된 값이 허용된다. Enqueue(삽입) 예시로 15라는 데이터가 들어왔을때 동작 순서이다. Dequeue(삭제) 20이라는 데이터..

https://app.codility.com/programmers/lessons/5-prefix_sums/passing_cars/ 코딜리티는 (1) 시간제한이 있어 늦장부리지 않고 풀 수 있어 좋다. (2) 테스트케이스도 정확도, 성능측정으로 분리되어 있으며 (3) 화면녹화도 제공하고 (4) 내 소스 시간복잡도도 계산해 주고 (5) 문제도 영어라 가끔 영어문제를 내는 큰 회사들 대비하기 좋다. 나는 성능이 구린 풀이를 잘 하기 때문에 코딜리티로 점검해 보았다. 곧이곧대로 풀지말고 그 안의 룰을 찾아내자 def solution(A): west_sum = 0 len_A = len(A) cnt_one = sum(A) for i in range(len_A): if A[i] == 0: west_sum += cnt..

Hackerrank에서 입출력 소스는 기본으로 제공해주다 보니 타기관 알고리즘 문제를 풀 때 입출력 처리를 못하는 문제가 발생했다. python에서는 input, c++에서는 cin으로 간편하게 처리 가능이지만, Java IO를 위해서는 Scanner, BufferedReader 객체를 사용해야 한다. 주로 Scanner를 많이 사용하지만 속도측면에서는 BufferedReader가 우수하다. Scanner, Sysout import java.util.Scanner; class Main{ public static void main(String[] args){ Scanner sc = new Scanner(System.in); int a; String b; a = sc.nextInt(); sc.nextLine..

시간초과로 여러번 통과하지 못했던 문제이다. 로직이 맞는 것 같은데 시간초과 뜬다면 input() 을 의심해보아야 한다. 몇 번의 input을 더 받아야하는지 알고 있다면 (대부분의 문제의 첫 값은 for문 돌아야 할 횟수를 알려준다) 다음을 활용하도록 하자. input() -> sys.stdin.readline() 풀이) #!/usr/bin/env python # -*- coding: utf-8 -*- import sys def main(n, input_num): # 산술평균 : N개의 수들의 합을 N으로 나눈 값 print(int(round(sum(input_num) / n))) # 중앙값 : N개의 수들을 증가하는 순서로 나열했을 경우 그 중앙에 위치하는 값 sorted_num = sorted(in..

https://www.hackerrank.com/challenges/sparse-arrays/problem?h_r=next-challenge&h_v=zen #!/bin/python3 import math import os import random import re import sys def matchingStrings(strings, queries): s_dict = {} ans = [] for s in strings: if s_dict.get(s): s_dict[s] = s_dict[s] + 1 else: s_dict[s] = 1 for q in queries: ans.append(s_dict.get(q, 0)) return ans if __name__ == '__main__': fptr = open(..

https://www.hackerrank.com/challenges/dynamic-array/problem 식도 다 세워준 문제인데 지문 이해가 좀 어려웠다. input을 아래와 같이 이해하면 쉽게 해결된다. 2 5 // n q 1 0 5 // query_type x y 1 1 7 1 0 3 2 1 0 2 1 1 lastAnswer를 print하는데에 for문 안에서 그때그때 하는 것이 아니라 main 로직에서 return 된 result를 string으로 mapping 시킨 후 print 해주기에 나는 lastAnswer를 list에 담아 반환해주면 된다. 2차원 배열을 이해하는 문제이다. #!/bin/python3 import math import os import random import re im..

java.lang.NullPointerException (NPE) 발생원인: Runtime Exception으로 java말고도 대부분 개발언어에서 자주 발생한다. null 객체를 참조하였을 때 발생한다. 해당 주소를 찾아갔을 때 아무것도 없다는 의미이다. 방어코드: 1) return null 지양하기 null이 "데이터 없음"을 의미할 수 도 있지만 "failure"를 의미하는 경우도 있어 모호하므로 버그가 많이 발생하게 된다. 되도록이면 return null 은 사용하지 않기로 한다. 2) parameter로 null 넘기지 말기 1번과 같은 의미로 어떤 특별한 의미가 없다면 굳이 주지도 받지도 말자. 3) null check 하기 TestObject test = new TestObject(); Str..

java로 개발하다보면 Integer.valueOf(String); Integer.parseInt(String); Map(Integer, String); 처럼 int와 다른 Integer라는 type을 사용하는 걸 볼 수 있다. 이 둘이 어떤 차이가 있는지 알아보도록 하자. 1. int (Primitive 자료형) - '자료형' 을 의미한다. (int, float, long, double 와 같은 하나의 primitive 자료형을 의미) - '산술 연산'이 가능하다. - null로 초기화 불가능 (0으로만 초기화 가능) 2. Integer (Wrapper 클래스-객체) - Wrapper '클래스'를 의미한다. - Unboxing 을 하지 않으면 산술 연산이 불가능하지만, null값을 처리할 수 있다. -..