1. 문자열 압축

문제 링크

• 프로그래머스 난이도 : 레벨 2

여러 방법이 있는데, 어차피 문자를 앞에서부터 잘라서 압축하는 것이니까, 자를 수 있는 문자열의 길이가 1~n/2 라고 생각했다.

그래서 인덱스 따져가면서 실제로 압축한 문자열을 만들어줘서, 길이가 가장 작은 문자열을 선택하는 방식으로 했다.

친구는 문자열을 만들지 않고 카운트를 해줬다고 하는데, 이 경우는 압축된 문자가 10, 100, 1000이 넘어가면 문자열 길이가 하나씩 더 늘어나는 것을 주의해야 한다.

코드

def solution(s):
    answer = len(s)
    # 1부터 n/2개로 문자를 자름
    for cut in range(1, len(s)):
        now_idx = cut
        bef = s[:cut]
        count = 1
        tmp = ""
        while now_idx + cut <= len(s):
            # 만약 이전 문자열과 같으면
            if bef == s[now_idx:now_idx + cut]:
                count += 1
            else:
                if count > 1:
                    tmp += str(count)
                tmp += bef
                count = 1
                bef = s[now_idx:now_idx + cut]
            now_idx += cut

        
        if count > 1:
            tmp += str(count)
        tmp += s[now_idx-cut:]
        
        answer = min(answer, len(tmp))
        
    return answer

2. 괄호 변환

문제 링크

• 프로그래머스 난이도 : 레벨 2

재귀 함수를 구현하는 문제 같다.
u,v로 쪼개서 계속 재귀를 돌린 값을 리턴하면 된다.
문제를 그대로 따라서 하면 될 것이고, 올바른 괄호 문자열을 판단하는 방법은 스택을 사용하든, 왼쪽 오른쪽 괄호 갯수 따져주든 상관 없다.

코드

def solution(p):

    answer = recursive(p)
    return answer

def recursive(s1):
    # 빈 문자열인 경우 빈 문자열 반환
    if len(s1) == 0:
        return ''
    u = ''
    v = ''
    left_count = 0
    right_count = 0
    # 균형잡힌 괄호 문자열 u,v로 분리
    is_correct = True
    for idx in range(len(s1)):
        if s1[idx] == '(':
            left_count += 1
        else:
            right_count += 1
        u += s1[idx]
        if left_count < right_count:
            is_correct = False
            
        if left_count == right_count:
            v = s1[idx+1:]
            break
    
    is_correct = True
    left_count = 0
    right_count = 0
    for idx in range(len(u)):
        if left_count < right_count:
            is_correct = False
            break
        if u[idx] == '(':
            left_count += 1
        else:
            right_count += 1
    
    # 올바른 괄호 문자열이면
    if is_correct:
        return u + recursive(v)
    # 4번
    else:
        string = '('
        string += recursive(v)
        string += ')'
        u = u[1:-1]
        for idx in range(len(u)):
            if u[idx] == '(':
                string += ')'
            elif u[idx] == ')':
                string += '('
            else:
                string += u[idx]
        
        return string

3. 자물쇠와 열쇠

문제 링크

• 프로그래머스 난이도 : 레벨 3

완전 탐색을 사용하는 문제인데, 키를 돌려서 그래프 매칭을 시키는 것이 관건이다. 이것을 어떻게 구현할 것인가가 중요한데, 그래프 크기를 키가 한칸만 겹칠 수 있을 만큼만 늘려서 처음부터 끝까지 키를 돌려가며 매칭해보면 된다.

코드

# N + N-1 + N-1 = 3N - 2
# 가로 세로가 3N-2
# 시작점이 N-1, N-1 -> 2N-2, 2N-2까지


def generate_lock(key, lock):
    m = len(key)
    n = len(lock)
    tmp = [[0] * (2 * m - 2 + n) for _ in range(2 * m - 2 + n)]
    for y in range(m - 1, m + n - 1):
        for x in range(m - 1, m + n - 1):
            tmp[y][x] = lock[y - (m - 1)][x - (m - 1)]

    return tmp

def solution(key, lock):
    n = len(lock)
    lock_count = 0
    for y in range(n):
        for x in range(n):
            if lock[y][x] == 0:
                lock_count += 1
    new_lock = generate_lock(key, lock)
    m = len(key)
    for _ in range(4):
        key = rotate(key)
        for start_y in range(n+m-1):
            for start_x in range(n+m-1):
                flag = True
                key_count = 0
                for ky in range(m):
                    if not flag:
                        break
                    for kx in range(m):
                        if key[ky][kx] + new_lock[start_y+ky][start_x+kx] == 2:
                            flag = False
                            break
                        
                        if m-1<= start_y+ky < m+n-1 and m-1 <= start_x + kx < m+n-1 and key[ky][kx] == 1:
                            key_count += 1
                
                if flag and key_count == lock_count:
                    return True
                
                    
    answer = False
    return answer


