[Algo]実装/文字列を見直すと良い問題集!

実装/文字列50チャレンジ!右のディレクトリを参照してください.
1.プログラマー-アクセント辞典
所要時間:20分

import itertools

def solution(word):
    word = [w for w in word]
    result = []
    for n in range(1,6):
        result += [list(item) for item in list(itertools.product((['A', 'E', 'I', 'O', 'U']), repeat=n))]
    result = sorted(result)
    return result.index(word) + 1

2.プログラマー-かっこを回転
時間:60分
ドアから配列を削除してから切るのを忘れないでください.インデックスエラー

コピーしろ

s[i:]+s[:i]操作、削除または変更可能

listをdequeとして保存し、文字列をrotateで回転できます.
- deque(s).回転(1):グリッドを右に移動

deque(s).rotate(-1):左に

を移動

def check(s):
    if s[0] == ')' or s[0] == ']' or s[0] == '}':
        return False
    if s[-1] == '(' or s[-1] == '[' or s[-1] == '{':
        return False
    return True

def is_vaild(s):
    dict = {'(': ')','[': ']','{': '}'}
    temp_s = [w for w in s]
    
    if not check(temp_s):
        return False

    for i in range(len(temp_s)):
        if temp_s[i] not in dict:
            if temp_s[i-1] in dict and temp_s[i] != dict[temp_s[i-1]]:
                return False
            
    while len(temp_s):
        if not check(temp_s):
            return False
        
        temp = dict[temp_s[0]]
        del temp_s[0]
        
        for i in range(len(temp_s)):
            if temp == temp_s[i]:
                del temp_s[i]
                break
    return True

def solution(s):
    answer = 0
    
    if len(s) % 2 != 0:
        return answer
    
    s = list(s)
    for i in range(len(s)):
        if is_vaild(s[i:] + s[:i]):
            answer += 1
        
    return answer

スタックを使用して

を解放

def is_vaild(s):
    dict = {')':'(', ']':'[','}':'{'}
    temp_s = [w for w in s]
    stack = []

    while len(temp_s):
        if temp_s[0] in ['(','[','{']:
            stack.append(temp_s.pop(0))
        else:
            if len(stack):
                if dict[temp_s[0]] != stack[-1]:
                    return False
                stack.pop()
                del temp_s[0]
            else: #stack이 비었을때
                return False

    return True

def solution(s):
    answer = 0
    
    if len(s) % 2 != 0:
        return answer
    
    s = list(s)
    for i in range(len(s)):
        if is_vaild(s[i:] + s[:i]):
            answer += 1
        
    return answer

3.プログラマー-あっしゅく
所要時間:50分

def solution(msg): 
    answer = []
    
    dict = {}
    for i in range(1,27):
        dict[chr(i+64)] = i
    
    n = 1
    while True:
        i = 1         
        while len(msg) >= i:
            if msg[:i]in dict and len(msg) == i:
                answer.append(dict[msg])
                return answer
            if msg[:i] not in dict:
                w = msg[:i-1]
                answer.append(dict[w])
                msg = msg[i-1:]
                break
            i += 1
        if len(msg) > 0:
            dict[w + msg[0]] = 26 + n
            n += 1
        else:
            break

4.プログラマー-トーン
s.sort(key=len)->なぜ長さで並べ替えるのか分からない

def solution(s):
    answer = []
    s = s[2:-2].split('},{')
    s = [w.split(',') for w in s]
    # print(s)
    s.sort(key=len)
    # print(s)
    for a in s:
        for w in a:
            if int(w) not in answer:
                answer.append(int(w))
    return answer

5.プログラマー-推薦職業群
時間:40分
->この利用も考えられる!
score_table = {lan : score for lan, score in zip(languages, preference)}
->もっと簡単な方法
dict(zip(languages, preference))

>>> keys = [1, 2, 3]
>>> values = ["A", "B", "C"]
>>> dict(zip(keys, values))
{1: 'A', 2: 'B', 3: 'C'}

