01_Study►Python

PythonCodeFight-Day19

Day 19

Q25. Minesweeper

In the popular Minesweeper game you have a board with some mines and those cells that don’t contain a mine have a number in it that indicates the total number of mines in the neighboring cells. Starting off with some arrangement of mines we want to create a Minesweeper game setup.

제출 코드

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
30
31
32
33
34
35
36
37
import numpy as np

def minesweeper(matrix):
import numpy as np

def minesweeper(matrix):
    row = len(matrix)
    col = len(matrix[0])

    MineCounterMat = np.zeros((row, col))

    for idx_row in range(row):
        for idx_col in range(col): 
            MineCounter = 0

            if idx_row == 0:
                idx_row_set = [idx_row, idx_row + 1]
            elif idx_row == row-1:
                idx_row_set = [idx_row - 1, idx_row]
            else:
                idx_row_set = [idx_row - 1, idx_row, idx_row + 1]

            if idx_col == 0:
                idx_col_set = [idx_col, idx_col + 1]
            elif idx_col == col-1:
                idx_col_set = [idx_col - 1, idx_col]
            else:
                idx_col_set = [idx_col - 1, idx_col, idx_col + 1]

            for mine_row in idx_row_set:
                for mine_col in idx_col_set:
                    if not ((mine_row == idx_row) and (mine_col == idx_col)):
                        if matrix[mine_row][mine_col]:
                            MineCounter = MineCounter + 1

            MineCounterMat[idx_row][idx_col] = MineCounter
    return MineCounterMat

작성 흐름

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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
# Test case

import numpy as np

matrix = [[True, False, False],
          [False, True, False],
          [False, False, False]]

# 알고리즘 생각해보기
# 자기 자신의 값을 제외하고, 현재 인덱스의 지뢰 개수는 현재 위치 값의 주위에 있는 true 값의 개수

# 행의 갯수
row = len(matrix)

# 열의 갯수
col = len(matrix[0])

# 지뢰 개수를 담을 매트릭스
MineCounterMat = np.zeros((row, col))

# 매트릭스 확인
print(matrix)

# 행, 열 개수 확인
print(row)
print(col)

# 전체 매트릭스의 인덱스에 대해 반복
for idx_row in range(row):
    for idx_col in range(col): 

        # 주위의 지뢰 갯수 찾기
        MineCounter = 0

        # 매트릭스의 테두리 부분은 주위 개수가 다르기 때문에 인덱스를 지정해주어야함
        # 행 인덱스 지정
        if idx_row == 0:
            idx_row_set = [idx_row, idx_row + 1]
        elif idx_row == row-1:
            idx_row_set = [idx_row - 1, idx_row]
        else:
            idx_row_set = [idx_row - 1, idx_row, idx_row + 1]

        # 열 인덱스 지정
        if idx_col == 0:
            idx_col_set = [idx_col, idx_col + 1]
        elif idx_col == col-1:
            idx_col_set = [idx_col - 1, idx_col]
        else:
            idx_col_set = [idx_col - 1, idx_col, idx_col + 1]

        # 지정한 인덱스 확인
        print(idx_row_set)
        print(idx_col_set)

        # 지정한 인덱스에 대해서 반복
        for mine_row in idx_row_set:
            for mine_col in idx_col_set:
                print("row: %d, col: %d" % (idx_row, idx_col))
                print("mine_row: %d, mine_col: %d" % (mine_row, mine_col))

                # 자기 자신을 제외한 주위의 값을 확인해서 지뢰 개수 세기
                if not ((mine_row == idx_row) and (mine_col == idx_col)):
                    if matrix[mine_row][mine_col]:
                        MineCounter = MineCounter + 1
                        print("Mine Counter: %d" % (MineCounter))

        # 현재 인덱스에 지뢰 개수 넣기
        MineCounterMat[idx_row][idx_col] = MineCounter
        print(MineCounterMat)
01_Study►Python

PythonCodeFight-Day18

Day_18

Intro

Q24. Mindsweeper

In the popular Minesweeper game you have a board with some mines and those cells that don’t contain a mine have a number in it that indicates the total number of mines in the neighboring cells. Starting off with some arrangement of mines we want to create a Minesweeper game setup.

알고리즘 고민, 및 러프한 코드 작성 중!

작성 흐름

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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
# Test case

import numpy as np

matrix = [[True, False, False],
          [False, True, False],
          [False, False, False]]

# 알고리즘 생각해보기

# 만약 현재 값이 true인 경우, 현재 인덱스의 값은 1
# 만약 현재 값이 false인 경우, 현재 인덱스의 값은 현재 위치 값의 주위에 true 개수

