코딩도장 문제풀이

사용언어: 파이썬 2.7

1. 난이도, Lv 1

1) 피보나치 수열

문제: http://codingdojang.com/scode/461

input = 10
cnt = 0
a = 0
b = 1
 
for index in range(0, input):
    if index %2 == 0:
        print a
        print b
    cnt = a+b
    a = b
    b = cnt
    pass

짬내서 코딩도장 문제풀이 시작하려고 합니다.

레벨1 문제이긴 한데

파이썬 문법자체를 자꾸 까먹으려고 해서 손풀기겸겸.

부끄럽게도 심각할정도로 돌머리라 문제자체를 이해못했습니다.

문장자체를 구조화 못하니 코드로 구현했겠나요?

그런 의미에서 피보나치 문제는 돌머리 탈출기념으로도 나름 의미는 있습니다.

---

2) Multiples of 3 and 5 

문제: http://codingdojang.com/scode/350

max = 1000
result = 0
 
for index in range(1, max):
    if index % 3 == 0:
        result += index
        print index
    elif index % 5 == 0:
        result += index
        print index
    pass
 
 
print result

1000에서는 233168

다른분들 문제풀이도 보니깐 if-else와 %연산자로 정말 쉽게 해결되는 문제입니다.

이중 bjKang이라는 분하고 코드가 유사하게 나오네요.

레벨 1은 2~3개까지만 더 해보고 레벨2로 옮겨야할지 싶습니다.

---

3) 구글 입사문제

문제: http://codingdojang.com/scode/393

max = 10000
cnt = 0
 
for index in range(1, max):
    tmp = index
    while tmp > 0:
        if tmp % 10 == 8:
            cnt += 1
        tmp /= 10
    pass    #END. while tmp > 0:
pass    #END. for index in range(1, max):
 
print cnt

9번째줄에서 들여쓰기 잘못해서 무한루프에 빠졌었습니다.

문제풀이중 jake kim님의 방식이 리스트처럼 특정순서를 뺴고 나머지 멤버로만 간편하게 추리는 방식이 정말 창의적입니다.

파이썬의 경우 문자열에서 count라는 함수가 있으나,

가급적 특정 언어에만 있는 API를 안 쓰고 문장을 구조화 하는게 좋을것 같아 이 방법을 선택했습니다.

---

4) 삽입정렬

문제: http://codingdojang.com/scode/443

g_list = [5, 2, 4, 6, 1, 3]
listLeng = len(g_list)
 
for index in range(1, listLeng):
    tmp = g_list[index]
    leftIdx = index - 1
 
    while ( leftIdx >= 0 and g_list[leftIdx] > tmp):
        g_list[leftIdx + 1] = g_list[leftIdx]
        g_list[leftIdx] = tmp
        print "loop. index=" + str(index) + ", leftIdx=" + str(leftIdx) + ", "  + str(g_list)
        leftIdx -= 1
        # END. while
    pass    # END. for index in range(1, listLeng):
 
print str(g_list)

이미지출처: http://effectiveprogramming.tistory.com/19

레벨1 문제는 이걸로 끝.

다음부터는 레벨2 문제.

2. 난이도, Lv 2

1) 아마존 면접문제

문제: http://codingdojang.com/scode/416

g_list = [10, 20, 30, 40, 50, 60, 70, 80, 90, 11, 21, 31, 41, 51, 61, 71, 81, 91]
limit = len(g_list) / 2
aList = []
bList = []
print "START. " + str(g_list)
 
for index in range(0, limit):
    aList.append( g_list[index] )
    bList.append( g_list[index + limit] )
    """
    해당 반복문은 아래의 2줄로도 가능하긴 함.
    aList = g_list[0:limit]
    bList = g_list[limit:len(g_list)]
    """
    pass
print "aList =" + str(aList)
print "bList =" + str(bList)
 
g_list = []
for index in range(0, limit):
    g_list.append( aList[index] )
    g_list.append( bList[index] )
    pass
print "FINAL. " + str(g_list)

---

2) 문자열 압축하기

