푼 문제 복기하기

1. 오픈채팅방

• 정답률 : 59.91%
• 프로그래머스 난이도 : 레벨 2

파이썬은 딕셔너리, 나머지 언어는 맵을 이용하면 쉽게 풀 수 있는 문제다.
유저 아이디별로 닉네임을 매핑 해놓고, 그걸 바탕으로 마지막에 출력하면 된다.

이건 푸는데 5분 걸렸다.

def solution(record):
    answer = []
    userdic = {}  # {userid : name} 의 딕셔너리
    for rec in record:
        inp = rec.split(' ')
        op = inp[0]
        uid = inp[1]
        if op == "Enter":
            nickname = inp[2]
            userdic[uid] = nickname
        elif op == "Change":
            nickname = inp[2]
            userdic[uid] = nickname

    for rec in record:
        inp = rec.split(' ')
        op = inp[0]
        uid = inp[1]
        if op == "Enter":
            log = userdic[uid] + "님이 들어왔습니다."
            answer.append(log)
        elif op == "Leave":
            log = userdic[uid] + "님이 나갔습니다."
            answer.append(log)

    return answer

2. 실패율

• 정답률 : 55.57%
• 프로그래머스 난이도 : 레벨 1

전혀 레벨 1 같지 않은 레벨 1 문제.. 레벨 1 치고는 어려운 것 같다.

실패율을 구할 때 스테이지에 도달한 플레이어 수랑 도달했으나 아직 클리어하지 못한 플레이어의 수를 각각 어떻게 저장해서 계산할지가 핵심인 문제다.

나는 클리어하지 못한 플레이어의 수를 딕셔너리에 저장해놓고 계산을 하는 식으로 했다.

그리고 실패율이 같은것이 있으면 역순으로 집어 넣어야 해서 pop을 이용했다.

야매로 풀려다가 실패해서 30분 정도 걸렸다. 그냥 정직하게 풀자...

def solution(N, stages):
    answer = []
    dic = {}
    for s in stages:
        if s in dic:
            dic[s] += 1
        else:
            dic[s] = 1

    percents = []
    app = len(stages)
    for i in range(1, N + 1):  # 1~N Stage
        if i in dic:
            unclear = dic[i]
            percent = unclear / app
            app -= unclear
            percents.append((percent, i))
        else:
            percents.append((0, i))
    percents.sort(reverse=True)

    same = []
    for i in range(len(percents)):
        if i == 0:
            same.append(percents[i][1])
            continue

        if percents[i][0] == percents[i - 1][0]:  # 이전꺼랑 확률이 같으면
            same.append(percents[i][1])
        else:  # 다르면
            # 같은 것이 있었을 때, 확률이 같은 것을 역순으로 집어넣기
            while len(same) != 0:
                val = same.pop()
                answer.append(val)
            same.append(percents[i][1])

    while len(same) != 0:
        val = same.pop()
        answer.append(val)

    return answer

3. 후보키

• 정답률 : 16.09%
• 프로그래머스 난이도 : 레벨 2

여기서부터 급격하게 까다로워졌다. 후보키의 정의를 이용하여 후보 키의 최대 개수를 구하는 문제다.

후보키 경우를 완전 탐색하면 되는 문제인데, 후보키 경우를 어떻게 세울 것인가가 가장 큰 고민이다.
모든 부분집합을 만드는 방법에는, Python의 itertools.combination 을 이용하는 방법과 bit mask가 있는데, 나는 전자를 이용했다. 하지만 지금 생각해보면 후자가 훨씬 간단할 듯 하다.

그리고 후보키 인지를 판별하는 것은, 그냥 string으로 ,를 이용해서 이어 붙여셔 딕셔너리에 때려 넣었다.

콤마로 이어넣은 이유는 만약에 ABC 랑 DE 라는 키쌍이 하나 있고 AB랑 CDE가 있을 때 이어붙이면 이거는 같은걸로 판별이 되버리기 때문에, 콤마로 구분해 주었다.

