Given an array of n distinct integers, transform the array into a zig zag sequence by permuting the array elements. A sequence will be called a zig zag sequence if the first k elements in the sequence are in increasing order and the last k elements are in decreasing order, where k=(n+1)/2. You need to find the lexicographically smallest zig zag sequence of the given array. 

Example.

a [2, 3, 5, 1, 4]

Now if we permute the array as [1, 4, 5, 3, 2], the result is a zig zag sequence.

Debug the given function findZigZagSequence to return the appropriate zig zag sequence for the given input array.

Note: You can modify at most three lines in the given code. You cannot add or remove lines of code.

To restore the original code, click on the icon to the right of the language selector.

Input Format

The first line contains t the number of test cases. The first line of each test case contains an integer n, denoting the number of array elements. The next line of the test case contains n elements of array a.

Constraints

1 <= t <= 20

1 <= n <= 10000(n is always odd)

1 <= a_i <= 10^9

Output Format

For each test cases, print the elements of the transformed zig zag sequence in a single line.

def findZigZagSequence(a, n):
    a.sort()
    mid = int(n/2) # 수정 (1)

    a[mid], a[n-1] = a[n-1], a[mid]
    st = mid + 1
    ed = n - 2 # 수정 (2)

    while(st <= ed):
        a[st], a[ed] = a[ed], a[st]
        st = st + 1 
        ed = ed - 1 # 수정 (3)

    for i in range (n):
        if i == n-1:
            print(a[i])
        else:
            print(a[i], end = ' ')
    return

이 문제는 구현해서 푸는 문제가 아니라 문제를 디버깅하여 수정하는 문제다.

이런 유형의 문제는 처음이라 조금 당황했었다.

전 날 고민하다가 도저히 안 풀려서 오늘 아침에 다시 풀었는데. 아주 굿!  잘 풀렸다.

문제가 안 풀리면 잠시 쉬고 푸는 것도 좋은 선택이다. 

Interview Preparation Kits > 1 Week Preparation Kit > Day 2 > Counting Sort 1

Comparison Sorting

Quicksort usually has a running time of n*log(n), but is there an algorithm that can sort even faster? In general, this is not possible. Most sorting algorithms are comparison sorts, i.e. they sort a list just by comparing the elements to one another. A comparison sort algorithm cannot beat n*log(n) (worst-case) running time, since n*log(n) represents the minimum number of comparisons needed to know where to place each element. For more details, you can see these notes (PDF).

Alternative Sorting

Another sorting method, the counting sort, does not require comparison. Instead, you create an integer array whose index range covers the entire range of values in your array to sort. Each time a value occurs in the original array, you increment the counter at that index. At the end, run through your counting array, printing the value of each non-zero valued index that number of times.

Example

arr  = [1, 1, 3, 2, 1]

All of the values are in the range [0 ... 3], so create an array of zeros, result = [0, 0, 0, 0]. The results of each iteration follow:

i	arr[i]	result
0	1	[0, 1, 0, 0]
1	1	[0, 2, 0, 0]
2	3	[0, 2, 0, 1]
3	2	[0, 2, 1, 1]
4	1	[0, 3, 1, 1]

The frequency array is [0, 3, 1, 1]. These values can be used to create the sorted array as well: sorted = [1, 1, 1, 2, 3].

Note

For this exercise, always return a frequency array with 100 elements. The example above shows only the first 4 elements, the remainder being zeros.

Challenge

Given a list of integers, count and return the number of times each value appears as an array of integers.

Function Description

Complete the countingSort function in the editor below.

countingSort has the following parameter(s):

• arr[n]: an array of integers

Returns

• int[100]: a frequency array

Input Format

The first line contains an integer n, the number of items in arr.

Each of the next n lines contains an integer arr[i] where 0 <= i < n.

Constraints

100 <= n <= 10^6

0 <= arr[i] < 100

Sample Input

100
63 25 73 1 98 73 56 84 86 57 16 83 8 25 81 56 9 53 98 67 99 12 83 89 80 91 39 86 76 85 74 39 25 90 59 10 94 32 44 3 89 30 27 79 46 96 27 32 18 21 92 69 81 40 40 34 68 78 24 87 42 69 23 41 78 22 6 90 99 89 50 30 20 1 43 3 70 95 33 46 44 9 69 48 33 60 65 16 82 67 61 32 21 79 75 75 13 87 70 33  

Sample Output

0 2 0 2 0 0 1 0 1 2 1 0 1 1 0 0 2 0 1 0 1 2 1 1 1 3 0 2 0 0 2 0 3 3 1 0 0 0 0 2 2 1 1 1 2 0 2 0 1 0 1 0 0 1 0 0 2 1 0 1 1 1 0 1 0 1 0 2 1 3 2 0 0 2 1 2 1 0 2 2 1 2 1 2 1 1 2 2 0 3 2 1 1 0 1 1 1 0 2 2