문제: http://codingdojang.com/scode/465

msg = "aaabbcccccca"
resultMsg = ""
msgLeng = len(msg) - 1
cnt = 1
index = 0
 
for index in range(0, msgLeng):
    if ( msg[index] == msg[index + 1] ):
        cnt += 1
        pass
    else:
        resultMsg += ( msg[index] + str(cnt) )
        cnt = 1
        if( index+1 == msgLeng ):
            resultMsg += ( msg[index+1] + str(1) )
            pass
        pass
    pass
 
print resultMsg

해당 문제의 경우, 압축에 관한 간단한 알고리즘중 하나였던걸로 기억함.

시작점이 0인지 1인지에 따라 문자열 마지막값에 대한 추가작업 여부가 갈림.

index는 가급적 0부터 쓰는게 무난하다고 봐서 이쪽으로 선택.

---

3) 구글 전화면접

문제: http://codingdojang.com/scode/414

g_list = [-1, 1, 3, -2, 2]
leftList = []
rightList = []
 
for index in range ( 0, len(g_list) ):
    tmp = g_list[index]
 
    if( tmp < 0 ):
        leftList.append(tmp)
    else:
        rightList.append(tmp)
    pass
 
print leftList + rightList

이미 풀었던 문제같은데도 다른 문제길래 확인결과 코딩도장, 아마존 면접문제를 역순으로 처리하는 정도네요.

---

4) 10진수 변환

문제: http://codingdojang.com/scode/458

def binaryNum(res, divN, result = ""):
    if( divN < 2 and 16 < divN):
        return
 
    if(res < 1 ):
        print result + "[" + str(divN) + "]"
        return
    else:
        tmp = res % divN
        if tmp > 10:
            result = chr( 65 + (tmp-10) ) + result
            pass
        else:
            result = str(tmp) + result
            pass
        tmpInt = res/ divN
        binaryNum( tmpInt, divN, result )
    pass
 
binaryNum(233, 16, "")  #입력

재귀함수로 처리하다가

파이썬에서도 함수인자에 기본값 지정이 가능한거 처음 알았네요.

다만 함수인자가 3개 이상일땐 가운데 인자가 맨 오른쪽로 처리되는 버그같은게 있었는데

액션스크립트하고는 문법이 미묘하게 다른게 아닐까도 싶네요.

---

5) 비슷한 단어 찾아내기

문제: http://codingdojang.com/scode/445

def oneEditApart(arg0Str, arg1Str):
    cntF = 0
    block = 0
    tmp = len(arg0Str) - len(arg1Str)
 
    if( tmp > 0 ):
        for index in range (0, len(arg0Str)-1):
            if( arg0Str[index:index+1] == arg1Str[0:1] ):
                block = index
                break
            pass
        arg1Str = ('_' * block) + arg1Str
        pass    #END. if( tmp > 0 ):
    elif( tmp < 0 ):
        for index in range (0, len(arg1Str)-1):
            if( arg1Str[index:index+1] == arg0Str[0:1] ):
                block = index
                break
            pass
        arg0Str = ('_' * block) + arg0Str
        pass    #END. elif( tmp < 0 ):
 
    for index in range (0, len(arg0Str) ):
        if ( arg0Str[index]==arg1Str[index] ):
            cntF += 1/( float(len(arg0Str)) )
            pass
        pass
 
    if( cntF > 0.5 ):
        print "TRUE\t" + arg0Str + "/" + arg1Str
    else:
        print "FALSE\t" + arg0Str + "/" + arg1Str
    pass    #END. def oneEditApart(arg0Str, arg1Str):
 
oneEditApart("cat", "dog")
oneEditApart("cat", "cats")
oneEditApart("cat", "cut")
oneEditApart("cat", "cast")
oneEditApart("cat", "at")
oneEditApart("cat", "acts")

문자열중 짧은쪽 0~1번을 긴쪽과 비교해 0~1번와 처음 일치할떄의 길이만큼 짧은쪽 앞에 메꾸고 난뒤,

인덱스기준으로 1:1 비교해서 그만큼 유사한 비율값(cntF) 누적.