# 90도 회전
def rotate(key):
    tmp = [[0] * len(key) for _ in range(len(key))]

    for y in range(len(key)):
        for x in range(len(key)):
            tmp[x][len(key) - 1 - y] = key[y][x]

    return tmp

4. 가사 검색

문제 링크

• 프로그래머스 난이도 : 레벨 4

레벨 4인만큼 험악한 문제다. 당연히 정확성 통과하기는 쉬운데, 효율성 통과하는 것이 가장 어렵다.

가장 쉬운 방법은 트라이 사용하는 것 같다. 문자열 길이별로 딕셔너리에 트라이를 넣어주고, 역순 트라이와 정순 트라이를 넣어서, 뒤에 물음표가 있는 경우는 역순 트라이를 탐색하도록 했다.

물론, 한번에 풀진 못하고 공식 해설을 참고했다^^

class Node:
    def __init__(self, key):
        self.key = key
        self.children = {}  # 아래 노드들 연결
        self.count = 0 # 이 다음에 와일드 카드가 올 것을 대비해 여기 아래로 단어가 몇개 있는지 확인.

class Trie:
    def __init__(self):
        self.head = Node(None)
        self.count = 0

    def insert(self, string):
        current_node = self.head
        for char in string:
            current_node.count += 1
            if char not in current_node.children:   # abc가 들어왔을때, b가 child에 없으면 b를 아래에 넣는 것.
                current_node.children[char] = Node(char)
            current_node = current_node.children[char]

    def isin(self, string):
        current_node = self.head
        for char in string:
            if char not in current_node.children:
                return False
            current_node = current_node.children[char]
        return True

    def search(self, string):   # 있다는 걸 전제로 찾는다.
        current_node = self.head
        for char in string:
            current_node = current_node.children[char]
        return current_node.count

    def total(self):    # 이 길이의 트라이 총 문자열 개수
        current_node = self.head
        for key in current_node.children:
            print(key)
            self.count += current_node.children[key].count





def solution(words, queries):
    # 길이 별로 트라이를 어떠게 나눌것인가?
    front_trie = {}
    back_trie = {}
    for word in words:  # 트라이에 문자 삽입
        word_len = len(word)
        if word_len not in front_trie:
            front_trie[word_len] = Trie()
            back_trie[word_len] = Trie()
        front_trie[word_len].insert(word)
        back_trie[word_len].insert(word[::-1])

    # 길이별 총 문자열 수 업데이트
    for key in front_trie:
        front_trie[key].total()
        back_trie[key].total()

    answer = []
    for query in queries:
        query_len = len(query)
        if query_len not in front_trie:
            answer.append(0)
            continue
        if query[0] == '?': # 첫 문자가 와일드카드면
            reversed_query = query[::-1].split('?')[0]
            if reversed_query == '':   # 그냥 쿼리 전체가 와일드카드면
                answer.append(back_trie[query_len].count)
            else:
                if back_trie[query_len].isin(reversed_query):
                    answer.append(back_trie[query_len].search(reversed_query))
                else:
                    answer.append(0)

        elif query[-1] == '?':  # 마지막 문자가 와일드 카드면
            front_query = query.split('?')[0]
            if front_trie[query_len].isin(front_query):
                answer.append(front_trie[query_len].search(front_query))
            else:
                answer.append(0)
        else: # 그낭 full 문자면
            if front_trie[query_len].isin(query):
                answer.append(1)
            else:
                answer.append(0)
                
    return answer

5. 기둥과 보 설치

문제 링크

• 프로그래머스 난이도 : 레벨 3

이거 아마 엄청 끙끙댔는데, 갑자기 설치 조건을 따지는 것이 생각나서 깔끔하게 정리하니까 깔끔하게 풀린 문제다.

이렇게 조건을 분기하고 따져주면 된다.

기둥이 설치 가능한 경우

1. 내 아래 기둥이 있다.
2. 내 아래 보가 있다.
3. 내 아래가 바닥이다.

보가 설치 가능한 경우

1. 왼쪽 아래에 기둥이 있다.
2. 오른쪽 아래에 기둥이 있다.
3. 양 옆에 보가 있다.

이렇게 경우를 따져주고, 만약 삭제할 때는 그 녀석을 삭제했을 때 그 주위에 있는 기둥과 보가 설치가 되어 있을 수 있는지 이조건으로 확인해주고, 하나라도 불가능하면 삭제할 수 없는 것이다.

이 문제는 고민을 정말 많이해서 그런지 아직도 뿌듯한 감이 있다.

# 기둥이 설치 가능한 경우
# 1. 내 아래 기둥이 있다. 2. 내 아래 보가 있다. 3. 내 아래가 바닥이다.