row = len(matrix)
col = len(matrix[0])

MineCounterMat = np.zeros((row, col))

print(row)
print(col)

for idx_row in range(row):

    for idx_col in range(col): 

        MineCounter = 0

        CurrVal = matrix[idx_row][idx_col]

        if idx_row == 0:
            idx_row_set = [idx_row, idx_row + 1]
        if idx_row == row:
            idx_row_set = [idx_row - 1, idx_row]

        if idx_col == 0:
            idx_col_set = [idx_col, idx_col + 1]
        if idx_col == col:
            idx_col_set = [idx_col - 1, idx_col]

        print(idx_row_set)
        print(idx_col_set)
        for mine_row in idx_row_set:
            for mine_col in idx_col_set:
                if matrix[mine_row][mine_col]:
                    print(mine_row)
                    print(mine_col)
                    MineCounter = MineCounter + 1

        MineCounterMat[idx_row][idx_col] = MineCounter

print(MineCounterMat)
01_Study►Python

PythonCodeFight-Day17

Day_17

Intro

Q23. Box Blur

Last night you partied a little too hard. Now there’s a black and white photo of you that’s about to go viral! You can’t let this ruin your reputation, so you want to apply the box blur algorithm to the photo to hide its content.

The pixels in the input image are represented as integers. The algorithm distorts the input image in the following way: Every pixel x in the output image has a value equal to the average value of the pixel values from the 3 × 3 square that has its center at x, including x itself. All the pixels on the border of x are then removed.

Return the blurred image as an integer, with the fractions rounded down.

제출 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
import numpy as np

def boxBlur(image):
    Row = len(image)
    Col = len(image[0])

    BlurSumSet = np.zeros((Row-2,Col-2))

    for i in range(1, Row-1, 1):
        for j in range(1, Col-1, 1):
            BlurSum = int((image[i-1][j-1] + image[i-1][j] + image[i-1][j+1] + image[i][j-1] + image[i][j] + image[i][j+1] + image[i+1][j-1] + image[i+1][j] + image[i+1][j+1])/9)
            BlurSumSet[i-1][j-1] = BlurSum

    return BlurSumSet

작성 흐름

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
import numpy as np

# test case
image = [[7, 4, 0, 1], 
         [5, 6, 2, 2], 
         [6, 10, 7, 8], 
         [1, 4, 2, 0]]

print("Row: %d" % (len(image)))
print("Col: %d" % (len(image[0])))

# 행, 열 사이즈 찾기
Row = len(image)
Col = len(image[0])

# 3x3이면 양쪽 위아래 1개씩 값을 빼야하므로, 각 행, 열 사이즈에서 2씩 뺀 빈 배열 선언
BlurSumSet = np.zeros((Row-2,Col-2))

for i in range(1, Row-1, 1):
    for j in range(1, Col-1, 1):
        print("Row: %d, Col: %d" % (i, j)) # center point 찾기
        # BlurSum 찾기
        BlurSum = int((image[i-1][j-1] + image[i-1][j] + image[i-1][j+1] + image[i][j-1] + image[i][j] + image[i][j+1] + image[i+1][j-1] + image[i+1][j] + image[i+1][j+1])/9)
        # set에 넣기
        BlurSumSet[i-1][j-1] = BlurSum
        print(BlurSum)
print(BlurSumSet)
01_Study►Python

PythonCodeFight-Day16

Day_16

Intro

Q22. avoidObstacles

You are given an array of integers representing coordinates of obstacles situated on a straight line.
Assume that you are jumping from the point with coordinate 0 to the right. You are allowed only to make jumps of the same length represented by some integer.
Find the minimal length of the jump enough to avoid all the obstacles.

제출 코드

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
def avoidObstacles(inputArray):
    inputSort = sorted(inputArray)

    StepLength = 1
    ArrIdx = 0
    CurrStep = 0


    while 1:
        
        CurrObs = inputSort[ArrIdx]

        if CurrObs == CurrStep:
            ArrIdx = 0
            StepLength = StepLength + 1
            CurrStep = 0
            continue
        elif CurrObs < CurrStep:
            ArrIdx = ArrIdx + 1
            if ArrIdx == len(inputSort):
                break        
            continue
        else:
            CurrStep = CurrStep + StepLength
            continue
            
    return StepLength

작성 흐름

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
30
31
32
33
34
35
36
37
38
39
# Test case
inputArray = [1, 4, 10, 6, 2]

# 값을 정렬
inputSort = sorted(inputArray)
print(inputSort)

