백준 algorithm Codility 2진법 format 1956 python

파이썬 알고리즘 : codility, 운동

Codility, 백준 1956

2023년 8월 8일 알고리즘 문제풀이

곧 있을 크래프톤 코딩테스트를 위한 연습으로 오늘은 Codility에서 문제를 풀었다.

혹시 백준에서만 하시는 분들은 해보시길 권한다. 나는 리트코드를 한 경험이 있는데 비슷한 느낌이다.

링크

각 주제별로 문제를 푸는 Lesson의 링크

문제 1

문제

A binary gap within a positive integer N is any maximal sequence of consecutive zeros that is surrounded by ones at both ends in the binary representation of N.

For example, number 9 has binary representation 1001 and contains a binary gap of length 2. The number 529 has binary representation 1000010001 and contains two binary gaps: one of length 4 and one of length 3. The number 20 has binary representation 10100 and contains one binary gap of length 1. The number 15 has binary representation 1111 and has no binary gaps. The number 32 has binary representation 100000 and has no binary gaps.

Write a function:

1

class Solution { public int solution(int N); }

that, given a positive integer N, returns the length of its longest binary gap. The function should return 0 if N doesn’t contain a binary gap.

For example, given N = 1041 the function should return 5, because N has binary representation 10000010001 and so its longest binary gap is of length 5. Given N = 32 the function should return 0, because N has binary representation ‘100000’ and thus no binary gaps.

Write an **efficient** algorithm for the following assumptions:

  • N is an integer within the range [1..2,147,483,647].

Copyright 2009–2023 by Codility Limited. All Rights Reserved. Unauthorized copying, publication or disclosure prohibited.

###

나의 생각

문제가 말하는 바는 다음과 같다. 정수 N을 2진수 형태로 바꾸었을 때, 1로 둘러싸인 연속된 0의 최대 길이를 반환하는 함수를 작성하라는 것이다. 따라서 나는 format함수를 통해 2진수인 문자열을 만들었다. 문자열에서 가장 앞에 있는 0번 index의 값은 무조건 1이다. 따라서 그 다음 1을 만날때를 탐색했다. 1을 만나면 이전 1일 때의 index와 차이가 그동안 0이 나타난 횟수를 의미했으니 그 값을 업데이트한다. 그리고 가장 최근에 만난 1의 index값을 방금 만난 값으로 업데이트 한 후 다시 탐색하는 과정을 반복했다.

그리고 이 format함수는 **문자열**을 반환하므로 1을 찾을 때 숫자가 아니라 문자열 1을 탐색해야 했다.

결과

Total Score : 100%

Correctness : 100%

코드

1
2
3
4
5
6
7
8
9
10

def solution(N):
    word = format(N, 'b')
    d = len(word)
    tmp = 0
    ans = 0
    for i in range(1,d):
        if word[i] == '1':
            ans = max(ans,i-tmp-1)
            tmp = i
    return ans

출처

python의 내장함수 format을 통해 10진수를 바꾼 결과를 문자열로 반환받을 수 있다. 2진법은 두번째 인자로 ‘b’, 8진법은 ‘o’를 넣으면 된다.

문제 2

문제

An array A consisting of N integers is given. Rotation of the array means that each element is shifted right by one index, and the last element of the array is moved to the first place. For example, the rotation of array A = [3, 8, 9, 7, 6] is [6, 3, 8, 9, 7] (elements are shifted right by one index and 6 is moved to the first place).

The goal is to rotate array A K times; that is, each element of A will be shifted to the right K times.

Write a function:

1

def solution(A, K)

that, given an array A consisting of N integers and an integer K, returns the array A rotated K times.

For example, given

1

    A = [3, 8, 9, 7, 6]    K = 3

the function should return [9, 7, 6, 3, 8]. Three rotations were made:

1

    [3, 8, 9, 7, 6] -> [6, 3, 8, 9, 7]    [6, 3, 8, 9, 7] -> [7, 6, 3, 8, 9]    [7, 6, 3, 8, 9] -> [9, 7, 6, 3, 8]

For another example, given

1

    A = [0, 0, 0]    K = 1

the function should return [0, 0, 0]

Given

1

    A = [1, 2, 3, 4]    K = 4