def solution(table, languages, preference):
    answer = []
    table_dict = {}
    score_dict = {}
    index_to_score = [5,4,3,2,1]
    
    for t in table:
        t = t.split(' ')
        table_dict[t[0]] = t[1:]
        
    for key,values in table_dict.items():
        total = 0
        for i, lan in enumerate(languages):
            if lan in values:
                total += index_to_score[values.index(lan)] * preference[i]
        score_dict[key] = total
        
    max_score = max(score_dict.values())
    for k,v in score_dict.items():
        if v == max_score:
            answer.append(k)
    return sorted(answer)[0]

6.プログラマー-畑を掘る
時間:1時間悩んだあげく->グーグルに助けを求めた

def solution(land):
    answer = 0
    tmp = land
    col = land[0].index(max(land[0]))
    for i in range(1,len(land)):
        for j in range(len(land[0])):
            # print(tmp[i-1][:j]+tmp[i-1][j+1:])
            tmp[i][j] += max(tmp[i-1][:j]+tmp[i-1][j+1:])
    return max(tmp[-1])

->バージョンエラー

def solution(land):
    answer = 0
    tmp = land
    col = land[0].index(max(land[0]))
    for i in range(1,len(land)):
        for j in range(4):
            if col != j:
                tmp[i][j] += tmp[i-1][col]
        col = tmp[i].index(max(tmp[i][:col]+[0]+tmp[i][col+1:]))
        print(col)
            
    return max(tmp[-1])

7.プログラマー-行列の乗算
->構造的には、まずforドアをどう回すべきかを考えてみましょう...!
マトリクスを乗じた場合、結果は(axc)です.
(a x b) * (b x c) = (a x c)

def solution(arr1, arr2):
    answer = [[0] * len(arr2[0]) for _ in range(len(arr1))]
    total = 0
    for a in range(len(arr1)):
        for c in range(len(arr2[0])):
            for b in range(len(arr2)):
                # print(a,b,b,c)
                total += arr1[a][b] * arr2[b][c]
            # print('---------------')
            answer[a][c] = total
            total = 0
    return answer

8.プログラマー-ファイル名のソート
->正規表現を学習します.

def splict_str(s):
    for i,w in enumerate(s):
        if w.isdigit():
            return [s[:i], int(s[i:])]
def solution(files):
    answer = []
    files = [[f] for f in files]
    for i,file in enumerate(files):
        if '.' in file[0]:
            index = file[0].index('.')
            # file += [file[0][:index].lower()]
            file += splict_str(file[0][:index].lower())
        elif '-' in file[0]:
            index = file[0].index('-')
            index2 = file[0].index(' ')
            file += [file[0][:index+1].lower()]
            file += [int(file[0][index+1:index2])]
    # print(files)
    files = sorted(files, key = lambda x : (x[1], x[2]))
    # print(files)
    for f in files:
        answer.append(f[0])
    return answer

9.プログラマー-最小長方形
時間:15分
->最大値を検索する方法を理解する
->藍多食に慣れる

def solution(sizes):
    sizes = [sorted(s) for s in sizes]
    m = max(sizes, key = lambda x: x[0])
    n = max(sizes, key = lambda x: x[1])
    return m[0] * n[1]

def solution(sizes):
    sizes = [sorted(s) for s in sizes]
    m = max(s[0] for s in sizes)
    n = max(s[1] for s in sizes)
    return m * n

10.プログラマー-N個の最小公倍数
->ライブラリを使用して再開

from gcd import math

11.プロドレマーズ-さっきの歌は
時間:2時間以上
置き換えを考えろ!!

from datetime import datetime

def check(m,n):
    if m in n:
        return True
    return False

def get_new_m(arr):
    tmp = []
    for w in arr:
        if w == '#':
            tmp[-1] += '#'
            continue
        tmp.append(w)
    for i in range(len(tmp)):
        if tmp[i][-1] == '#':
            tmp[i] = tmp[i][0].lower()
    return tmp