def check_tower(bo,tower,x,y): # 이 (x,y) 좌표에 타워가 설 수 있는지.
    if y == 2:  # y = 2이면, 아래가 바닥이므로 참이다.
        return True

    if tower[y-1][x] == 1:  # 아래에 기둥이 있으므로 세울 수 있다.
        return True

    if bo[y][x] == 1 or bo[y][x-1] == 1:    #아래에 보가 있다.
        return True

    return False

# 보가 설치 가능한 경우
# 1. 왼쪽 아래에 기둥이 있다. 2. 오른쪽 아래에 기둥이 있다. 3. 양 옆에 보가 있다.
def check_bo(bo,tower,x,y): # 이 (x,y) 좌표에 보가 설 수 있는지.
    if tower[y-1][x] == 1:  # Case 1
        return True

    if tower[y-1][x+1] == 1:    # Case 2
        return True

    if bo[y][x-1] == 1 and bo[y][x+1] == 1: # Case 3
        return True

    return False

# 타워를 삭제할 수 있는 경우
# 1. 위에 타워가 있는 경우, 타워가 서있을 수 있어야 한다.
# 2. 위에 보가 있는 경우, 보가 서있을 수 있어야 한다.


def solution(n, build_frame):
    answer = []
    bo = [[0 for _ in range(n + 4)] for _ in range(n + 4)]
    tower = [[0 for _ in range(n + 4)] for _ in range(n + 4)]

    # 좌표를 2씩 더해서, -2 +2 연산을 자유롭게 하자.
    # 기둥의 경우를 y 좌표를 세로 직선으로 하자.
    # 보는 x좌표를 가로 직선으로 하자

    for frame in build_frame:
        x = frame[0] + 2
        y = frame[1] + 2
        a = frame[2]
        b = frame[3]

        if b == 1:  # 설치하는 경우
            if a == 0 and check_tower(bo,tower,x,y): #기둥인 경우
                tower[y][x] = 1
            elif a == 1 and check_bo(bo,tower,x,y): # 보인 경우
                bo[y][x] = 1
        else:   # 삭제하는 경우
            if a == 0:  # 타워을 삭제하는 경우
                tower[y][x] = 0 # 일단 삭제해본다.
                if tower[y+1][x] == 1 and not check_tower(bo,tower,x,y+1):  # 위에 타워가 있는 경우
                    tower[y][x] = 1 # 삭제 못함
                    continue

                if bo[y+1][x] == 1 and not check_bo(bo, tower, x, y+1):# 위에 보가 오른쪽으로 있는 경우
                    tower[y][x] = 1  # 삭제 못함
                    continue

                if bo[y+1][x-1] == 1 and not check_bo(bo, tower, x-1, y+1):  # 보가 왼쪽으로 있는 경우
                    tower[y][x] = 1  # 삭제 못함
                    continue
            elif a == 1:    #보를 삭제하는 경우
                bo[y][x] = 0    # 일단 삭제한다.
                if tower[y][x] == 1 and not check_tower(bo,tower,x, y): # 왼쪽 위에 타워가 있는 경우
                    bo[y][x] = 1
                    continue

                if tower[y][x+1] == 1 and not check_tower(bo,tower,x+1,y):  # 오른쪽 위에 타워가 있는 경우
                    bo[y][x] = 1
                    continue

                if bo[y][x-1] == 1 and not check_bo(bo,tower,x-1,y):
                    bo[y][x] = 1
                    continue

                if bo[y][x+1] == 1 and not check_bo(bo,tower,x+1,y):
                    bo[y][x] = 1
                    continue

    for x in range(2, len(bo)):
        for y in range(2, len(bo)):
            if tower[y][x] == 1:
                answer.append([x - 2, y - 2, 0])

            if bo[y][x] == 1:
                answer.append([x - 2, y - 2, 1])

    return answer

6. 외벽 점검

문제 링크

• 프로그래머스 난이도 : 레벨 3

이 문제는 외벽의 경우를 따지지 말고, 친구의 경우를 순열로 따지는 게 맞다.

나는 외벽의 경우를 계속 따져서, 시간 초과를 해결하지 못했다.

뭔가 어려운 것 같지 않은데, 어려운 문제다.

# 파이썬
from itertools import permutations
def solution(n, weak, dist):
    L = len(weak)
    cand = []
    weak_point = weak + [w+n for w in weak]  # 선형으로

    for i, start in enumerate(weak):
        for friends in permutations(dist):  # 순열 이용
            count = 1
            position = start
            # 친구 조합 배치
            for friend in friends:
                position += friend
                # 끝 포인트까지 도달 못했을 때
                if position < weak_point[i+L-1]:
                    count += 1  # 친구 더 투입
                    # 현재 위치보다 멀리 있는 취약지점 중 가장 가까운 위치로
                    position = [w for w in weak_point[i+1:i+L]
                                if w > position][0]
                else:  # 끝 포인트까지 도달
                    cand.append(count)
                    break

    return min(cand) if cand else -1