유사한 정도가 별도로 명시되지 않아서 0.5가 넘으면 비슷한 단어로 처리.

다음은 레벨3문제.

3. 난이도, Lv 3

1) Spiral Array

문제: http://codingdojang.com/scode/266

def spiralArray(rowLeng, colLeng):
    spiralMetrix = [[0 for col in range(colLeng)] for row in range(rowLeng)]
 
    direction = 1
    mx = 0
    index = 0
    while (index < colLeng * rowLeng):
        idx = 0
        if(direction == 1):   #RIGHT
            for idx in range (mx, colLeng - mx):
                spiralMetrix[mx][idx] = index
                index += 1
                pass
            direction = direction << 1
            pass
        elif(direction == 2):   #DOWN
            for idx in range (mx+1, rowLeng - mx):
                spiralMetrix[idx][colLeng - (mx+1)] = index
                index += 1
                pass
            direction = direction << 1
            pass
        elif(direction == 4):   #LEFT
            for idx in range (colLeng - (mx+2) , mx-1, -1):
                spiralMetrix[rowLeng - (mx+1)][idx] = index
                index += 1
                pass
            direction = direction << 1
            pass
        elif(direction == 8):   #UP
            for idx in range (rowLeng - (mx+2), mx, -1):
                spiralMetrix[idx][mx] = index
                index += 1
                pass
            mx += 1
            direction = direction >> 3
            pass
 
        #   REULT
        print "\n\tloop. " + str(index) + ", " + str(direction)
        for i in spiralMetrix:
            print i
            pass
    pass
 
spiralArray(6, 6);

    loop. 6, 2

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

[0, 0, 0, 0, 0, 0]

[0, 0, 0, 0, 0, 0]

[0, 0, 0, 0, 0, 0]

[0, 0, 0, 0, 0, 0]

[0, 0, 0, 0, 0, 0]

    loop. 11, 4

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

[0, 0, 0, 0, 0, 6]

[0, 0, 0, 0, 0, 7]

[0, 0, 0, 0, 0, 8]

[0, 0, 0, 0, 0, 9]

[0, 0, 0, 0, 0, 10]

    loop. 16, 8

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

[0, 0, 0, 0, 0, 6]

[0, 0, 0, 0, 0, 7]

[0, 0, 0, 0, 0, 8]

[0, 0, 0, 0, 0, 9]

[15, 14, 13, 12, 11, 10]

    loop. 20, 1

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

[19, 0, 0, 0, 0, 6]

[18, 0, 0, 0, 0, 7]

[17, 0, 0, 0, 0, 8]

[16, 0, 0, 0, 0, 9]

[15, 14, 13, 12, 11, 10]

    loop. 24, 2

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

[19, 20, 21, 22, 23, 6]

[18, 0, 0, 0, 0, 7]

[17, 0, 0, 0, 0, 8]

[16, 0, 0, 0, 0, 9]

[15, 14, 13, 12, 11, 10]

    loop. 27, 4

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

[19, 20, 21, 22, 23, 6]

[18, 0, 0, 0, 24, 7]

[17, 0, 0, 0, 25, 8]

[16, 0, 0, 0, 26, 9]

[15, 14, 13, 12, 11, 10]

    loop. 30, 8

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

[19, 20, 21, 22, 23, 6]

[18, 0, 0, 0, 24, 7]

[17, 0, 0, 0, 25, 8]

[16, 29, 28, 27, 26, 9]

[15, 14, 13, 12, 11, 10]

    loop. 32, 1

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

[19, 20, 21, 22, 23, 6]

[18, 31, 0, 0, 24, 7]

[17, 30, 0, 0, 25, 8]

[16, 29, 28, 27, 26, 9]

[15, 14, 13, 12, 11, 10]

    loop. 34, 2

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

[19, 20, 21, 22, 23, 6]

[18, 31, 32, 33, 24, 7]

[17, 30, 0, 0, 25, 8]

[16, 29, 28, 27, 26, 9]

[15, 14, 13, 12, 11, 10]

    loop. 35, 4

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