한 시간 정도 걸린 것 같다.

import itertools

def solution(relation):
    col_len = len(relation[0])  # 컬럼 길이
    arrs = [i for i in range(col_len)]  # 0~n-1
    combs = []
    answers = []
    for i in range(1, col_len + 1):
        comb_list = list(itertools.combinations(arrs, i))
        if not comb_list:
            continue
        combs.append(comb_list)

    for comb in combs:  # 조합에 접근하려면 삼중 for문 실환가..
        for idx in comb:  # (1,2), (1,2,3) # col 경우별로 따지기
            dic = {}  # 후보 키 따지기 위한 딕셔너리
            is_ck = True  # 후보키인가

            for rel in relation:  # row 별로
                string = ""
                for i in idx:
                    string += rel[i] + ","

                if string in dic or string == "":  # 중복 식별
                    is_ck = False
                    break
                else:
                    dic[string] = 1

            if is_ck:  # 일단 유일하게 구별이 되는 경우
                answer_string = ""

                for i in idx:
                    answer_string += str(i)

                is_answer = False

                if len(answers) == 0:  # 비어 있는 경우
                    is_answer = True
                else:
                    for string in answers:  # 더 적게 들어간 것이랑 비교해서 최소성 판단
                        is_answer = False

                        for i in range(len(string)):
                            if string[i] not in answer_string:
                                is_answer = True
                                break

                        if not is_answer:
                            break

                if is_answer:
                    answers.append(answer_string)

    return len(answers)

4. 무지의 먹방 라이브

• 정답률 : 정확성 42.08% / 효율성 5.52%
• 프로그래머스 난이도 : 레벨 4

갑자기 레벨 4문제가..?
실제로 코딩테스트를 참가한다면 이런 문제는 정확성 풀고 시간 줄일 방법이 생각이 나질 않는 다면 뒤에 문제를 푸는 게 맞는 것 같다.

이런 문제 정확성 통과 코드는 5분컷이 난다. 하지만 효율성이 문제일 뿐...

나는 링크드 리스트까지 써서 해봤는데 시간을 못줄여서 포기했다. 결국 해설을 참고했는데, 시간을 하나씩 따지는 게 아니고 이전 시간이랑 비교해서 한번에 쭉 쭉 지워 나가는 방식으로 하는 것이다.

지워 나가다가 k보다 커지게 되면 나머지를 이용해 인덱스를 구하는데, 이 때 인덱스를 다시 원래 음식의 번호 순서대로 재정렬 하는 게 굉장히 중요하다. 나는 이 점을 캐치 못해서 상당한 시간이 소요되었다.

틀린 코드랑 맞은 코드 한번에 첨부해야지.

# 1차 시도 당연히 시간초과 날것 ( 정확성은 통과할 것 )
## 이 코드는 5분컷,, 시간 초과 어떻게 해결할까?

def solution(food_times, k):
    time = 0
    idx = 0
    answer = 0
    dic = {}
    while True:
        if idx == len(food_times):  # 끝에 도달
            idx = 0
            continue

        if food_times[idx] == 0:
            if len(dic) == len(food_times):
                return -1
            idx += 1
            dic[idx] = 1
            continue

        if time == k:
            answer = idx + 1
            break

        food_times[idx] -= 1
        time += 1
        idx += 1

    return answer

# 2차 시도
### 링크드 리스트로 2차 시도 해봤는데도 시간 줄이기 실패.

class Node:
    def __init__(self, time, idx):
        self.time = time
        self.idx = idx
        self.next = None
        self.prev = None



class LinkedList:
    def __init__(self, time, idx):
        node = Node(time, idx)
        self.head = node
        self.cur = node

    def insert(self, time, idx): # 링크드 리스트 끝에 추가
        current_node = self.head
        while current_node.next is not None:
            current_node = current_node.next
        node = Node(time,idx)
        current_node.next = node
        node.prev = current_node

