JungPadak 블로그

leetcode 1. two sum

06 Oct 2017 | 알고리즘 프로그래밍

문제출처

문제

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

Example:
Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

풀이코드

def two_sum(nums, target):
    for idx, num in enumerate(nums):
        if target - num in nums:
            return idx, nums.index(target-num)

다른사람풀이

  • hash table을 활용 (O(n))
def two_sum(nums,target):
    dic = {}
    i = 0
    for num in nums:
        if target - num in dic:
            return dic[target-num], i
        d[num] = i
        i += 1

level 4. 최고의 집합

04 Oct 2017 | 알고리즘 프로그래밍

문제출처

문제

자연수 N개로 이루어진 집합 중에, 각 원소의 합이 S가 되는 수의 집합은 여러 가지가 존재합니다.
최고의 집합은, 위의 조건을 만족하는 집합 중 각 원소의 곱이 최대가 되는 집합을 의미합니다.

집합 원소의 개수 n과 원소들의 합 s가 주어지면,
최고의 집합을 찾아 원소를 오름차순으로 반환해주는 bestSet 함수를 만들어 보세요.
만약 조건을 만족하는 집합이 없을 때는 배열 맨 앞에 –1을 담아 반환하면 됩니다.
예를 들어 n=3, s=13이면 [4,4,5]가 반환됩니다.
(자바는 집합이 없는 경우 크기가 1인 배열에 -1을 담아 반환해주세요.)

풀이코드

  • 처음에는 itertools, functools 모듈을 임포트해서 주어진 길이와 합 조건에 맞는 모든 리스트의 경우의 수를 구했다.
  • 모든 경우의 수를 구하고 for 문을 돌리다 보니 실행시간이 오래 걸리는 문제가 발생한다.
  • 참 어렵게도 풀었다..

첫번재 시도 - 느리다

def bestSet(n, s):
    import itertools
    from functools import reduce
    if n > s:
        return [-1]
    combinations = [i for i in itertools.combinations_with_replacement(range(s+1), n) if sum(i) == s]
    multiply_li = [reduce(lambda x,y: x*y, combination) for combination in combinations]
    index = multiply_li.index(max(multiply_li))
    return sorted(list(combinations[index]))

두번째 시도

  • 첫번째 방법으로 풀고나니 이렇게 어렵게 풀 문제가 아닌것 같다는 생각이 들었다.
  • 단순한 예시를 사용해서 곱이 최대가 되는 경우를 살펴보니 각 요소의 편차가 가장 작을 때 곱이 최대가 되는것 같다.
def bestSet(n, s):
    if n > s:
        return [-1]
    portion, remainder = divmod(s, n)
    li = [portion] * n
    for i in range(remainder):
        li[i] += 1

    return sorted(li)

세번째 시도

def bestSet(n, s):
    if n > s:
        return [-1]
    portion, remainder = divmod(s, n)
    li = [portion] * n
    while remainder > 0:
        li[li.index(min(li))] += 1
        remainder -= 1

    return sorted(li)

codility 5-2. PassingCars

12 Jun 2017 | 알고리즘 프로그래밍

문제출처

문제

A non-empty zero-indexed array A consisting of N integers is given.
The consecutive elements of array A represent consecutive cars on a road.

Array A contains only 0s and/or 1s:

0 represents a car traveling east,
1 represents a car traveling west.
The goal is to count passing cars.
We say that a pair of cars (P, Q), where 0 ≤ P < Q < N, is passing when P is traveling to the east and Q is traveling to the west.

For example, consider array A such that:

  A[0] = 0
  A[1] = 1
  A[2] = 0
  A[3] = 1
  A[4] = 1
We have five pairs of passing cars: (0, 1), (0, 3), (0, 4), (2, 3), (2, 4).

Write a function:

def solution(A)

that, given a non-empty zero-indexed array A of N integers,
returns the number of pairs of passing cars.

The function should return −1 if the number of pairs of passing cars exceeds 1,000,000,000.

For example, given:

  A[0] = 0
  A[1] = 1
  A[2] = 0
  A[3] = 1
  A[4] = 1
the function should return 5, as explained above.

Assume that:

N is an integer within the range [1..100,000];
each element of array A is an integer that can have one of the following values: 0, 1.
Complexity:

expected worst-case time complexity is O(N);
expected worst-case space complexity is O(1),
beyond input storage (not counting the storage required for input arguments).