[19, 20, 21, 22, 23, 6]

[18, 31, 32, 33, 24, 7]

[17, 30, 0, 34, 25, 8]

[16, 29, 28, 27, 26, 9]

[15, 14, 13, 12, 11, 10]

    loop. 36, 8

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

[19, 20, 21, 22, 23, 6]

[18, 31, 32, 33, 24, 7]

[17, 30, 35, 34, 25, 8]

[16, 29, 28, 27, 26, 9]

[15, 14, 13, 12, 11, 10]

행렬을 선언후,

시작점부터 특정구간마다 방향을 틀면서 값을 채우게 처리했습니다.

값을 입력하는 패턴은 분기별로 '출발점~방향전화하는 지점'

방향의 경우 index구간마다 방향전환을 하기에는 코드가 지저분해져서 위와같이 했습니다.

Rosetta Code에서 Simple solution을 보면,

좌표에 변화를 줄 mx를 2개의 배열로 하는 방법도 있군요.

---

2) 그 시간 사무실에 몇 명이 있었나?(아마존 면접)

문제: http://codingdojang.com/scode/418

log = """09:12:23 11:14:35
09:04:00 12:00:00
11:06:00 12:00:45
10:34:01 13:23:40
09:04:00 11:00:00
10:34:31 11:20:10"""
 
def howMany(logStr, time):
    personCheck = log.splitlines()
    personNum = len(personCheck)
    cnt = 0
    hour = int(time[0:2])
    minute = int(time[3:5])
    second = int(time[6:8])
 
    for index in range(0, personNum):
        tmp = personCheck[index].split(' ')
        inTime = tmp[0]
        outTime = tmp[1]
 
        if( hour == int(inTime[0:2]) ):
            if( minute > int(inTime[3:5]) ):
                cnt += 1
                pass
            elif( minute == int(inTime[3:5]) and second >= int(inTime[6:8]) ):
                cnt += 1
                pass
            pass
        elif( int(inTime[0:2]) < hour < int(outTime[0:2]) ):
            cnt += 1
            pass
        elif( hour == int(outTime[0:2]) ):
            if( minute < int(outTime[3:5]) ):
                cnt += 1
                pass
            elif( minute == int(outTime[3:5]) and second <= int(outTime[6:8]) ):
                cnt += 1
                pass
            pass
        pass    #END. for index in range(0, personNum):
 
    print time + ", " + str(cnt) + "person(s)."
    pass    #END. def howMany(logStr, time):
 
howMany(log, "09:30:00")
howMany(log, "11:05:20")

출퇴근 로그파일을 육안으로 볼때,
입력된 값의 시단위가 출퇴근 시간이내 여부 확인.
시간은 같다면 분/초단위로 세이프가 되는지로 확인하는걸 코드로 구현.

---

3) Ugly Numbers

문제: 

처음에 시도한 아래의 코드는 사실 계산상 문제는 없지만 저조한 퍼포먼스.

import time;
 
def uglyNumber(nthNum):
    _t = time.time();
    resultFt = 0.0;
    listCnt = 1;
    idxFt = 1.0;
 
    while (listCnt < nthNum):
        if( degradedNum(idxFt) ):
            print "[" + str(listCnt+1) + "] " + str(idxFt);
            listCnt += 1;
            resultFt = idxFt;
            pass
        idxFt += 1.0;
        pass
 
    print str(resultFt) + ',   %.02f seconds' % (time.time() - _t);
    pass    # END. def uglyNumber(nthNum):
 
def degradedNum(input):
    tmp = input;
    if(tmp%2 == 0):
        while (tmp%2 == 0):
            tmp /= 2;
            if (tmp == 1):
                return True;
            pass
        pass
    if(tmp%3 == 0):
        while (tmp%3 == 0):
            tmp /= 3;
            if (tmp == 1):
                return True;
            pass
        pass
    if(tmp%5 == 0):
        while (tmp%5 == 0):
            tmp /= 5;
            if (tmp == 1):
                return True;
            pass
        pass
    return False;
    pass    # END. def degradedNum(isEven, input):
 