StepLength = 1
ArrIdx = 0
CurrStep = 0
NoPassFlag = 0

while 1:
    print('Current Step Length: %d' % (StepLength))
    
    CurrObs = inputSort[ArrIdx]
    print('Current obstacle: %d' % (CurrObs))
    print('Current step: %d' % (CurrStep))

    if CurrObs == CurrStep:
        print("Can't pass current obstacles")
        ArrIdx = 0
        StepLength = StepLength + 1
        CurrStep = 0
        print("Add step length")
        print(" ")
        continue
    elif CurrObs < CurrStep:
        print("Add obstacle index")
        ArrIdx = ArrIdx + 1
        if ArrIdx == len(inputSort):
            break        
        continue
    else:
        print("Add step length to current step ")
        CurrStep = CurrStep + StepLength
        continue
        
print("Break Step Length: %d" % (StepLength))
01_Study►Python

PythonCodeFight-Day15

Day_15

Intro

Q22. avoidObstacles

You are given an array of integers representing coordinates of obstacles situated on a straight line.
Assume that you are jumping from the point with coordinate 0 to the right. You are allowed only to make jumps of the same length represented by some integer.
Find the minimal length of the jump enough to avoid all the obstacles.

제출 코드

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
30
31
32
33
from math import gcd

def solution(arr):
    def lcm(x,y):
        return x*y // gcd(x,y)

    while True:
        arr.append(lcm(arr.pop(),arr.pop()))
        if len(arr) == 1:
            return arr[0]


def avoidObstacles(inputArray):
    inputArray = [5, 3, 6, 7, 9]

    inputSort = sorted(inputArray)

    DiffNum = []

    for i in range(len(inputSort)-1):
        if inputSort[i] + 1 != inputSort[i+1]:
            DiffNum.append(inputSort[i] + 1)
            
    DiffDiffNum = []
    for i in range(len(DiffNum)):
        if i == 0:
            DiffDiffNum.append(DiffNum[i])
        else:
            DiffDiffNum.append(DiffNum[i] - DiffNum[i-1])

    MinLen = solution(DiffDiffNum)

    return MinLen

제출 결과

2/12 tests passed.

Click the “Run Tests” button to see output, console logs, and detailed error messages for sample or custom test cases. This information is hidden when clicking the “Submit” button in order to prevent hard-coding solutions to the hidden test cases.

Sample tests: 2/6

Hidden tests: 0/6

Score: 33/300

각 값의 차이를 구하고, 그 차이 값의 최소공배수를 구해서 넘어가는 방식으로 코드 작성을 해봤는데, 아예 틀린 방법이었나보다.

작성 흐름

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
30
31
32
33
34
35
36
37
38
39
40
41
42
43

from math import gcd

# inputArray = [5, 3, 6, 7, 9]
inputArray = [1, 4, 10, 6, 2]

# 값을 정렬
inputSort = sorted(inputArray)

DiffNum = []

# 비어있는 부분 찾기
for i in range(len(inputSort)-1):
    if inputSort[i] + 1 != inputSort[i+1]:
        DiffNum.append(inputSort[i] + 1)
        

print(inputSort)
print(DiffNum)

# 비어있는 부분의 간격 계산
DiffDiffNum = []
for i in range(len(DiffNum)):
    if i == 0:
        DiffDiffNum.append(DiffNum[i])
    else:
        DiffDiffNum.append(DiffNum[i] - DiffNum[i-1])

print(DiffDiffNum)

# 간격들의 최소공배수 구하기
def solution(arr):
    def lcm(x,y):
        return x*y // gcd(x,y)

    while True:
        arr.append(lcm(arr.pop(),arr.pop()))
        if len(arr) == 1:
            return arr[0]

MinLen = solution(DiffDiffNum)

print(MinLen)
01_Study►Python

PythonCodeFight-Day14

Day_14

Intro

Q21. isIPv4Address

An IP address is a numerical label assigned to each device (e.g., computer, printer) participating in a computer network that uses the Internet Protocol for communication. There are two versions of the Internet protocol, and thus two versions of addresses. One of them is the IPv4 address.

제출 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def isIPv4Address(inputString):
    inputDivide = inputString.split('.')

    if len(inputDivide) != 4:
        return False
    else:
        for i in range(len(inputDivide)):
            if not inputDivide[i]:
                return False
            else:
                try:
                    if not ((int(inputDivide[i]) >= 0) and (int(inputDivide[i]) <= 255)):
                        return False
                except:            
                    return False
    return True