def get_music(music):
    t = []
    for mu in music:
        if mu == '#':
            t[-1] = t[-1].lower()
            continue
        t.append(mu)
    return ''.join(t)

def solution(music, musicinfos):
    answer = []
    pre_diff_sec = 0
    music = get_music(music)
    for m in musicinfos:
        m = m.split(',')
        diff_sec = (datetime.strptime(m[1],"%H:%M") - datetime.strptime(m[0],"%H:%M")).seconds // 60
        entire_music = get_new_m(m[3])
        
        n = ''.join((entire_music * diff_sec)[:diff_sec])
        if check(music,n) and diff_sec > pre_diff_sec:
            pre_diff_sec = diff_sec
            answer = [m[2],diff_sec]
    if answer:
        return answer[0]
    return '(None)'

12.プログラマー-アクセスの長さ
所要時間:20分

def solution(dirs):
    move = {'U':[0,1],'D':[0,-1],'R':[1,0],'L':[-1,0]}
    answer = []
    x,y = 0,0
    for dir in dirs:
        xx,yy = x + move[dir][0], y + move[dir][1]
        if xx < -5 or xx > 5 or yy < -5 or yy > 5:
            continue
        if [str(x)+str(y), str(xx)+str(yy)] not in answer:
            answer.append([str(x)+str(y), str(xx)+str(yy)])
            answer.append([str(xx)+str(yy), str(x)+str(y)])
        x, y = xx, yy
    return len(answer) // 2

より簡潔:strに変換することなく比較可能
ex) [1,2,3,4] == [4,3,2,1] //false

def solution(dirs):
    move = {'U':[0,1],'D':[0,-1],'R':[1,0],'L':[-1,0]}
    answer = []
    x,y = 0,0
    for dir in dirs:
        xx,yy = x + move[dir][0], y + move[dir][1]
        if xx < -5 or xx > 5 or yy < -5 or yy > 5:
            continue
        if [x,y,xx,yy] not in answer:
            answer.append([x,y,xx,yy])
            answer.append([xx,yy,x,y])
        x, y = xx, yy
    return len(answer) // 2

13.プログラマー-チェックアウト
所要時間:2時間ですが、すべて失敗しました.3時間以上で成功
-> collections.カウンタの理解
->配列長を超えたインデックスでスライドしようとすると[]と表示されます

#get: 퇴실이 끝나지 않은 사람 수 구하기. 즉, 아직까지는 입실만 찍힌 사람 
def get(arr):
    return len(arr) - 2 * (len(arr) - len(set(arr)))#중복으로 나타나지 않은 요소 찾기

# def get(arr): # 같은 의미이지만 시간초과..!
#     arr = [a for a in arr if arr.count(a) == 1]
#     return len(arr)

def solution(enter, leave):
    answer = [0] * len(leave)
    tmp = []
    #입실 퇴실 모든 과정을 tmp에 저장한다
    for l in leave:
        if l not in tmp:
            tmp += enter[:enter.index(l)+1] # 첫번째로 퇴실하는 사람이 입실할때까지 
            enter = enter[enter.index(l)+1:] #입실한 사람들 제거
        tmp.append(l)
    #모든 입실 퇴실 과정을 바탕으로  
    for i in range(1,len(leave)+1):
        start_index = tmp.index(i,0)
        end_index = tmp.index(i,start_index+1)
        if end_index - start_index == 1: #입실 퇴실이 연속으로 일어났을때
            answer[i-1] += get(tmp[:start_index])
        else:
            arr_set = list(set(tmp[start_index+1:end_index]))
            answer[i-1] += len(arr_set) #입실과 퇴실 사이에 들어온 사람
            arr = [a for a in tmp[:start_index] if a not in arr_set]
            answer[i-1] += get(arr) #입실 전에 들어와있던 사람
    return answer

他の人を解答します.論理が粗い.