uglyNumber(1550)

... ... ...

[1499] 854296875.0
[1500] 859963392.0
[1501] 860934420.0

... ... ...

[1549] 1088391168.0

[1550] 1093500000.0

1093500000.0,   2204.15 seconds

다른 풀이중, '길가의풀'이라는 분이 업로드한 코드에는 min()이라는 함수가 있는데,

리스트 꼬리값과 min함수를 이용해서 루프를 돌릴때마다 규칙에 맞는값 append

---

4) 숫자에 콤마 삽입

문제: http://codingdojang.com/scode/398

def setComma(arg):
    mark = "";
    if (arg< 0):
        mark = "-";
        arg *= -1;
        pass
 
    #    소수점 이하 분리.
    pointFt = float(arg - int(arg));
    tmpPtStr = str(pointFt);
    arg -= pointFt;
    arg = int(arg);
    
    tmpStr = str(arg);
    msgStr = "";
    idx = 0;    #콤마 표기용 idx값
    for index in range (len(tmpStr)-1, -1, -1):
        if(idx % 3 == 0 and idx > 1):
            msgStr = "," + msgStr;
            pass
        idx += 1;
        msgStr = tmpStr[index] + msgStr;
        pass
 
    print mark + msgStr + tmpPtStr[1:len(tmpPtStr)];
    pass
 
setComma(1000);
setComma(20000000);
setComma(-3245.24);

1,000.0
20,000,000.0
-3,245.24

for문내에서 숫자문자열을 k->0순으로 += 시킬때,
특정구간에 콤마를 먼저붙이게 지정.
그밖에 소수점 이하값과 음수/양수 표기를 다른 변수에 뗴어놓고 출력시 모아줌.

---

5) 앞뒤가 같은 수

문제: http://codingdojang.com/scode/401

1안. 재귀함수 사용시

import time;
 
def getPairNum(arg):
    cntInt = 0;
    result = -1;
    _t = time.time();
 
    if(arg == 0):
        print "pairNum[" + str(arg) + "]=1";
        return;
 
    while (cntInt < arg):
        result += 1;
        tmpStr = str(result);
        strLeng = len(tmpStr);
        if( result < 10 ):
            cntInt += 1;
            pass
        elif( result < 100 ):
            if( tmpStr[0] == tmpStr[1] ):
                cntInt += 1;
            pass
        elif( result < 1000 ):
            if(tmpStr[0] == tmpStr[2]):
                cntInt += 1;
            pass
        elif(tmpStr[0] == tmpStr[strLeng-1] and tmpStr[1] == tmpStr[strLeng-2]):
            if( result < 10000 ):
                cntInt += 1;
            elif( checkPair(tmpStr, 0, strLeng) ):
                cntInt += 1;
        pass;    # while (cntInt < arg):
 
    print "pairNum[" + str(arg) + "]=" + str(result) + ',   %.04f seconds' % (time.time() - _t);
    pass;    # def getPair(arg):
 
def checkPair(msg, token, gap):
    #print str(gap) + ", msg=" + str(msg);
    if(len(msg)%2==0 and gap<1):
        return True;
        pass
    elif(len(msg)%2!=0 and gap<2):
        return True;
        pass
    elif(msg[token] == msg[gap-1]):
        token += 1;
        gap -= 2;
        checkPair(msg, token, gap)
        pass
    else:
        return False;
    pass    # def checkPair(msg, msgLeng):
 
getPairNum(1);
getPairNum(4);
getPairNum(20);
getPairNum(21);
getPairNum(30);
getPairNum(100);
getPairNum(1000);
getPairNum(1001);
getPairNum(30000);
getPairNum(1000000);

pairNum[1]=0,   0.0000 seconds
pairNum[4]=3,   0.0000 seconds
pairNum[20]=101,   0.0000 seconds
pairNum[21]=111,   0.0000 seconds
pairNum[30]=202,   0.0000 seconds
pairNum[100]=909,   0.0010 seconds
.... .... ...