def solution(food_times, k):
    linked_list = LinkedList(food_times[0], 0)
    for i in range(1,len(food_times)):
        linked_list.insert(food_times[i],i)

    cur = linked_list.head
    while k>0:
        cur.time -= 1
        k -= 1

        if cur.time == 0:
            if cur == linked_list.head:
                if cur.next is None:    # 더 섭취할 음식이 없음
                    return -1
                linked_list.head = cur.next
            else:
                prev_node = cur.prev
                if cur.next is not None:    # 삭제 하는 과정
                    next_node = cur.next
                    prev_node.next = next_node
                    next_node.prev = prev_node
                else:
                    prev_node.next = None

        if cur.next is None:    # 다음 리스트로
            cur = linked_list.head
        else:
            cur = cur.next

    return cur.idx + 1

# 이분 탐색으로 풀어야 할 것 같은 느낌
# 3트
## 해설 보고 풀었다.
## 정렬 시켜서 묶어서 뺴는 방식으로 카운트 가짓 수를 크게 줄이는게 방법이다.
## 마지막에 인덱스 정렬하는 거를 캐치 못해서 오래걸렸다.

def solution(food_times, k):
    q = []
    for i in range(len(food_times)):
        q.append((food_times[i],i))
    q.sort()
    food_times.sort()
    times = list(set(food_times))
    times.sort()
    idx = 0
    qlen = len(q)

    for i in range(len(times)):
        while times[i] > q[idx][0]:
            idx += 1

        if i == 0:
            minus_time = times[0]
        else:
            minus_time = times[i] - times[i-1]

        k -= minus_time * (qlen - idx)   # 한 바퀴 쭉 먹어준다.
        if k < 0:   #만약 한 바퀴 쭉 돌았을 때 끝났으면,
            k += minus_time * (qlen - idx)
            idx_arr = []
            for j in range(idx,len(q)):
                idx_arr.append(q[j][1])
            idx_arr.sort()
            ans_idx = k % (qlen - idx)
            return idx_arr[ans_idx] + 1

    return -1

5. 길 찾기 게임

• 정답률 : 7.40%
• 프로그래머스 난이도 : 레벨 3

이 문제를 보고 반성을 정말 많이 했다. 코딩테스트는 클래스 구현 안하고 풀 수 있다는 선입견에 갇혀 있었는데, 절대 아니다. 그냥 트리 그려서 넣으면 되는 아주 단순한 문제인데, 파이썬으로 트리를 처음 구현해보는 거여서 너무 당황해서 못풀었다.(검색을 안하고 하려하니..)

그래서 이걸 기점으로 클래스 선언해서 푸는 방법을 굉장히 많이 연습중이다.

방법은 그냥 y값으로 정렬하면 위에서부터 내려오는 거니까 x값만 신경 써서 삽입해주고 preorder, postorder은 아주 단순하므로 그냥 하면 되는 것!

5시간 재고 풀었을 때, 시간이 없어서 이 문제를 풀지 못했다.

아 그리고, 런타임 에러 난다면 파이썬의 재귀 제한을 한번 확인해 보는 것이 좋을 것 같다. 이 문제도 recursionlimit 때문에 런타임 에러가 나서 설정해주니 해결됐다.

# 6,7번 런타임 에러? -> 재귀 한도 문제였다.
# 이건 시간안에 못풀고 번외로 푼 것.
import sys

sys.setrecursionlimit(20000)
pre_nodes = []
post_nodes = []


class Node:
    def __init__(self, x, idx):
        self.left = None
        self.right = None
        self.x = x
        self.idx = idx


