search

itisused / Algorithm_Study

알고리즘 문제풀이 연습
0 stars 2 forks source link

02_Implementation #3

Open itisused opened 2 years ago

itisused commented 2 years ago

스터디 2회차 구현: 10월 11일 ~ 10월 16일 풀어볼 코드

01) 필수1 문자열 압축 (출처 - 2020 KAKAO BLIND RECRUITMENT) 02) 필수2 자물쇠와 열쇠 (출처 - 2020 KAKAO BLIND RECRUITMENT) 03) 선택 기둥과 보 설치 (출처 - 2020 KAKAO BLIND RECRUITMENT)

참고

Cheyenne-cloud commented 2 years ago

1. String Compression

1. 문자를 1~len(s)//2 만큼으로 쭉 자른다.

2. 연속해서 해당 패턴이 나오는 수를 셈

2-1. 각 패턴당 count=1부터 시작 2-2. 다음 패턴과 지금 패턴이 동일하지 않으면 count 올라가지 않고, 같으면 count 올라감 2-3. 다음 패턴과 지금 패턴이 동일하지 않을 때 현재의 count가 1 초과이면 패턴 앞에 숫자를 붙인 패턴을 써주고, 1이면 패턴만 씀 2-4. 해당 패턴들을 모두 join 시켜주고, length 써주기

3. 함수화시 문자열 길이가 1인 경우 추가

