[hackerrank][python]Roads and Libraries

https://www.hackerrank.com/challenges/torque-and-development/problem

#!/bin/python3
from pprint import pprint
import sys
from collections import defaultdict

def dfs(graph, start):
  visited, stack = set(), [start]
  while stack:  # dfs는 stack을 이용한다.
    vertex = stack.pop()
    if vertex not in visited:
      visited.add(vertex)
      stack.extend(graph[vertex] - visited)  # 해당 정점에 연결된 것들을 stack에 넣는다.
  return visited
  

def roadsAndLibraries(n, c_lib, c_road, cities):
  total_cost = 0
  
  if c_road >= c_lib or len(cities) == 0: 
    return n*c_lib  # 도서관이 싸니까 도로를 만들 이유가 없다.
  else:  # here be real shits
    city_graph = defaultdict(set)  # 저절로 set이 만들어지기 때문에 add만 하면 됨.
    connected_cities = set() # might make this into a set
    for i in cities:
      city_graph[i[0]].add(i[1])
      city_graph[i[1]].add(i[0])
      connected_cities.add(i[0])
      connected_cities.add(i[1])
    
    # print(city_graph)
    # print(connected_cities)
    isolated_cities = set([i+1 for i in range(n)]) - connected_cities
    
    while connected_cities:  # dfs를 이용하여 도시들을 돌아다닌다. 그리고 도시들이 비어질 때까지 돌아다닌다. 그리고 도시들은 한 묶음(여러그룹일 것이다.)에 끝나지 않는 경우가 많기 때문에 dfs를 여러번 실행해야 한다.
    # if connected_cities:  # it's wrong. Becuase the cities will have multiple groups.
      temp = connected_cities.pop()
      component = dfs(city_graph, temp)
      # print('component', component)
      total_cost += (len(component) - 1)*c_road + c_lib  # 라이브러리 하나에 도로 여러개
      connected_cities -= component  # 지들끼리  연결된 component connected_ciites에서 제외
    return total_cost + len(isolated_cities)*c_lib
    

# 모든 도시가 도서관을 접할 수 있도록 해야 한다.
# 모든 도시에 도서관을 만들거나
# 도서관을 하나 만들어서 연결되어 있는 도시(정점)끼리 도로를 만들어야 한다.
# (도로가 연결되어 있지 않다면 도서관을 연결해야 하겠지...)
#if __name__ == "__main__":
q = int(input().strip())
for a0 in range(q):
    n, m, c_lib, c_road = input().strip().split(' ')
    n, m, c_lib, c_road = [int(n), int(m), int(c_lib), int(c_road)]
    cities = []
    for cities_i in range(m):
       cities_t = [int(cities_temp) for cities_temp in input().strip().split(' ')]
       cities.append(cities_t)

    result = roadsAndLibraries(n, c_lib, c_road, cities)
    print(result)

[hackerrank][python] Cut the sticks

https://www.hackerrank.com/challenges/cut-the-sticks/problem

def cut_sticks(sticks):
  count = 0
  if sticks:
    min_stick = min(sticks)
  else:
    return
  new_sticks = []
  for ele in sticks:
    count += 1
    new_ele = ele - min_stick
    if new_ele != 0:
      new_sticks.append(new_ele)
  print(count)
  cut_sticks(new_sticks)

input()
arr = [int(x) for x in input().strip().split(' ')]
cut_sticks(arr)

from collections import Counter

n = int(input())
arr =  [int(x) for x in input().strip().split(' ')]
counter = Counter(arr)

for i in range(1000):
  if counter[i]:
    print(n)
    n -= counter[i]
  
  if n == 0: break

def cut_sticks(sticks):
  count = 0
  sticks.sort()
  
  while sticks:
    print(len(arr))
    min_stick = sticks[0]
    arr[:] = [ s - min_stick for s in sticks if s > min_stick]

input()
arr = [int(x) for x in input().strip().split(' ')]
cut_sticks(arr)

문제 요약: 막대기 중에 가장 작은 막대기로 나머지 막대기들을 잘라낸다. 한번 자를 때마다 남아있는 막대기를 출력한다.

[python][hackerrank] Library Fine