class Tree:
    def __init__(self, root):
        self.root_node = root
        self.current_node = None

    def insert(self, x, idx):
        self.current_node = self.root_node
        while True:
            if self.current_node.x < x:  # x값이 더 크니까 오른쪽으로 간다.
                if self.current_node.right is not None:
                    self.current_node = self.current_node.right
                else:
                    self.current_node.right = Node(x, idx)
                    break
            else:  # 왼쪽으로 간다.
                if self.current_node.left is not None:
                    self.current_node = self.current_node.left
                else:
                    self.current_node.left = Node(x, idx)
                    break

    def preOrder(self, node):
        pre_nodes.append(node.idx)
        if node.left is not None:
            self.preOrder(node.left)
        if node.right is not None:
            self.preOrder(node.right)

    def postOrder(self, node):
        if node.left is not None:
            self.postOrder(node.left)
        if node.right is not None:
            self.postOrder(node.right)
        post_nodes.append(node.idx)


def solution(nodeinfo):
    # 길이가 1인 경우
    if len(nodeinfo) == 1:
        return [[1], [1]]

    nodes = []
    for i in range(len(nodeinfo)):
        x = nodeinfo[i][0]
        y = nodeinfo[i][1]
        nodes.append((y, x, i + 1))

    nodes.sort(reverse=True)  # y값 큰 순으로 정렬.

    tree = Tree(Node(nodes[0][1], nodes[0][2]))

    for i in range(1, len(nodes)):
        tree.insert(nodes[i][1], nodes[i][2])

    answer = []

    tree.preOrder(tree.root_node)
    tree.postOrder(tree.root_node)
    answer.append(pre_nodes)
    answer.append(post_nodes)
    return answer

6. 매칭 점수

• 정답률 : 6.12%
• 프로그래머스 난이도 : 레벨 3

진짜 거지같은 문제.

그냥 정규 표현식 쓰면 간단하게 풀리는데, 안써보고 풀겠다고 이악물고 풀다가 10번 테케 하나 하루종일 못잡아서 그냥 포기하고 정규 표현식 썼다.

뒤에도 보니까 정규 표현식 쓸만한 문제가 자주 보이던데, 정규 표현식 연습하는 것이 훨씬 좋을 것 같다.

문자열 파싱만 잘하면 나머지는 단순한 계산 문제였다. 문자열 파싱이 속을 썩여서 그렇지..

실제로 해설에도 문자열 파싱 능력을 요구하는 문제라고 써있다.
테케를 통과하지 못한 코드도 첨부해보았다. 분명히 공백 기준으로 파싱해서 아무 문제가 없어야 하는데..후..

import re
def solution(word, pages):
    answer = 0
    link_counts = []  # 외부 링크 수
    normal_counts = []  # 기본 점수
    link_idx = {}  # 링크 별 인덱스 값
    idx_link = {}
    linkToLink = [[] for _ in range(21)]
    word = word.lower()  # 소문자로만 비교하자.

    # 기본 점수
    for k in range(len(pages)):
        page = pages[k]
        word_len = len(word)
        score = 0

        for i in range(len(page) - word_len):
            if page[i].lower() == word[0]:  # 첫글자가 같을 때,

                if 'a' <= page[i - 1].lower() <= 'z':  # 앞에 연속된 문자가 있으면
                    continue

                is_same = True
                for j in range(word_len):
                    if word[j] != page[i + j].lower():
                        is_same = False
                        break

                if is_same:
                    if 'a' <= page[i + word_len].lower() <= 'z':  # 뒤에 연속된 문자가 있으면
                        continue
                    else:
                        score += 1  # 기본 점수 + 1
                        continue

        normal_counts.append(score)

    for k in range(len(pages)):
        page = pages[k]
        real_link = re.search(r'(<meta property.+content=")(https://.*)"/>', page).group(2)  # 현재 url검색
        link_idx[k] = real_link  # 링크 - 인덱스, 인덱스 - 링크 둘 다 저장
        idx_link[real_link] = k

    # 링크 점수 구하기
    for k in range(len(pages)):
        page = pages[k]
        real_link = re.findall(r'<a href="https://\S*">', page)  # 외부 링크 url 전부 검색
        link_counts.append(len(real_link))
        for link in real_link:
            l = link[9:-2]
            print(l)
            if l in idx_link:
                idx = idx_link[l]  # 연결된 링크의 인덱스 번호
                linkToLink[idx].append(k)

    scores = []
    for i in range(len(pages)):
        link_score = 0
        if len(linkToLink[i]) != 0:
            for idx in linkToLink[i]:  # 이 링크로 이어지는 링크들
                link_score += normal_counts[idx] / link_counts[idx]

        scores.append(link_score + normal_counts[i])

    max_score = max(scores)

    for i in range(len(pages)):
        if scores[i] == max_score:
            answer = i
            break

    return answer