작성 흐름

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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
# Case
# inputString = "172.16.254.1"
# inputString = ".254.255.0"
# inputString = "1.23.256.255."
inputString = "0.254.255.0"
# inputString = "1.1.1.1a"

print(len(inputString))
print(inputString)
inputDivide = inputString.split('.') # '.'을 기준으로 문자열 분리
print(inputDivide)

# Test 1 
# inputString = "1.1.1.1a" 의 케이스에서 에러가 났음
# 1a를 int로 처리하는 경우 에러가 발생!
if len(inputDivide) != 4: # split을 하는 경우, '.' 가 3개가 아니면 ip가 아니기 때문에 갯수 제약 조건을 넣어줬음
    print("False, Not 4 values")
else: # 갯수가 맞는 경우
    for i in range(len(inputDivide)): # 각 항몫을 판단
        if not inputDivide[i]: # 값이 없는 경우
            print("False, Empty string")
        else:
            if not int(inputDivide[i]): 
                print("False, Not number")
            else:
                if not ((int(inputDivide[i]) >= 0) and (int(inputDivide[i]) <= 255)): # 값이 숫자 범위 내에 있지 않은 경우
                    print("False, Not in range")
                else:
                    print("True")

# Test 2
# 0인 경우 False 값을 리턴하는 에러가 생겼음
if len(inputDivide) != 4:
    print("False, Not 4 values")
else:
    for i in range(len(inputDivide)):
        try:
            if not int(inputDivide[i])): # 이렇게 하니까 0인 경우 False가 나옴
                print("False, Not number")
            else:
                if not ((int(inputDivide[i]) >= 0) and (int(inputDivide[i]) <= 255)):
                    print("False, Not in range")
                else:
                    print("True")
        except:
            print("False, Not number")                    

# Test 3
# 최종 제출 코드
if len(inputDivide) != 4:
    print("False, Not 4 values")
else:
    for i in range(len(inputDivide)):
        if not inputDivide[i]:
            print("False, Empty string")
        else:
            try:
                if not ((int(inputDivide[i]) >= 0) and (int(inputDivide[i]) <= 255)):
                    print("False, Not in range")
                else:
                    print("True")
            except:
                print("False, Not number")
01_Study►Python

PythonCodeFight-Day13

Day_13

Intro

Q21. isIPv4Address

An IP address is a numerical label assigned to each device (e.g., computer, printer) participating in a computer network that uses the Internet Protocol for communication. There are two versions of the Internet protocol, and thus two versions of addresses. One of them is the IPv4 address.

제출 코드

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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
def isIPv4Address(inputString):
    dotidxlist = []
    
    if len(inputString) >= 15 or len(inputString) < 8:
        return False
    else:
        for i in range(len(inputString)):
            if inputString[i] == ".":
                dotidxlist.append(i)

        if len(dotidxlist) != 3:
            return False
        else:
            for i in range(len(dotidxlist)):
                if i == 0:
                    try:
                        Temp = int(inputString[0:dotidxlist[i]])
                        if Temp < 0 or Temp > 255:
                            return False
                    except:
                        return False

                elif i == len(dotidxlist)-1:
                    try:
                        Temp1 = int(inputString[dotidxlist[i-1]+1:dotidxlist[i]])
                        if Temp1 < 0 or Temp1 > 255:
                            return False
                    except:
                        return False

                    try:
                        Temp2 = int(inputString[dotidxlist[i]+1:])
                        if Temp2 < 0 or Temp2 > 255:
                            return False
                    except:
                        return False
                else:
                    try:
                        Temp = int(inputString[dotidxlist[i-1]+1:dotidxlist[i]])
                        if Temp < 0 or Temp > 255:
                            return False
                    except:
                        return False
            return True

현재 결과
33/35 tests passed.
Sample tests: 18/18
Hidden tests: 15/17
Score: 276/300

  • 2개의 히든케이스를 만족하지 못했음 => 연산시간적인 문제 혹은 다른 문제 때문에 발생했다고 판단됨

해결 방안

  • 파이썬에서 제공하는 string 관련 기본적인 메소드 들을 이용해서 다시 한 번 작성하기
    • string의 경우 내장함수 split 을 이용하면 원하는 키워드를 기준으로 string 문자열을 분리해낼 수 있음

작성 흐름

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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
# Case
# inputString = "172.16.254.1"
inputString = ".254.255.0"

print(len(inputString))

dotidxlist = []
if len(inputString) >= 15:
    print("False")