https://www.hackerrank.com/challenges/library-fine/problem

d1, m1, y1 = (int(a) for a in input().split(' '))
d2, m2, y2 = (int(a) for a in input().split(' '))

yd = y1 - y2
md = m1 - m2
dd = d1 - d2

if yd < 0:
  print(0)
elif yd > 0:
  print(10000 * yd)
elif md < 0:
  print(0)
elif md > 0:
  print(500 * md)
elif dd < 0:
  print(0)
elif dd > 1:
  print(15 * dd)
else:
  print(0)

[python][cpp] 백준 알고리즘 2750 번 풀이

n = int(input())
a = []
for _ in range(n):
  a.append(int(input()))

print('\n'.join(str(e) for e in sorted(a)))

#include iostream
#include vector
#include algorithm


using namespace std;
int main() {
  int n;
  int number;
  cin >> n;
  vector numbers;  
  
  for(int i = 0; i < n; ++i) {
    cin >> number;
    numbers.push_back(number);
  }
  
  sort(numbers.begin(), numbers.end());
  for(auto i : numbers)
    cout << i << endl;
}

[python][algospot] 외발뛰기 (JUMPGAME)

[구종만의 알고리즘 문제해결전략] 내용을 파이썬으로 변경

n = 7
board = [[2,5,1,6,1,4,1],
         [6,1,1,2,2,9,3],
         [7,2,3,2,1,3,1],
         [1,1,3,1,7,1,2],
         [4,1,2,3,4,1,2],  # [4,1,2,3,4,1,3], [4,1,2,3,4,1,2]
         [3,3,1,2,3,4,1],
         [1,5,2,9,4,7,0]]

def jump(x,y):
    if x >= n or y >= n: return  False  # 게임판 밖을 벗어남.
    if x == n-1 and y == n-1:
        # print(board[x][y], x, y)
        return True  # 마지막칸에 도착한경우.
    jump_size = board[x][y]
    
    return jump(x+jump_size, y) or jump(x, y+jump_size)

print(jump(0,0))


# 동적 계획법
cache = [ [None]*n for _ in range(n)]
# print('cache', cache)
def jump2(x,y):
    if x >= n or y >= n: return False
    if x == n-1 and y == n-1: return True

    if cache[x][y] is not None:
        return cache[x][y]
    else:
        jump_size = board[x][y]
        cache[x][y] = jump2(x+jump_size, y) or jump2(x, y+jump_size)
        return cache[x][y]
print(jump2(0,0))

자바스크립트 정규식을 이용한 DOM 객체 클래스 삭제 방법

$('.evtPop').find('.img').removeClass(function (idx, className) {
  console.log('클래스삭제', idx, className);
  return className.match(/win\d/).join(' ');
})

[clojure][designpattern] 반복자패턴 (Iterator pattern)

일단 자바

Iterator i;
while (i.hasNext()) {
  i.next();
}

Node next = root;
while( next != null )
  next = next.next;

클로저에서 반복자에 해당하는 것