the function should return [1, 2, 3, 4]

Assume that:

  • N and K are integers within the range [0..100];
  • each element of array A is an integer within the range [−1,000..1,000].

In your solution, focus on **correctness**. The performance of your solution will not be the focus of the assessment.

나의 생각

주어진 배열 A에서 가장 오른쪽의 원소를 왼쪽으로 옮기는 동작을 K번 반복한다. 배열의 뒤에서 나와 앞으로 들어가므로 deque을 사용하는 것이 적절하다고 생각했다. 따라서 주어진 배열 A의 원소들을 덱에 넣고 문제에서 말하는 동작을 수행한 후 알맞게 반환하기 위해 다시 list에 넣어줬다.

결과

Task Score: 87%

Correctness : 87%

코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

from collections import deque

def solution(A, K):
    arr =deque()
    for x in A:
        arr.append(x)
    cnt = 0
    while cnt < K:
        cnt += 1
        num = arr.pop()
        arr.appendleft(num)
    ans = []
    for x in arr:
        ans.append(x)
    return ans

87점은 빈 배열이 입력되었을 때의 test case로 인한 것이었다. 문제에서 주어진대로 N과 K의 범위는 0부터 100이었는데, 0일 때를 간과하였다. if not A : return A 코드를 추가해서 빈배열일때를 고려하였더니 100%가 되었다.

백준 1956

문제

1차 시도

나의 생각

bfs나 dfs를 통해 경우를 탐색하면서 사이클이 완성된다면 현재까지 경로의 합을 저장하면서 업데이트 하는 방식으로 구현해야겠다고 생각했다. 흠.. 너무 복잡해서 코드가 완성되지 못했다. 출발지가 고정된게 아니라 각 출발지 때마다 그 출발지로 돌아오는 길이 있는 마지막 마을을 순회해야할까?

결과

오답

코드

X

2차 시도

출처

나의 생각

그래프에 거리를 표시하지 않고 그래프는 길이 있는 경우만 표시하도록 바꾸었다. 그리고 거리에 관한 배열을 새로 만들었다. heap을 이용하였는데, heap에 거리를 첫번째 인자로 두고 출발점과 끝점도 넣어두었다. 우선순위 큐에서 가장 작은 값을 꺼낸다. 그러면 heap에서 거리가 가장 짧은 것과 그 거리의 출발점과 도착점이 나온다. 도착점에서 갈 수 있는 다음 마을을 graph를 통해 찾아내고 그 마을까지의 도로의 거리를 더한다. 즉 현재 출발점 - 현재 도착점 - 다음 도착점 으로 이어지는 길의 길이가 구해진 것. 이 값을 기존에 저장해 두었던 거리 배열에서 찾은 값과 비교하여 더 작다면 업데이트해준다.

이 작업이 반복된 결과는 두 마을을 이동하는 여러 루트 중 최소거리가 heap에 저장된다는 것, 그리고 heap에 있는 다양한 경로 중 거리가 짧은 순서대로 pop된다는 것이다. pop하면서 출발지와 도착지가 같은 원소가 출력됐다면, 사이클 중 이동 거리가 가장 짧다는 의미이므로 그 값을 정답으로 출력한다.

결과

이해 오답

코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

import sys
from heapq import heappop, heappush

v,e = map(int,sys.stdin.readline().split())
graph = [[] for _ in range(v+1)]
dist = [[1e9 for _ in range(v+1)] for _ in range(v+1)]
heap = []
for _ in range(e):
    a,b,c = map(int,sys.stdin.readline().split())
    graph[a].append([c,b])
    dist[a][b] = c
    heappush(heap,[c,a,b])

while heap:
    d,p,q = heappop(heap)
    if p == q:
        print(d)
        break

    if dist[p][q] < d:
        continue

    for next_d, next_q in graph[q]:
        new_d = d + next_d
        if new_d < dist[p][next_q]:
            dist[p][next_q] = new_d
            heappush(heap,[new_d,p,next_q])
else:
    print(-1)

3차시도

나의 생각

기존 2차 시도의 코드는 새로운 기준이 추가되면서, 재채점되었다. 그 결과 메모리초과로 인해 오답처리 되었다.

CATALOG
    algorithm