else:
    for i in range(len(inputString)):
        if inputString[i] == ".":
            dotidxlist.append(i)
            print('idx = %d '%(i))
            print("True")
            print(dotidxlist)
    for i in range(len(dotidxlist)):
        if i == 0:
            try:
                Temp = int(inputString[0:dotidxlist[i]])
                print(Temp)
                if Temp < 0 or Temp > 255:
                    print("False")
            except:
                print("Empty False")
            # print(i)
        elif i == len(dotidxlist)-1:
            try:
                Temp1 = int(inputString[dotidxlist[i-1]+1:dotidxlist[i]])
                print(Temp1)
                if Temp1 < 0 or Temp1 > 255:
                    print("False")
            except:
                print("Empty False")
            
            try:
                Temp2 = int(inputString[dotidxlist[i]+1:])
                print(Temp2)
                if Temp2 < 0 or Temp2 > 255:
                    print("False")            
            except:
                print("Empty False")
            # print(i)
        else:
            try:
                Temp = int(inputString[dotidxlist[i-1]+1:dotidxlist[i]])
                print(Temp)
                if Temp < 0 or Temp > 255:
                    print("False")            
            except:
                print("Empty False")
            # print(i)
    print("True")
01_Study►Python

PythonCodeFight-Day12

Day_12

Intro

Q19. areEquallyStrong

Call two arms equally strong if the heaviest weights they each are able to lift are equal.

Call two people equally strong if their strongest arms are equally strong (the strongest arm can be both the right and the left), and so are their weakest arms.

Given your and your friend’s arms’ lifting capabilities find out if you two are equally strong.

제출 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
def areEquallyStrong(yourLeft, yourRight, friendsLeft, friendsRight):
    if yourLeft >= yourRight:
        yourStrong = yourLeft
        yourWeak = yourRight
    else:
        yourStrong = yourRight
        yourWeak = yourLeft

    if friendsLeft >= friendsRight:
        friendsStrong = friendsLeft
        friendsWeak = friendsRight
    else:
        friendsStrong = friendsRight
        friendsWeak = friendsLeft

    if (yourStrong == friendsStrong) and (yourWeak == friendsWeak):
        return True
    else:
        return False

작성 흐름

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
30
31
32
33
34
35
36
37
38
39
40
41
42
# Case: true
# yourLeft = 10
# yourRight = 15
# friendsLeft = 15
# friendsRight = 10

# Case: false
yourLeft = 15
yourRight = 10
friendsLeft = 15
friendsRight = 9

# 맨 처음엔 둘의 합을 가지고 계산하는 조건을 넣으려고 했으나, 생각해보니 강한 팔과 약한 팔의 값이 같으면 합은 당연히 같은 거라서 따로 조건을 넣어줄 필요가 업성서 뺐음
# yourWeight = yourLeft + yourRight
# friendsWeight = friendsLeft + friendsRight

# 나의 강한 팔 값 찾기
if yourLeft >= yourRight:
    yourStrong = yourLeft
    yourWeak = yourRight
else:
    yourStrong = yourRight
    yourWeak = yourLeft

# 친구의 강한 팔 값 찾기
if friendsLeft >= friendsRight:
    friendsStrong = friendsLeft
    friendsWeak = friendsRight
else:
    friendsStrong = friendsRight
    friendsWeak = friendsLeft

# 비교해서 값 리턴하기
if (yourStrong == friendsStrong) and (yourWeak == friendsWeak):
    print("true")
else:
    print("false")

# if yourWeight == friendsWeight:
#     print("True")
# else:
#     print("False")

Q20. arrayMaximalAdjacentDifference

Given an array of integers, find the maximal absolute difference between any two of its adjacent elements.

제출 코드

1
2
3
4
5
6
def arrayMaximalAdjacentDifference(inputArray):
    difflist = []
    for i in range(len(inputArray)-1):
        difflist.append(abs(inputArray[i]-inputArray[i+1]))
    
    return max(difflist)

작성 흐름

1
2
3
4
5
6
7
8
9
10
11
12
# Case
# inputArray = [2, 4, 1, 0]
inputArray = [-1, 4, 10, 3, -2]

# 차이 값을 넣을 리스트 선언
difflist = []

# 전체 배열 돌면서 차이의 절대값 넣기
for i in range(len(inputArray)-1):
    difflist.append(abs(inputArray[i]-inputArray[i+1]))

print(max(difflist))
01_Study►Python

PythonCodeFight-Day11

Day_11

Intro

Q17. arrayChange

You are given an array of integers. On each move you are allowed to increase exactly one of its element by one. Find the minimal number of moves required to obtain a strictly increasing sequence from the input.

제출 코드