Explanation

Each of the resulting values result[i] represents the number of times i appeared in arr.

#!/bin/python3

import math
import os
import random
import re
import sys

#
# Complete the 'countingSort' function below.
#
# The function is expected to return an INTEGER_ARRAY.
# The function accepts INTEGER_ARRAY arr as parameter.
#

def countingSort(arr):
    # Write your code here
    lst = [0 for i in range(100)]
    for i in arr:
        lst[i] += 1
    print(lst)
    return lst

if __name__ == '__main__':
    fptr = open(os.environ['OUTPUT_PATH'], 'w')

    n = int(input().strip())

    arr = list(map(int, input().rstrip().split()))

    result = countingSort(arr)

    fptr.write(' '.join(map(str, result)))
    fptr.write('\n')

    fptr.close()

- 제약조건을 똑바로 읽자

Given a square matrix, calculate the absolute difference between the sums of its diagonals.

For example, the square matrix arr is shown below:

1 2 3
4 5 6
9 8 9

The left-to-right diagonal = 1 + 5 + 9 = 15. The right to left diagonal = 3 + 5 + 9 = 17. Their absolute difference is |15 - 17| = 2.

Function description

Complete the diagonalDifference function in the editor below.

diagonalDifference takes the following parameter:

• int arr[n][m]: an array of integers

Return

• int: the absolute diagonal difference

Input Format

The first line contains a single integer, n, the number of rows and columns in the square matrix arr.

Each of the next n lines describes a row, arr[i], and consists of n space-separated integers -100 < arr[i][j] <= 100.

Constraints

Output Format

Return the absolute difference between the sums of the matrix's two diagonals as a single integer.

Sample Input

3 11 2 4 4 5 6 10 8 -12

Sample Output

15

Explanation

The primary diagonal is:

11
   5
     -12

Sum across the primary diagonal: 11 + 5 - 12 = 4

The secondary diagonal is:

     4
   5
10

Sum across the secondary diagonal: 4 + 5 + 10 = 19

Difference: |4 - 19| = 15

Note: |x| is the absolute value of x

#!/bin/python3

import math
import os
import random
import re
import sys

#
# Complete the 'diagonalDifference' function below.
#
# The function is expected to return an INTEGER.
# The function accepts 2D_INTEGER_ARRAY arr as parameter.
#
'''
3
11 2 4
4 5 6
10 8 -12
'''
def diagonalDifference(arr):
    # Write your code here
    dig = 0
    anti_dig = 0
    l = len(arr[0])

    for i in range(l):
        dig += arr[i][i]
        anti_dig += arr[i][(l-1)-i]

    return abs(dig-anti_dig)

if __name__ == '__main__':
    # fptr = open(os.environ['OUTPUT_PATH'], 'w')

    n = int(input().strip())

    arr = []

    for _ in range(n):
        arr.append(list(map(int, input().rstrip().split())))

    result = diagonalDifference(arr)
    print(result)

    # fptr.write(str(result) + '\n')
    #
    # fptr.close()

Interview Preparation Kits > 1 Week Preparation Kit > Day 2 > Lonely Integer

Given an array of integers, where all elements but one occur twice, find the unique element.

Example

a = [1, 2, 3, 4, 3, 2, 1]

The unique element is 4.

Function Description

Complete the lonelyinteger function in the editor below.

lonelyinteger has the following parameter(s):

• int a[n]: an array of integers

Returns

• int: the element that occurs only once

Input Format

The first line contains a single integer, n, the number of integers in the array.

The second line contains n space-separated integers that describe the values in a.

Constraints

• 1 <= n < 100
• It is guaranteed that n is an odd number and that there is one unique element.
• 0 <= a[i] <= 100, where 0 <= i < n.

#!/bin/python3

import math
import os
import random
import re
import sys
import collections


#
# Complete the 'lonelyinteger' function below.
#
# The function is expected to return an INTEGER.
# The function accepts INTEGER_ARRAY a as parameter.
#

# def lonelyinteger(a):
#     # Write your code here
#     arr = []
#     temp = collections.Counter(a)
#     for i in sorted(temp.items()):
#         arr.append(i)
#     print(arr[-1][0])
#     return arr[-1][0]

def lonelyinteger(a):
    # Write your code here
    arr = []
    temp = collections.Counter(a)
    for i in (temp.items()):
        num, cnt = i
        if cnt == 1:
            return num
    
if __name__ == '__main__':
    fptr = open(os.environ['OUTPUT_PATH'], 'w')

    n = int(input().strip())

    a = list(map(int, input().rstrip().split()))

    result = lonelyinteger(a)

    fptr.write(str(result) + '\n')

    fptr.close()

- sort와 sorted의 명확한 차이에 대해 다시 한 번 공부해야겠다. 

- collections의 counter 메소드는 매우 유용하므로 알고 있으면 좋을 것이다!

07:05:45PM

19:05:45