재귀함수를 쓰긴 했지만 너무 느려서 4자리 이상 숫자에 대한 판별을 수정토록 함.

2안.

import time;
 
def getPairNum(arg):
    cntInt = 0;
    result = -1;
    _t = time.time();
 
    if(arg == 0):
        print "pairNum[" + str(arg) + "]=1";
        return;
 
    while (cntInt < arg):
        result += 1;
        tmpStr = str(result);
        strLeng = len(tmpStr);
        if( result < 10 ):
            cntInt += 1;
            pass
        elif( result < 100 ):
            if( tmpStr[0] == tmpStr[1] ):
                cntInt += 1;
            pass
        elif( result < 1000 ):
            if(tmpStr[0] == tmpStr[2]):
                cntInt += 1;
            pass
        elif(tmpStr[0] == tmpStr[strLeng-1] and tmpStr[1] == tmpStr[strLeng-2]):
            if( result < 10000 ):
                cntInt += 1;
            elif( checkPair(tmpStr, strLeng) ):
                cntInt += 1;
        pass;    # while (cntInt < arg):
 
    print "pairNum[" + str(arg) + "]=" + str(result) + ',   %.04f seconds' % (time.time() - _t);
    pass;    # def getPair(arg):
 
def checkPair(msg, msgLeng):
    rangeEnd = int(msgLeng/2);
    head = -1;
 
    for head in range(0, rangeEnd):
        rear = msgLeng - 2*head - 1;
        if(rear < 3):
            return True;
            pass;
        elif(msg[head] != msg[rear]):
            return False;
        pass;
 
    pass    # def checkPair(msg, msgLeng):
 
getPairNum(1);
getPairNum(4);
getPairNum(20);
getPairNum(21);
getPairNum(30);
getPairNum(100);
getPairNum(1000);
getPairNum(1001);
getPairNum(30000);
getPairNum(1000000);

pairNum[1]=0,   0.0000 seconds
pairNum[4]=3,   0.0000 seconds
pairNum[20]=101,   0.0000 seconds
pairNum[21]=111,   0.0000 seconds
pairNum[30]=202,   0.0000 seconds
pairNum[100]=909,   0.0000 seconds
pairNum[1000]=90009,   0.0650 seconds
pairNum[1001]=90109,   0.0670 seconds
pairNum[30000]=200000002,   151.8450 seconds
... ... ...

---

6) 넥슨 입사문제, 셀프 넘버

문제: http://codingdojang.com/scode/365

def selfNumAcc(start, end):
    resultInt = 0;
    generateList = [];
    tmpToken = [];
 
    for index in range(start, end):
        generateList.append( getGenerator(index) );
        pass;
    #print str(generateList);
 
    for index in range(start, end):
        if( index not in generateList):
            resultInt += index;# print str(index) + ", " + str(resultInt);
            pass
        pass;
    print str(start) + "~" + str(end) + " self num sum = " + str(resultInt);
 
    pass;    # def selfNumAcc(start, end):
 
def getGenerator(arg):
    tmpSum = arg;
    while(arg > 0):
        tmpSum += (arg%10);
        arg //= 10; # quotient
        pass;
    return tmpSum;
    pass;
 
selfNumAcc(1, 5000);

답: 1227365

d(k*10 + 1)~d(k*10 + 9)구간에서 제네레이터 결과값들이 간격이 2씩 있고,

d(k*10 + 9) > d(k*10 + 10)같은 규칙까지는 코드로 가능해서

1차 수열로 1~4999의 합에서 셀프 넘버가 아닌 수를 뺴려고 했지만 d(91) == d(100)처럼 중복되는 경우에 대한 처리 규칙을 못 잡아서

리스트 검색등에 in 사용.

다음은 Lv. 4

원래라면 Lv. 5까지 다 풀고 파이썬기반으로 작은 프로젝트를 진행하려고 했지만 현재 시간관리상 레벨5까지 하고

프로젝트로 넘어가기에는 지체가 심해질것같아서

코딩도장 문제풀이는 여기까지.

기타. 변경이력

일자	변경이력
2015-03-10	초안.