1
2
3
4
5
6
7
8
9
def arrayChange(inputArray):
    AddNum = 0
    
    for i in range(len(inputArray) -1):
        if inputArray[i] >= inputArray[i+1]:
            AddNum += inputArray[i] + 1 - inputArray[i+1]
            inputArray[i+1] = inputArray[i] + 1
            
    return AddNum

작성 흐름

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
30
31
32
33
34
35
36
37
# 테스트 케이스들
inputArray = [1, 1, 1]
inputArray = [3122, -645, 2616, 13213, -8069]
inputArray = [2, 3, 3, 5, 5, 5, 4, 12, 12, 10, 15]
inputArray = [22121, 42080, -51776, -28528, 39895, -50842, 25463, 46187, -29518,
42293, -25615, -47412, 24945, -2630, -12717, -23773, -47824, -7768, -23620,
-30270, -51644, 42829, 27609, -40734, 2142, 20285, 29665, -36557, -24074,
-11996, 30511, 17104, 4360, -41163, 6814, 959, 26613, -15121, -17355,
28424, -11305, 33175, -8585, 23649, -18428, 16770, 14095, 38766, -22425,
-45139, -5836, -28668, -15123, -35450, 41353, 11103, -29233, -51990, -14958,
45944, 20841, -34149, 34720, -51760, 23519, -46257, 40985, -32615, -43378,
14243, -24731, 1311, -4236, -24885, 41713, -45195, -14683, 47765, 26904,
-51741, 38051, 13429, 38189, -45812, -52474, 14936, 6582, -26313, 4692,
12313, -37502, -40673, 5799, 23264, 33617, -50938, 26268, -25548, -22353,
-15175, -21568, 18656, 19208, 20674, 41228, -42538, -45085, -32356, -39901,
-39585, -50690, 2859, -4079, 29823, 28849, -2142, -16613, 23378, 36363,
31780, -40379, 7489, -13324, -22377, 35661, -27141, -42727, 10122, -40385,
-19765, 33913, -10504, -4715, -18190, 41430, -19134, 32646, 25839, 783, 32941, -25142]

# 리턴해줄 값을 0으로 초기화
AddNum = 0

# 입력받은 행렬의 전체 길이 - 1 만큼 반복한다 (다음 값과 비교해야해서 -1 처리 해주는 것)
for i in range(len(inputArray)-1):
    # 만약 현재 값이 다음 값보다 큰 경우, 
    if inputArray[i] >= inputArray[i+1]:
        # 다음 값을 현재 값보다 1 크게 하기 위한 값을 저장한다.
        AddNum += inputArray[i] + 1 - inputArray[i+1]
        # 확인용 print 코드
        print("Index: {}, Diff: {}, Total: {}".format(i, inputArray[i] + 1 - inputArray[i+1], AddNum))
        # 다음 값을 현재 값보다 1 크게 해준다.
        inputArray[i+1] = inputArray[i] + 1

# 바뀐 배열의 결과 확인
print(inputArray)
# 출력해줄 값 확인
print(AddNum)

Q18. palindromeRearranging

Given a string, find out if its characters can be rearranged to form a palindrome.

제출 코드

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
30
31
32
33
34
35
36
37
38
39
40
def palindromeRearranging(inputString):
    setString = list(set(inputString))

    dict_alphabet = dict()
    
    # 각 문자별로 갯수 세기
    for i_set in range(len(setString)):
        temp_alphabet = setString[i_set]
        dict_alphabet[temp_alphabet] = 0
        
        for i_input in range(len(inputString)):
            
            if inputString[i_input] == temp_alphabet:
                dict_alphabet[temp_alphabet] += 1

    # 짝수인 경우
    count_odd = 0
    if (len(inputString) % 2) == 0 : 
        
        for i_set in range(len(setString)):
            temp_alphabet = setString[i_set]
            
            if (dict_alphabet[temp_alphabet] % 2) != 0:
                count_odd += 1

                if count_odd >= 1:
                    return False
        return True
    # 홀수인 경우
    else:
        
        for i_set in range(len(setString)):
            temp_alphabet = setString[i_set]
            
            if (dict_alphabet[temp_alphabet] % 2) != 0:
                count_odd += 1

                if count_odd >= 2:
                    return False
        return True

작성 흐름

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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
inputString = "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaabc"
print(len(inputString))
# 문자의 길이 확인하기 => 짝수인지 홀수인지
# 짝수인 경우 => 모든 문자가 짝수개여야 한다.
# 홀수인 경우 => 한 문자까지는 홀수개가 가능하다.
# 문자의 종류 확인하기 
setString = list(set(inputString))
print(setString)

# 알파벳 별로 갯수를 세기 위해서 dictionary 선언
dict_alphabet = dict()