"""
대체 왜 10번 테케만 통과를 못하는지 모르겠다.
def solution(word, pages):
    answer = 0
    link_counts = []  # 외부 링크 수
    normal_counts = []  # 기본 점수
    link_idx = {}  # 링크 별 인덱스 값
    idx_link = {}
    linkToLink = [[] for _ in range(21)]
    word = word.lower()  # 소문자로만 비교하자.

    # 기본 점수
    for k in range(len(pages)):
        page = pages[k]
        word_len = len(word)
        is_tag = False
        score = 0

        for i in range(len(page) - word_len):
            if page[i] == '<':  # <~~~~>는 태그 안에 있는 글이다.
                is_tag = True

            if page[i] == '>':
                is_tag = False

            if not is_tag:  # 태크 안에 있는게 아니면
                if page[i].lower() == word[0]:  # 첫글자가 같을 때,
                    if 'a' <= page[i - 1].lower() <= 'z':  # 앞에 연속된 문자가 있으면
                        continue

                    is_same = True
                    for j in range(word_len):
                        if word[j] != page[i + j].lower():
                            is_same = False
                            break

                    if is_same:
                        if 'a' <= page[i + word_len].lower() <= 'z':  # 뒤에 연속된 문자가 있으면
                            continue
                        else:
                            score += 1  # 기본 점수 + 1
                            continue

        normal_counts.append(score)

    for k in range(len(pages)):
        page = pages[k]
        string = page.split(' ')  # 공백 기준으로 나누기
        find_url = False  # 처음에 메타값에서 찾아야 한다.

        # 이 웹페이지 링크 구하기
        for p in string:
            if find_url:
                break

            if "content" in p and not find_url:
                new_link = p[9:]
                # 링크 구하기
                for i in range(len(new_link) - 2):
                    if new_link[i] == '\"' and new_link[i + 1] == "/" and new_link[i + 2] == ">":
                        real_link = new_link[:i]

                        if real_link in idx_link:  # 이거 추가하니까 9번 통과
                            continue

                        link_idx[k] = real_link  # 링크 - 인덱스, 인덱스 - 링크 둘 다 저장
                        idx_link[real_link] = k
                        find_url = True
                        break

    # 링크 점수 구하기
    for k in range(len(pages)):
        page = pages[k]
        link_count = 0  # 외부 링크 수
        string = page.split(' ')  # 공백 기준으로 나누기
        for p in string:
            if "href" in p:
                new_link = p[6:]
                # 링크 연결 시켜주기
                for i in range(len(new_link)):
                    if new_link[i] == '\"' and new_link[i + 1] == ">":
                        real_link = new_link[:i] # 이 웹페이지에 걸린 링크
                        link_count += 1
                        if real_link not in idx_link:
                            break
                        idx = idx_link[real_link]  # 연결된 링크의 인덱스 번호
                        if k in linkToLink[idx]:
                            break
                        linkToLink[idx].append(k)

        link_counts.append(link_count)  # 인덱스 별로 링크 카운트

    scores = []
    for i in range(len(pages)):
        link_score = 0
        if len(linkToLink[i]) != 0:
            for idx in linkToLink[i]:  # 이 링크로 이어지는 링크들
                link_score += normal_counts[idx] / link_counts[idx]

        scores.append(link_score + normal_counts[i])

    max_score = max(scores)

    for i in range(len(pages)):
        if scores[i] == max_score:
            answer = i
            break

    print(scores)
    return answer
"""