def solution(enter, leave):
    answer = [0] * len(enter)
    room = []
    e_idx = 0
    for l in leave:
        while l not in room: # 퇴실할 사람이 방에 들어올때까지 입실
            room.append(enter[e_idx])
            e_idx += 1
        room.remove(l) # 퇴실할 사람이 방에 들어온다면 해당 사람을 퇴실시킨다.
        for p in room: 
            answer[p - 1] += 1 # 현재 방에 있는 사람들이 만난 사람 수에 1씩 더해준다.
        answer[l - 1] += len(room) # 퇴실한 사람의 만난 사람 수에 현재 방 인원수를 더해준다.
    return answer

14.プログラマー-圧縮後数世紀
時間:解決できません
->関数の関数
->ブロックごとの関数のロードを確認する

def solution(arr):
    answer = [0,0]
    l = len(arr)
    def check(a,b,n):
        target = arr[a][b]
        for i in range(a,a+n):
            for j in range(b,b+n):
                if target != arr[i][j]:
                    n = n // 2
                    check(a,b,n)
                    check(a,b+n,n)
                    check(a+n,b,n)
                    check(a+n,b+n,n)
                    return
        answer[target] += 1
    check(0,0,l)
    return answer

15.プログラマー-n進ゲーム
所要時間:20分

import string

def convert(num, base):
    tmp = string.digits+string.ascii_uppercase
    q, r = divmod(num, base)
    if q == 0 :
        return tmp[r] 
    else :
        return convert(q, base) + tmp[r]
    
def solution(n, t, m, p):
    tmp = ''
    answer = ''
    
    num = 0
    while len(tmp) < m * t:
        tmp += str(convert(num, n))
        num += 1
        
    for i in range(t):
        answer += tmp[p-1 + m * i] 
    
    return answer

16.プログラマー-ジャンプと瞬間移動
所要時間:40分以内に完了できません...
半減したかったけど奇数の時-まさか1

def solution(n):
    ans = 0
    while n != 0:
        if n % 2 == 0:
            n = n // 2
        else:
            n -= 1
            ans += 1
    return ans

17.プログラマー-予算
所要時間:5分、レベル1

def solution(d, budget):
    answer = 0
    d = sorted(d)
    
    for m in d:
        if budget == 0:
            return answer
        if budget - m >= 0:
            budget -= m
            answer += 1
    return answer

18.プログラマー-収集シール(2)
-解決できない
所要時間:1時間半以上、レベル3
基本的なテーマにのみ答えます...dp.を利用すべきです.

def odd_index(arr):
    return [arr[i] for i in range(len(arr)) if i % 2 !=0]

def even_index(arr):
    return [arr[i] for i in range(len(arr)) if i % 2 == 0]

def compare_arr(arr):
    a = sum([arr[i] for i in range(len(arr)) if i % 2 !=0])
    b = sum([arr[i] for i in range(len(arr)) if i % 2 == 0])
    return max(a,b)
    
def solution(sticker):
    answer = 0
    if len(sticker) == 1:
        return sticker[0]
    
    if len(sticker) % 2 == 0:
        return compare_arr(sticker)
    else:
        a = sum(odd_index(sticker))
        b1 = sticker[0] + compare_arr(sticker[2:-1])
        b2 = sticker[-1] + compare_arr(sticker[1:-2])
        return max(a, b1, b2)

19.プログラマー-正方形
->もう一度解いてみる
最大公約数

import math

def solution(w,h):
    return w * h - (w + h - math.gcd(w,h))

20.プログラマー-基地局の設定
所要時間:30～40分(タイムアウトなし)
タイムアウトでは解決できません.O(n)で解決しなければならない.

#시간초과
def solution(n, stations, w):
    answer = 0
    s = []
    for station in stations:
        s += [num for num in range(station-w,station+w+1) if 1 <= num <= n]
    s.append(n+1)

    tmp = 0
    for index in range(1, n+2):
        if index not in s:
            tmp += 1
        elif tmp > 0:
            answer += tmp // (w * 2 + 1)
            if tmp % (w * 2 + 1) != 0:
                answer += 1
            tmp = 0
    return answer