# 각 문자별로 갯수 세기
for i_set in range(len(setString)):
    temp_alphabet = setString[i_set]
    dict_alphabet[temp_alphabet] = 0

    for i_input in range(len(inputString)):

        if inputString[i_input] == temp_alphabet:
            dict_alphabet[temp_alphabet] += 1
    
print(dict_alphabet)

# 홀수 개수인 알파벳 개수 체크
count_odd = 0

# 짝수인 경우
if (len(inputString) % 2) == 0 : 
    for i_set in range(len(setString)):
        temp_alphabet = setString[i_set]

        if (dict_alphabet[temp_alphabet] % 2) != 0:
            count_odd += 1

            if count_odd >= 1:
                print("false")
                break
    print("true")

# 홀수인 경우
else:
    for i_set in range(len(setString)):
        temp_alphabet = setString[i_set]

        if (dict_alphabet[temp_alphabet] % 2) != 0:
            count_odd += 1

            if count_odd >= 2:
                print("false")
                break
    print("true")
01_Study►C

[16] 2차원 배열 정렬 (Sort 2D Array)

2차원 배열 정렬 (sortrows)

Matlab에서 제공하는 sortrows 함수를 C언어로 구현한 것

참고자료: 코딩도장 - 버블정렬

2차원 배열 정렬 기능 설명

2차원 배열을 받아서, 각 행의 맨 앞의 값의 크기를 기준으로 오름차순으로 정렬한다.

예를 들어보면

1
2
3
4
5
6
int a[4][3] = {
    {5,3,4,2},
    {4,5,6,3},
    {7,8,9,3},
    {2,4,4,5}
};

위와 같은 배열이 있을 때, 각 행의 맨 앞의 값과 행의 인덱스는 아래와 같다.

1
2
rowVal1 = {{5},{4},{7},{2}};
rowIdx1 = {{0},{1},{2},{3}};

위의 정보를 행의 값에 따라 오름차순으로 정렬하면 아래와 같다.

1
2
rowSortVal1 = {{2},{4},{5},{7}};
rowSortIdx1 = {{3},{1},{0},{2}};

정렬된 행에 맞게 행렬 자체를 정렬하면 아래와 같다.

1
2
3
4
5
6
int aSort[4][3] = {
    {2,4,4,5},
    {4,5,6,3},
    {5,3,4,2},
    {7,8,9,3}
};

따라서, 각 행의 첫 값을 비교하여 바꿀 인덱스를 확인한 다음, 배열에서 해당 행들의 인덱스를 바꿔주면 된다.

C언어로 작성한 코드

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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

// 코딩 도장에서 제공한 기본적인 bubble sort를 내가 필요한 방식으로 수정
// 입력으로 배열의 각 행 첫 열의 값과 인덱스를 담은 배열을 받아오고, 배열의 크기를 받아온다.
// 배열을 입력으로 받아오는 것이기 때문에, 따로 리턴 값을 지정해줄 필요는 없다.
void bubble_sort_modi(int arrVal[], int arrIdx[], int arrSize){ 
    // 임시 저장 변수 선언
    int temp, tempIdx;
    
    // 배열의 사이즈 만큼 반복
    for(int i = 0; i < arrSize; i++){ 
        // 배열의 사이즈 - 1 만큼 반복 (다음 값을 봐야해서)
        for(int j = 0; j < arrSize-1; j++){
            // 현재 값이 다음 값보다 크면
            if(arrVal[j] > arrVal[j+1]){
                // 값을 바꿔라
                temp = arrVal[j];
                arrVal[j] = arrVal[j+1];
                arrVal[j+1] = temp;
                
                // 그리고 해당하는 인덱스의 위치도 바꿔라
                tempIdx = arrIdx[j];
                arrIdx[j] = arrIdx[j+1];
                arrIdx[j+1] = tempIdx;
            }
        }
    }
}