풀이코드 - O(n^2)

  • Detected time complexity: O(N)
  • 조합 가능한 (0,1) pair의 갯수를 찾는다
  • 조건
    • 0의 index < 1의 index
    • pair의 갯수가 100만이 넘으면 -1 리턴
    • 시간 복잡도 O(N)
def solution(A):
    index_zero = [i for i, x in enumerate(A) if x == 0]
    result = 0
    for i in index_zero:
        result += A[i+1:].count(1)

    if result > 1000000000:
        return -1
    return result

다른사람 풀이

  • 리스트를 순회하면서, 0의 갯수를 누적해서 더하고, 1을 만나면 누적 값을 result에 합산한다
def solution(A):
    result = 0
    count_zero = 0
    for i in A:
        if i == 1 and count_zero == 0:
            continue
        elif i == 0:
            count_zero += 1
        elif i == 1:
            result += count_zero

    if result > 1000000000:
        return -1
    return result

codility 10-2. CountFactors

12 Jun 2017 | 알고리즘 프로그래밍

문제출처

문제

A positive integer D is a factor of a positive integer N if there exists an integer M such that N = D * M. For example, 6 is a factor of 24, because M = 4 satisfies the above condition (24 = 6 * 4).

Write a function: def solution(N) that, given a positive integer N, returns the number of its factors. For example, given N = 24, the function should return 8, because 24 has 8 factors, namely 1, 2, 3, 4, 6, 8, 12, 24. There are no other factors of 24.

Assume that: N is an integer within the range [1..2,147,483,647]. Complexity: expected worst-case time complexity is O(sqrt(N)); expected worst-case space complexity is O(1).

풀이코드

  • 시간복잡도 : O(sqrt(N))
  • 1 ~ 루트 N 까지의 숫자만 검색하여 시간복잡도 O(sqrt(N)) 으로 연산
def solution(N):
    i = 1
    result = 0
    while i**2 <= N:
        print(i)
        if i ** 2 == N:
            result += 1
        elif N % i == 0:
            result += 2
        i += 1
    return result

다른사람 코드

def solution(N):
    candidate = 1
    result = 0
    while candidate * candidate < N:
        # N has two factors: candidate and N // candidate
        if N % candidate == 0:      
          result += 2

        candidate += 1

    # If N is square of some value.
    if candidate * candidate == N:  result += 1

    return result

level 1. 문자열 내림차순으로 배치하기 (java)

11 Jun 2017 | 알고리즘 프로그래밍

문제

reverseStr 메소드는 String형 변수 str을 매개변수로 입력받습니다. str에 나타나는 문자를 큰것부터 작은 순으로 정렬해 새로운 String을 리턴해주세요. str는 영문 대소문자로만 구성되어 있으며, 대문자는 소문자보다 작은 것으로 간주합니다. 예를들어 str이 “Zbcdefg”면 “gfedcbZ”을 리턴하면 됩니다.

풀이코드 (java)

import java.util.Arrays;
import java.util.Collections;

public class ReverseStr {
  public String reverseStr(String str){
    String[] array = str.split("");
    Arrays.sort(array);
    Collections.reverse(Arrays.asList(array));
    return  String.join("",array);
  }

// 아래는 테스트로 출력해 보기 위한 코드입니다.
  public static void main(String[] args) {
    ReverseStr rs = new ReverseStr();
    System.out.println( rs.reverseStr("Zbcdefg") );
  }
}

다른사람 코드

import java.util.Arrays;

public class ReverseStr {
    public String reverseStr(String str){
      char[] sol = str.toCharArray();
      Arrays.sort(sol);
      return new StringBuilder(new String(sol)).reverse().toString();
    }

    // 아래는 테스트로 출력해 보기 위한 코드입니다.
    public static void main(String[] args) {
        ReverseStr rs = new ReverseStr();
        System.out.println( rs.reverseStr("Zbcdefg") );
    }
}

import java.util.Arrays;
import java.util.Collections;

public class ReverseStr {
    public String reverseStr(String str){
        String[] array = str.split("");
        Arrays.sort(array,  Collections.reverseOrder());

        return String.join("", array);
    }

    // 아래는 테스트로 출력해 보기 위한 코드입니다.
    public static void main(String[] args) {
        ReverseStr rs = new ReverseStr();
        System.out.println( rs.reverseStr("Zbcdefg") );
    }
}