(seq [1 2 3]) => (1 2 3)
(seq (list 4 5 6)) => (4 5 6)
(seq #{ 7 8 9}) => (7 8 9)
(seq (int-array 3)) => (0 0 0)
(seq "abc") => (\a \b \c)

시퀀스인가? 반복자는 단순 시퀀스이다.

(first (seq [1 2 3]))
; 1
(rest (seq [1 2 3]))
; (2 3)

시퀀스가 아닌 것으로도 이렇게 돌아다닐 수 있나? 클로저는 자바다. 인터페이스를 구현하면 된다.

(deftype RedGreenBlackTree [& elems]
clojure.lang.Seqable
(seq [self]
;; traverse element in needed order
))

내 생각에는 그냥 죄다 시퀀스로 쓰면 될 것 같다.

[hackerrank][java8][clojure] SolveMeFirst

int 두개 더하기
java

static int solveMeFirst(int a, int b) {
  return a + b;     
}

clojure

(defn solveMeFirst [x y]    
    (+ x y))

여기서 특이한 점은 stdin, stdout 방법을적어놔야할 것 같다. 자바

Scanner in = new Scanner(System.in);
int a = in.nextInt();
int b = in.nextInt();
int sum = solveMeFirst(a, b);
System.out.println(sum);

클로저

(def a (read-line))
(def b (read-line))

(println (solveMeFirst (Integer/parseInt a) (Integer/parseInt b)))

[python][hackerrank] Sherlock and Squares

https://www.hackerrank.com/challenges/sherlock-and-squares/problem

import math

q = int(input().strip())
for _ in range(q):
    a, b = map(int, input().strip().split(' '))
    _start = math.ceil((math.sqrt(a)))
    ret = 0
    while _start**2 <= b:
        ret += 1
        _start += 1
    print(ret)

[clojure][designpattern]책임 연쇄(Chain Of Responsibility) 패턴

비속어를 별표로 변하는 필터를 만들자.

public abstract class Filter {
  protected Filter nextFilter;

  abstract void process(String message);

  public void setNextFilter(Filter nextFilter) {
    this.nextFilter = nextFilter;
  }
}

실제 적용할 필터

class LogFilter extends Filter {
  @Override
  void process(String message) {
    Logger.info(message);
    if (nextFilter != null) nextFilter.process(message);
  }
}

class Profanityfilter extends Filter {
  @Override
  void process(String message) {
    String newMessage = message.replaceAll("fuck","f*ck");
    if (nextFilter != null) nextFilter.process(newMessage);
  }
}

class RejectFilter extends Filter {
  @Override
  void process(String message) {
    System.out.println("RejectFilter");
    if (message.startsWith("[A Project NY]")) {
      if (nextFilter. != null) nextFilter.process(message);
    }
  }
}

class StatisticsFilter extends Filter {
  @Override
  void process(String message) {
    Statistics.addUsedChars(message.length());
    if (nextFilter != null) nextFilter.process(message);
  }
}

1. 각 필터를 만든다. 2. 서로 기차놀이처럼 연결한다. (순서를 만드는 것이다)

Filter rejectFilter = new RejectFilter();
Filter logFilter = new LogFilter();
Filter profanityFilter = new ProfanityFilter();
Filter statsFilter = new StatisticsFilter();

rejectFilter.setNextFilter(logFilter);
logFilter.setNextFilter(profanityFilter);
profanityFilter.setNextFilter(statsFilter);

String message = "[A PROFIT NY] What the fuck?";
rejectFilter.process(message);

clojure 클로저는 각 필터를 함수로 만든다.

;; define filters

(defn log-filter [message]
  (logger/log message)
  message)

(defn stats-filter [message]
  (stats/add-used-chars (count message))
  message)

(defn profanity-filter [message]
  (clojure.string/replace message "fuck" "f*ck"))

(defn reject-filter [message]
  (if (.startsWith message "[A Profit NY]")
    message))

(defn chain [message]
  (some-> message
          reject-filter
          log-filter
          stats-filter
          profanity-filter))

저 some->가 뭐지? some->는 ->와 기능이 같다.
한가지만 빼고 표현식이 nil이면 멈춘다. 그리고 nil을 내뱉는다. nil이 아니면 값을 다음에 넘긴다.

(chain "fuck") => nil
(chain "[A Profit NY] fuck") => "f*ck"

[A profit NY] 가 없으면 reject-filter에서 이미 걸려서 nil이 나옴.

[algorithm] 선택정렬 (selction sort with C and Python)

선택정렬 C언어와 파이썬 비교

main.c

#include 
#include 

#include "selection_sort.h"

void printArray(int value[], int count);

int main()
{
    int values[] = { 80, 75, 10, 60, 15, 49, 12, 25 };
    int count = sizeof(values)/sizeof(int);

    printArray(values, count);

    printf("\n선택 정렬이 시작됩니다 \n");
    selection_sort(values, count);

    printArray(values, count);

    return 0;
}
void printArray(int value[], int count)
{
    int i = 0;
    for(i = 0; i < count; i++) {
        printf("%d ", value[i]);
    }
    printf("\n");
}

selection_sort.h

#ifndef SELECTION_SORT_H_INCLUDED
#define SELECTION_SORT_H_INCLUDED

void selection_sort(int value[], int count);

#endif // SELECTION_SORT_H_INCLUDED

selection_sort.c