#!/bin/python3

import math
import os
import random
import re
import sys

#
# Complete the 'timeConversion' function below.
#
# The function is expected to return a STRING.
# The function accepts STRING s as parameter.
#

def timeConversion(s):
    # Write your code here
    if s.endswith('PM'):
        hh, mm, ss = s.split(':')
        if int(hh) < 12:
            new_hh = str(int(hh)+12)
            s = new_hh + ':' + mm + ":" + ss[:-2]
            print(s)
            return s
    else:
        hh, mm, ss = s.split(':')
        new_hh = str(int(hh)-12).zfill(2)
        s = new_hh + ':' + mm + ":" + ss[:-2]
        print(s)
        return s

if __name__ == '__main__':
    fptr = open(os.environ['OUTPUT_PATH'], 'w')

    s = input()

    result = timeConversion(s)

    fptr.write(result + '\n')

    fptr.close()

테스트 케이스 2, 4, 6 실패

헉. Test case 2, 4, 6번을 통과하지 못 했다.  

해커랭크는 Test case를 공개해준다! 매우 땡베감 .. (5개 한정인듯)

테스트 케이스를 분석해보니, 올바르게 AM/PM을 잘 입력했을 때 리턴 값을 정해진 출력 형식에 맞추지 않아서 통과하지 못했다. 

따라서 아래와 같이 코드를 수정해주었다.

def timeConversion(s):
    # Write your code here
    if s.endswith('PM'):
        hh, mm, ss = s.split(':')
        if int(hh) < 12:
            new_hh = str(int(hh)+12)
            s = new_hh + ':' + mm + ":" + ss[:-2]
            return s
        else:
            print(s[:-2])
            return s[:-2]
    else:
        hh, mm, ss = s.split(':')
        if int(hh) < 12:
            print(s[:-2])
            return s[:-2]
        else:
            new_hh = str(int(hh)-12).zfill(2)
            s = new_hh + ':' + mm + ":" + ss[:-2]
            print(s)
            return s

통과가 되었다! 굿!

새로 알게 된 함수

string.endswitch(value) : 문자열이 value로 끝나는 문자열

string.startswitch(value) : 문자열이 value로 시작하는 문자열

str(str_num).zfill(num) : 한 자릿 수 숫자를 원하는 여러 자릿수 형태로 만들어주는 함수 

ex) str(7).zfill(2) | output : `07` 

코딩테스트를 오랜만에 하다보니 머리가 굳었다. 하지만 여전히 재밌다!

HackerRank - 1 Week Preparation Kit - Day1 - Plus Minus

Mini-Max Sum

16 24

1 2 3 4 5

10 14

#!/bin/python3

import math
import os
import random
import re
import sys

#
# Complete the 'miniMaxSum' function below.
#
# The function accepts INTEGER_ARRAY arr as parameter.
#

def miniMaxSum(arr):
    # Write your code here
   sort_arr = arr.sort()
   min_ = sum(arr[:-1])
   max_ = sum(arr[1:])
   print(f"{min_} {max_}") 

if __name__ == '__main__':

    arr = list(map(int, input().rstrip().split()))

    miniMaxSum(arr)

HackerRank - 1 Week Preparation Kit - Day1 - Plus Minus

0.400000
0.400000
0.200000

STDIN           Function
-----           --------
6               arr[] size n = 6
-4 3 -9 0 4 1   arr = [-4, 3, -9, 0, 4, 1]

0.500000
0.333333
0.166667

import math
import os
import random
import re
import sys


#
# Complete the 'plusMinus' function below.
#
# The function accepts INTEGER_ARRAY arr as parameter.
#

def plusMinus(arr):
    # Write your code here
    pos = 0
    nag = 0
    zero = 0

    for i in arr:
        if i > 0:
            pos += 1
        elif i < 0:
            nag += 1
        else:
            zero += 1
    print("{: .6f}\n{: .6f}\n{: 6f}".format(pos / len(arr), nag / len(arr), zero / len(arr)))


if __name__ == '__main__':
    n = int(input().strip())
    arr = list(map(int, input().rstrip().split()))

    plusMinus(arr)

1일차라 그런지 생각보다 쉽다. 굿

오늘 부터 해커랭크 코딩테스트를 연습할 것이다. https://www.hackerrank.com/

해커랭크는 해외 코딩테스트 사이트로, 모두 영어로 되어있다. 

Interview Preparation Kits

1 week/ 1 month/ 3 month Kit가 있는데, 일주일 먼저 도전! 

1 Week Preparation Kit

Day1에 들어가보니, 세 문제와 테스트를 해볼 수 있는 문제(?)가 있다. 

문제 확인

지원되는 programming language를 확인해보니 다양했다.  

나는 프로그래머스와 백준 문제만 풀어봤는데, 프로그래머스의 레이아웃 형태와 거의 유사하다. 

1 Week 챌린지 레츠고!