// 입력으로 배열을 받아왔을 때 처리하는 방법과 배열까지 동적으로 선언해서 제공해주는 두 가지의 방법을 작성했다.
// 1. 입력으로 정렬할 배열의 주소를 받아올 때
// 2차원 배열의 경우, 고정된 값으로 선언했을 때에는 첫번째 입력에서 볼 수 있는 것처럼
// (자료형) arr[][열 사이즈]와 같이 선언해줘야한다.
// 입력으로 넣어주는 2차원 배열이 이중 포인터를 이용한 동적 할당으로 선언된 경우 두번째 입력에서 볼 수 있는 것처럼
// (자료형) **sortedArr 로 선언해주면 된다.
// 그리고 행과 열의 사이즈를 입력으로 넣어주면 된다.
void sort2DArr(int arr[][3], int **sortedArr, int row){
    // 0으로 초기화된 값, 인덱스를 위한 배열을 선언
    int *seq = calloc(row, sizeof(int));
    int *seq_idx = calloc(row, sizeof(int));
    
    // 받아온 배열에서 첫 행의 값 꺼내서 넣고, 행의 인덱스 채워넣기
    for (int i = 0; i < row; i++){
        seq[i] = arr[i][0];
        seq_idx[i] = i;
    }

    // 인덱스 정렬하기
    bubble_sort_modi(seq,seq_idx,row);

    // 정렬된 인덱스에 따라서 정렬한 값을 넣을 배열에 값을 복사해서 넣기
    for (int i = 0; i < row; i++){
        memcpy(sortedArr[i],arr[seq_idx[i]],sizeof(int)*3);
    }
    
    // 동적 할당한 배열 메모리 해제
    free(seq);
    free(seq_idx);
}

// 2. 정렬할 배열을 만들어서 리턴해줄 때
// 동적 할당으로 선언된 배열을 이중포인터로 리턴해주고, 행렬의 사이즈를 잘 알려주면 리턴으로 받아서 이용할 수 있다.
int** sort2DArr2(int arr[][3], int row){
    // 0으로 초기화된 값, 인덱스를 위한 배열을 선언
    int *seq = calloc(row, sizeof(int));
    int *seq_idx = calloc(row, sizeof(int));
    
    // 받아온 배열에서 첫 행의 값 꺼내서 넣고, 행의 인덱스 채워넣기
    int **sortedArr = calloc(row, sizeof(int *));
    for (int i = 0; i < row; i++){
        sortedArr[i] = calloc(3, sizeof(int));
    }

    // 받아온 배열에서 첫 행의 값 꺼내서 넣고, 행의 인덱스 채워넣기
    for (int i = 0; i < row; i++){
        seq[i] = arr[i][0];
        seq_idx[i] = i;
    }
	
    // 인덱스 정렬하기
    bubble_sort_modi(seq,seq_idx,row);

    // 정렬된 인덱스에 따라서 정렬한 값을 넣을 배열에 값을 복사해서 넣기
    for (int i = 0; i < row; i++){
        memcpy(sortedArr[i],arr[seq_idx[i]],sizeof(int)*3);
    }
    
    // 동적 할당한 배열 메모리 해제
    free(seq);
    free(seq_idx);

    return sortedArr;
}

테스트코드

테스트 해볼 방법만 살려두고 주석처리하고 실행해야함

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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

void bubble_sort_modi(int arrVal[], int arrIdx[], int arrSize);
void sort2DArr(int arr[][3], int **sortedArr, int row);
int** sort2DArr2(int arr[][3], int row);

int main(){

    int a[4][3] = {
        {3,2,2},
        {6,7,3},
        {4,5,6},
        {7,9,2}
    };

    // 1번 방법으로 이용할 경우
    int **sortedArr = calloc(4, sizeof(int *));
    for (int i = 0; i < 4; i++){
        sortedArr[i] = calloc(3, sizeof(int));
    }

    int seq[4];
    int seq_idx[4];
    for (int i = 0; i < 4; i++){
        seq[i] = a[i][0];
        seq_idx[i] = i;
    }

    printf("Base a\n");
    for(int i = 0; i < 4; i++){
        for(int j = 0; j < 3; j++){
            printf("%d ",a[i][j]);
        }
        printf("\n");
    }
    printf("\n");

    sort2DArr(a, sortedArr, 4);

    printf("Sorted a\n");
    for(int i = 0; i < 4; i++){
        for(int j = 0; j < 3; j++){
            printf("%d ",sortedArr[i][j]);
        }
        printf("\n");
    }
    printf("\n");
    
    // 2번 방법으로 이용할 경우
    int **sortedArr;
    
    printf("Base a\n");
    for(int i = 0; i < 4; i++){
        for(int j = 0; j < 3; j++){
            printf("%d ",a[i][j]);
        }
        printf("\n");
    }
    printf("\n");    
    
    sortedArr = sort2DArr2(a, 4);

    printf("Sorted a\n");
    for(int i = 0; i < 4; i++){
        for(int j = 0; j < 3; j++){
            printf("%d ",sortedArr[i][j]);
        }
        printf("\n");
    }
    printf("\n");
    

    // Free
    for(int i = 0; i < 4; i++){
        free(sortedArr[i]);
    }
    free(sortedArr);

    return 0;
}