21.プログラマー-デジタルゲーム

def solution(A, B):
    answer = 0
    A.sort()
    B.sort()
    
    i = 0
    for j in range(len(B)):
        if A[i] < B[j]:
            i += 1
            j += 1
            answer += 1
        else:
            j += 1
            
    
    return answer

22.プログラマー-かいてんマトリクスきょうかい
所要時間:何日ですか.ははは
方向ベクトルで回転します.
後で解いてみよう!!

def solution(rows, columns, queries):
    answer = []
    arr = [[0] * columns for _ in range(rows)]
    dx = [0,1,0,-1]
    dy = [1,0,-1,0]
    
    num = 1
    for i in range(rows):
        for j in range(columns):
            arr[i][j] = num
            num += 1
    
    for a,b,c,d in queries:
        a,b,c,d = a-1,b-1,c-1,d-1
        x,y = a,b
        cur = arr[x+1][y]
        minValue = cur
        n = (c - a + 1) * 2 + (d - b + 1 - 2) * 2
        direction = 0

        for i in range(n):
            tmp = arr[x][y]
            arr[x][y] = cur
            cur = tmp
            minValue = min(cur,minValue)
            x += dx[direction]
            y += dy[direction]
            
            if not (b <= y <= d and a <= x <= c):
                x -= dx[direction]
                y -= dy[direction]
                direction = (direction + 1) % 4
                x += dx[direction]
                y += dy[direction]
        answer.append(minValue)

    return answer

23.プログラマー-カタツムリ匹

def solution(n):
    answer = []
    maxLen = [num for num in range(1,n+1)]
    tmp = [[0] * n for _ in range(n)]
    dr = [1,0,-1,1]
    dc = [0,1,0,-1]
    
    target = 0
    for num in range(1, n+1):
        target += num
    r,c = 0,0
    num = 1
    direction = 0
    while num <= target:
        tmp[r][c] = num
        r += dr[direction] 
        c += dc[direction] 
        if not (0 <= r < n and 0 <= c < n) or tmp[r][c] != 0 or n - tmp[r].count(0) >= maxLen[r]:
            r -= dr[direction] 
            c -= dc[direction]
            direction = (direction + 1) % 4
            if direction == 0:
                direction += 1
            r += dr[direction] 
            c += dc[direction]
        num += 1

    for t in tmp:
        for i in t:
            if i == 0:
                continue
            answer.append(i)
    return answer    

24. Hacker rank - Simple Text Editor

S = ''
Q = int(input())
tmp = []
for i in range(Q):
    ops = input().split(' ')
    if ops[0] == '1':
        tmp.append(S)
        S += ops[1]
    elif ops[0] == '2':
        tmp.append(S)        
        S = S[:-int(ops[1])]
    elif ops[0] == '3':
        print(S[int(ops[1]) - 1])
    elif ops[0] == '4':
        S = tmp.pop()

25.プログラマー-n*2クリップスキーム

思いがけない解答方法...ㅜ

divmod(i,n)
-tuple形式でパケットを返して解く場合、*divmod(i,n)

i//n, i%n

def solution(n, left, right):
    answer = []
    
    for i in range(left, right+1):
        # print(divmod(i, n))
        answer.append(max(divmod(i, n)) + 1)
    # print(answer)
    return answer

26.プログラマー-スキルツリー

def solution(skill, skill_trees):
    answer = 0
    for skills in skill_trees:
        tmp = []
        flag = True
        tmp_skill = list(skill)
        for s in skills:
            if s in skill:
                if s != tmp_skill.pop(0):
                    flag = False
                    break
        #         tmp.append(skill.index(s))
        # if flag and sorted(tmp) == tmp:
        #     answer += 1
        else:
            answer += 1
    return answer