def solution(s):

    if len(s) == 1:
        answer = 1

    else:
        compressed = []

        for n in range(1, (len(s)//2)+1):
            patterns = [s[i:i+n] for i in range(0, len(s), n)]
            count = 1
            compressing = []
            for idx, pattern in enumerate(patterns):
                try:
                    if patterns[idx] == patterns[idx+1]:
                        count += 1
                    else:
                        if count == 1:
                            compressing.append(pattern)
                        else:
                            compressing.append(str(count)+pattern)
                            count = 1
                except:
                    if patterns[idx] != patterns[idx-1]:
                        compressing.append(pattern)
                    else:
                        compressing.append(str(count)+pattern)

            final_string = ''.join(compressing)
            compressed.append(len(final_string))

        answer = min(compressed)

    return answer

2. Locks and Keys

def solution(key, lock):

    # import 및 기본 변수 지정
    import numpy as np
    key = key
    lock = lock
    M = len(key)
    N = len(lock)

    # 1. key의 0도, 90도, 180도, 270도 회전 케이스 구현해 리스트 cases에 보관
    # ------------------------------------------------------------------------
    # 90도를 돌리면
    # 1. 현재 열의 좌표는 90도 돌린 후의 행 좌표가 된다.
    # 2. 행 좌표는 pairs에 기재된 쌍으로 달라진다.
    # 3. 구현할 케이스는 90도, 180도, 270도의 3개
    ### 준비 1. 0부터 key의 len-1까지 1씩 증가하는 리스트를 만든다.
    ### 준비 2. M * M 의 빈 행렬을 준비한다.
    ### 준비 3. 빈 딕셔너리 pairs를 생성한다 -- 여기에 서로 바뀔 인덱스 번호를 쌍으로 지정할 것임
    ### 준비 4. 바뀔 인덱스 페어를 만들어준다.
    # ------------------------------------------------------------------------

    # 0부터 key의 len-1까지 1씩 증가하는 리스트
    for_idx = [i for i in range(M)]

    # M * M 크기의 빈 배열 만들기
    # or new_array = np.zeros(shape=(M, M))
    new_array = [[0 for i in range(M)] for j in range(M)]

    # key를 90도씩 돌릴 케이스를 저장할 리스트 만들기
    cases = [key]

    # 90도 돌린 경우를 만들때 쓸 인덱스 페어 생성하기
    pairs = {}
    for idx, num in enumerate(for_idx):
        pairs[for_idx[0+idx]] = for_idx[-1-idx]

    # 90도 회전 케이스 구현 - 90도, 180도, 270도 3개 케이스 저장
    for i in range(3):
        new_array = [[0 for i in range(M)] for j in range(M)]
        for j in range(M):
            for k in range(M):
                new_array[k][pairs[j]] = cases[i][j][k]
        # 작성한 것을 미리 준비해놓은 cases 리스트에 담아주기
        cases.append(new_array)

    # 2. lock을 기준으로 key가 들어갈 수 있는 공간을 고려한, 넓힌 배열 공간 만들기
    sum_array = np.pad(lock, (M-1,M-1))

    # 3. 목표로 하는 lock의 모습은 match
    match = np.ones(shape=(N, N))

    # 4. sum_array에서 각 case만큼을 더해주면서 가운데 lock의 모습 뽑아 match와 비교하기
    answer = False
    for c in range(len(cases)):
        for i in range(N+M-1):
            for j in range(N+M-1):
                for k in range(M):
                    for l in range(M):
                        sum_array[i+k][j+l] += cases[c][k][l]
                current_lock = sum_array[(M-1):(M+N-1), (M-1):(M+N-1)]
                if (current_lock.tolist()==match.tolist()) == True:
                    answer = True
                sum_array = np.pad(lock, (M-1,M-1))

    return answer
itisused commented 2 years ago

항상 1등이시네요 ㅎ

lizzys16 commented 2 years ago

1. 문자열 압축

def solution(s):
    answer = []
    s_len = len(s)
    if s_len == 1:
        return 1

    for i in range(1, s_len//2 + 1): 
        result = ''
        cnt = 1
        pattern = s[:i]

        for j in range(i, s_len, i): 
            if pattern == s[j:j+i]:
                cnt += 1
            else:
                if cnt != 1:
                    result += str(cnt) + pattern
                else:
                    result += pattern
                pattern = s[j:j+i]
                cnt = 1

        # 마지막 패턴이 저장되기전에 2번째 포문이 끝나버려서 후처리필요
        if cnt != 1:
            result += str(cnt) + pattern
        else:
            result += pattern

        answer.append(len(result))

    return min(answer)

2. 자물쇠와 열쇠

너무 어려워서 블로그 참고하면서 이해하면서 풀었습니다. 이해하는 데만 반나절 😵

# 최대한 큰 matrix를 만드는 게 중요한 것 같음. 
# 안그러면 key가 위 아래로 이동할 때 out of index range 런타임 에러.
# M <= N 이기 때문에 M에 2배를 해주었음.

# matrix 90도 회전
def rotate90(matrix):
    return list(zip(*matrix[::-1]))

# 열쇠 넣기
def attach(m, n, matrix, key):
    for i in range(len(key)):
        for j in range(len(key)):
            matrix[m+i][n+j] += key[i][j]

# 열쇠 빼기
def detach(m, n, matrix, key):
    for i in range(len(key)):
        for j in range(len(key)):
            matrix[m+i][n+j] -= key[i][j]

def check(matrix, M, N):
    for i in range(N):
        for j in range(N):
            if matrix[M+i][M+j] != 1:
                return False
    return True

def solution(key, lock):
    M, N = len(key), len(lock)

    # step 1 - 2*M+N 사이즈의 martix 만들기
    matrix = [[0] * (2*M+N) for _ in range(2*M+N)]

    # step 2 - matrix 중앙에 lock 넣기
    # out of index range 방지를 위해 M을 기준으로 넣어줌
    for i in range(N):
        for j in range(N):
            matrix[M+i][M+j] = lock[i][j]

    # step 3 - key를 90도, 180도, 270도, 0도 4방향으로 돌려서 확인
    rotated_key = key
    for _ in range(4):
        rotated_key = rotate90(rotated_key)
        # step 4 - key를 움직이면서 맞춰보기
        for m in range(M+N):
            for n in range(M+N):
                # 열쇠 맞춰보기
                attach(m, n, matrix, rotated_key)
                if check(matrix, M, N):
                    return True
                # 원상복구
                detach(m, n, matrix, rotated_key)
    return False
2pterons commented 2 years ago

블로그 출처:

문자열 압축

기둥과 보 설치

문자열 압축

def solution(s): 
    result=[] 
    if len(s)==1: 
        return 1

    for i in range(1, (len(s)//2)+1): 
        b = '' 
        cnt = 1 
        tmp=s[:i] 

        for j in range(i, len(s), i):
            if tmp==s[j:i+j]: 
                cnt+=1 
            else: 
                if cnt!=1: 
                    b = b + str(cnt)+tmp 
                else: 
                    b = b + tmp 
                tmp=s[j:j+i] 
                cnt = 1 
        if cnt!=1: b = b + str(cnt) + tmp 
        else: 
            b = b + tmp 

        result.append(len(b)) 
    return min(result)

자물쇠와 열쇠

def attach(x, y, M, key, board):
    for i in range(M):
        for j in range(M):
            board[x+i][y+j] += key[i][j]

def detach(x, y, M, key, board):
    for i in range(M):
        for j in range(M):
            board[x+i][y+j] -= key[i][j]

def rotate90(arr):
    return list(zip(*arr[::-1]))

def check(board, M, N):
    for i in range(N):
        for j in range(N):
            if board[M+i][M+j] != 1:
                return False;
    return True

def solution(key, lock):
    M, N = len(key), len(lock)

    board = [[0] * (M*2 + N) for _ in range(M*2 + N)]
    # 자물쇠 중앙 배치
    for i in range(N):
        for j in range(N):
            board[M+i][M+j] = lock[i][j]

    rotated_key = key
    # 모든 방향 (4번 루프)
    for _ in range(4):
        rotated_key = rotate90(rotated_key)
        for x in range(1, M+N):
            for y in range(1, M+N):
                # 열쇠 넣어보기
                attach(x, y, M, rotated_key, board)
                # lock 가능 check
                if(check(board, M, N)):
                    return True
                # 열쇠 빼기
                detach(x, y, M, rotated_key, board)

    return False

기둥과 보 설치

def impossible(result):
    COL, ROW = 0, 1
    for x, y, a in result:
        if a == COL: # 기둥일 때
            if y != 0 and (x, y-1, COL) not in result and \
        (x-1, y, ROW) not in result and (x, y, ROW) not in result:
                return True
        else: # 보일 때
            if (x, y-1, COL) not in result and (x+1, y-1, COL) not in result and \
        not ((x-1, y, ROW) in result and (x+1, y, ROW) in result):
                return True
    return False

def solution(n, build_frame):
    result = set()

    for x, y, a, build in build_frame:
        item = (x, y, a)
        if build: # 추가일 때
            result.add(item)
            if impossible(result):
                result.remove(item)
        elif item in result: # 삭제할 때
            result.remove(item)
            if impossible(result):
                result.add(item)
    answer = map(list, result)

    return sorted(answer, key = lambda x : (x[0], x[1], x[2]))
pangyosim commented 2 years ago

문자열 압축

def solution(s):
    answer = len(s)
    for x in range(1, int(len(s)/2)+1):
        d = 0
        comp = ''
        c = 1
        for i in range(0, len(s), x):
            temp = s[i:i+x]
            if comp == temp:
                c += 1
            elif comp != temp:
                d += len(temp)
                if c > 1:
                    d += len("{}".format(c))
                c = 1
                comp = temp
        if c > 1:
            d += len("{}".format(c))
        answer = min(answer, d)
    return answer

자물쇠와 열쇠

블로그 출처: https://johnyejin.tistory.com/127

#시계방향으로 90도 회전
def rotation(arr):
    n = len(arr)
    ret = [[0] * n for _ in range(n)]

    for i in range(n):
        for j in range(n):
            ret[j][n-1-i] = arr[i][j]
    return ret

#자물쇠가 열리는지 체크
#expendList=(len(key)-1)*2+len(lock)) 크기의 배열
def check(startX, startY, key, lock, expendSize, start, end):
    expendList = [[0] * expendSize for _ in range(expendSize)]

    for i in range(len(key)):
        for j in range(len(key)):
            expendList[startX + i][startY + j] += key[i][j]

    for i in range(start, end):
        for j in range(start, end):
            expendList[i][j] += lock[i - start][j - start]
            if expendList[i][j] != 1:
                return False

    return True

def solution(key, lock):
    start = len(key) - 1  
    end = start + len(lock)  
    expendSize = len(lock) + start * 2  

    for a in range(0, 4):
        for i in range(end):
            for j in range(end):
                if check(i, j, key, lock, expendSize, start, end):
                    return True
        key = rotation(key)

    return False
itisused commented 2 years ago

1. 문자열 압축

# 21.09. 언젠가 처음 푼 코드
def solution(s):
    num = len(s)
    max_iter = num // 2

    result = [[], []]
    sep_list = []
    for d in range(1, max_iter+2):
        temp_result = []
        sep_list = [s[d_inn:d_inn+d] for d_inn in range(0, num, d)] # 문자 나누기
        temp_temp = [sep_list.pop(0)]

        # 같은 개수 찾기
        for idx, _ in enumerate(sep_list):
            if temp_temp[-1] == sep_list[idx]:    # 같은 문자가 있는 경우
                temp_temp.append(sep_list[idx])
            else:                               # 같은 문자가 없는 경우
                if len(temp_temp) > 1:
                    temp_result.extend([str(len(temp_temp)), temp_temp[-1]])
                else:
                    temp_result.extend([temp_temp[-1]])
                temp_temp.clear()
                temp_temp = [sep_list[idx]]

        # 마지막에 작업한게 안 딸려오네
        if len(temp_temp) > 1:
            temp_result.extend([str(len(temp_temp)), temp_temp[-1]])
        else:
            temp_result.extend([temp_temp[-1]])

        temp_result = ''.join(temp_result)
        result[0].append(temp_result); result[1].append(len(temp_result))

    answer = min(result[1])
    return answer

2. 자물쇠와 열쇠

# 여긴 약간의 수학이 있네(?)
# key 리스트(결국, 2차원 행렬)의 90도 회전 함수
def rotation_key(key):
    n_dim = len(key) # key dimension
    rot_key = [[0] * n_dim for _ in range(n_dim)] # 2차원 리스트 생성
    # 여긴 정사각 행렬이니 n_dim 하나로 해결한 것이고
    # 만약 직사각 행렬일 경우 row, column 따로 계산해서 rot_key 초기화해야 함

    for i in range(n_dim):
        for j in range(n_dim):
            rot_key[j][(n_dim-1)-i] = key[i][j]
    return rot_key

# 확대한 lock 리스트(행렬)의 중앙 부분의 각 구성 원소가 모두 1인지 확인
def check_element_one(extend_lock):
    extend_n_dim = len(extend_lock) // 3
    for i in range(extend_n_dim, 2 * extend_n_dim):
        for j in range(extend_n_dim, 2 * extend_n_dim):
            if extend_lock[i][j] != 1:
                return False
    return True

def solution(key, lock):

    # 1. lock를 가로 세로 3배씩 확장 (신박하네.)
    lock_dim = len(lock)
    key_dim = len(key
    extend_lock_dim = lock_dim * 3
    extend_lock = [[0] * extend_lock_dim for _ in range(extend_lock_dim)] # 크기 3배 확장시킨 2차원 리스트 생성

    # 2. 확대한 lock의 정중앙에 Original lock 삽입
    for i in range(lock_dim, 2*lock_dim):
        for j in range(lock_dim, 2*lock_dim):
            extend_lock[i][j] = lock[i-lock_dim][j-lock_dim]

    # 3. key를 회전시켜가면서 풀리는지 확인
    rotation_num = 360 // 90 # 각 칸이 사각형이라서
    for rotation in range(rotation_num):
        # 먼저 회전
        key = rotation_key(key)

        # 훑는다.
        # 어느 M by M 지점에 할지 위치를 잡고
        for i in range(1, extend_lock_dim-key_dim ):
            for j in range(1, extend_lock_dim-key_dim ):

                # 더한다.
                for k in range(key_dim ):
                    for l in range(key_dim ):
                        extend_lock[i+k][j+l] = extend_lock[i+k][j+l] + key[k][l]

                # 중앙이 모두 1인지 체크
                answer = check_element_one(extend_lock)
                if answer:
                    return answer

                # 다시 원상 복구
                for k in range(key_dim ):
                    for l in range(key_dim ):
                        extend_lock[i+k][j+l] = extend_lock[i+k][j+l] - key[k][l]
    return answer

3. 기둥과 보 설치

?
itisused commented 2 years ago

2021.10.17 p.m. 11:00 ~ 2021.10.18 a.m. 00:00 스터디 2회차 종료 참석자: 김예찬, 김태영, 김택현, 심판교, 이지수, 진가형