[level 2] 짝지어 제거하기 - 12973

문제 링크

성능 요약

메모리: 14.9 MB, 시간: 88.56 ms

구분

코딩테스트 연습 > 2017 팁스타운

채점결과

정확성: 60.2
효율성: 39.8
합계: 100.0 / 100.0

문제 설명

짝지어 제거하기는, 알파벳 소문자로 이루어진 문자열을 가지고 시작합니다. 먼저 문자열에서 같은 알파벳이 2개 붙어 있는 짝을 찾습니다. 그다음, 그 둘을 제거한 뒤, 앞뒤로 문자열을 이어 붙입니다. 이 과정을 반복해서 문자열을 모두 제거한다면 짝지어 제거하기가 종료됩니다. 문자열 S가 주어졌을 때, 짝지어 제거하기를 성공적으로 수행할 수 있는지 반환하는 함수를 완성해 주세요. 성공적으로 수행할 수 있으면 1을, 아닐 경우 0을 리턴해주면 됩니다.

예를 들어, 문자열 S = baabaa 라면

b aa baa → bb aa → aa →

의 순서로 문자열을 모두 제거할 수 있으므로 1을 반환합니다.

제한사항

• 문자열의 길이 : 1,000,000이하의 자연수
• 문자열은 모두 소문자로 이루어져 있습니다.

---

입출력 예

s	result
baabaa	1
cdcd	0

입출력 예 설명

입출력 예 #1
위의 예시와 같습니다.
입출력 예 #2
문자열이 남아있지만 짝지어 제거할 수 있는 문자열이 더 이상 존재하지 않기 때문에 0을 반환합니다.

※ 공지 - 2020년 6월 8일 테스트케이스가 추가되었습니다.

출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges

def solution(s):
    # def delete_alphas(alphabets):
    #     tmp_list = []
    #     i = 0
    #     while i < len(alphabets):
    #         if i == len(alphabets) - 1:
    #             tmp_list.append(i)
    #         else:
    #             if alphabets[i] == alphabets[i + 1]:                
    #                 i += 1
    #             else:
    #                 tmp_list.append(i)              
    #         i += 1
    #     if tmp_list:
    #         for i in range(len(tmp_list)):
    #             tmp_list[i] = alphabets[tmp_list[i]]
    #         return tmp_list
    #     else :
    #         return False
    # s = list(s)
    # answer = 1
    # while s:
    #     check_list = delete_alphas(s)
    #     if check_list == s:
    #         answer = 0
    #         break
    #     s = check_list  
    stack = []
    for letter in s:
        if stack:
            if stack[-1] == letter:
                stack.pop()
            else :
                stack.append(letter)
        else :
            stack.append(letter)
    if stack:
        answer = 0
    else :
        answer = 1
    

    # [실행] 버튼을 누르면 출력 값을 볼 수 있습니다.

    
    return answer

배울점

문제를 읽고 스택이 생각났지만, 자료구조 알고리즘 없이 구현이 가능할 듯하여, 그리디한 방법으로 처음에 구현해보았다. 문자열에 2연속 중복되지 않는 문자열의 인덱스를 기억해놨다가 모두 순회하면 해당 인덱스의 문자만 다시 출력하는 방식이었다. 이때, 아무런 변화가 없으면 False를 반환한다. 뒤에서 while 문을 돌릴때 필요하기 때문이다.

위처럼 구현할 경우, 당연하게도 시간 오류가 발생하였다. 결국 stack으로 중복된 알파벳이 들어오면 동시에 삭제하고 넘어가는 방식으로 하니 훨씬 간단하고 시간복자도 또한 크게 개선되었다. 오늘 알고리즘 문제로 왜 자료구조 알고리즘이 중요한지 다시금 깨닫게 되었다

---

[level 2] 피로도 - 87946

문제 링크

성능 요약

메모리: 10.2 MB, 시간: 0.14 ms

구분

코딩테스트 연습 > 완전탐색

채점결과

정확성: 100.0
합계: 100.0 / 100.0

문제 설명

XX게임에는 피로도 시스템(0 이상의 정수로 표현합니다)이 있으며, 일정 피로도를 사용해서 던전을 탐험할 수 있습니다. 이때, 각 던전마다 탐험을 시작하기 위해 필요한 "최소 필요 피로도"와 던전 탐험을 마쳤을 때 소모되는 "소모 피로도"가 있습니다. "최소 필요 피로도"는 해당 던전을 탐험하기 위해 가지고 있어야 하는 최소한의 피로도를 나타내며, "소모 피로도"는 던전을 탐험한 후 소모되는 피로도를 나타냅니다. 예를 들어 "최소 필요 피로도"가 80, "소모 피로도"가 20인 던전을 탐험하기 위해서는 유저의 현재 남은 피로도는 80 이상 이어야 하며, 던전을 탐험한 후에는 피로도 20이 소모됩니다.

이 게임에는 하루에 한 번씩 탐험할 수 있는 던전이 여러개 있는데, 한 유저가 오늘 이 던전들을 최대한 많이 탐험하려 합니다. 유저의 현재 피로도 k와 각 던전별 "최소 필요 피로도", "소모 피로도"가 담긴 2차원 배열 dungeons 가 매개변수로 주어질 때, 유저가 탐험할수 있는 최대 던전 수를 return 하도록 solution 함수를 완성해주세요.

제한사항

• k는 1 이상 5,000 이하인 자연수입니다.
• dungeons의 세로(행) 길이(즉, 던전의 개수)는 1 이상 8 이하입니다.
  • dungeons의 가로(열) 길이는 2 입니다.
  • dungeons의 각 행은 각 던전의 ["최소 필요 피로도", "소모 피로도"] 입니다.
  • "최소 필요 피로도"는 항상 "소모 피로도"보다 크거나 같습니다.
  • "최소 필요 피로도"와 "소모 피로도"는 1 이상 1,000 이하인 자연수입니다.
  • 서로 다른 던전의 ["최소 필요 피로도", "소모 피로도"]가 서로 같을 수 있습니다.

입출력 예

k	dungeons	result
80	[[80,20],[50,40],[30,10]]	3

입출력 예 설명

현재 피로도는 80입니다.

만약, 첫 번째 → 두 번째 → 세 번째 던전 순서로 탐험한다면

• 현재 피로도는 80이며, 첫 번째 던전을 돌기위해 필요한 "최소 필요 피로도" 또한 80이므로, 첫 번째 던전을 탐험할 수 있습니다. 첫 번째 던전의 "소모 피로도"는 20이므로, 던전을 탐험한 후 남은 피로도는 60입니다.
• 남은 피로도는 60이며, 두 번째 던전을 돌기위해 필요한 "최소 필요 피로도"는 50이므로, 두 번째 던전을 탐험할 수 있습니다. 두 번째 던전의 "소모 피로도"는 40이므로, 던전을 탐험한 후 남은 피로도는 20입니다.
• 남은 피로도는 20이며, 세 번째 던전을 돌기위해 필요한 "최소 필요 피로도"는 30입니다. 따라서 세 번째 던전은 탐험할 수 없습니다.

만약, 첫 번째 → 세 번째 → 두 번째 던전 순서로 탐험한다면

• 현재 피로도는 80이며, 첫 번째 던전을 돌기위해 필요한 "최소 필요 피로도" 또한 80이므로, 첫 번째 던전을 탐험할 수 있습니다. 첫 번째 던전의 "소모 피로도"는 20이므로, 던전을 탐험한 후 남은 피로도는 60입니다.
• 남은 피로도는 60이며, 세 번째 던전을 돌기위해 필요한 "최소 필요 피로도"는 30이므로, 세 번째 던전을 탐험할 수 있습니다. 세 번째 던전의 "소모 피로도"는 10이므로, 던전을 탐험한 후 남은 피로도는 50입니다.
• 남은 피로도는 50이며, 두 번째 던전을 돌기위해 필요한 "최소 필요 피로도"는 50이므로, 두 번째 던전을 탐험할 수 있습니다. 두 번째 던전의 "소모 피로도"는 40이므로, 던전을 탐험한 후 남은 피로도는 10입니다.

따라서 이 경우 세 던전을 모두 탐험할 수 있으며, 유저가 탐험할 수 있는 최대 던전 수는 3입니다.

---

※ 공지 - 2022년 2월 25일 테스트케이스가 추가되었습니다.

출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges

def solution(k, dungeons):
    visited = [0]*len(dungeons)
    global max_cnt
    max_cnt = 0   
    def check(visited, k):
        for i in range(len(visited)):
            if not visited[i]:
                if k >= dungeons[i][0]:
                    return True
        return False
                
    def dfs(k, visited, cnt):
        global max_cnt
        # 모두 방문했을 경우,
        if sum(visited) == len(dungeons):
                if max_cnt < cnt:
                    max_cnt = cnt
                    return
        # 남은 피로도로 갈 수 잇는 던전 체크 
        if not check(visited, k):
            if max_cnt < cnt:
                    max_cnt = cnt
                    return           
        
        # 모두 방문하지 않았을 경우, 순회하면서 방문하지 않은 곳
        for i in range(len(dungeons)):                        
            if not visited[i]:              
                if k >= dungeons[i][0]:
                    k -= dungeons[i][1]
                    cnt += 1
                    visited[i] = 1
                    # print(visited)
                    dfs(k, visited, cnt)
                    k += dungeons[i][1]
                    cnt -= 1
                    visited[i] = 0 
                    
    dfs(k, visited, 0) 
    # print(max_cnt)
    # print(visited)
     
    answer = max_cnt
    return answer

배울점

간단한 DFS문제이다. 해당 리스트들의 던전을 방문하는 모두 경우의 수를 탐색하면서 가장 많이 탐색한 횟수를 저장해서 출력하면 된다. 다른 풀이들을 보니 dfs로는 아무도 안 푼거 같은데 왜 그런지는 모르겠다. 무슨 q안에 방문처리를 넣는거 같던데 굳이 큐로 억지로 풀어야하나 싶었다. 시간 복자도의 유의미한 차이가 있을 법도 하다.

위의 if처리에서 깜빡하고 if문 하나를 설정을 안해서 30분동안 헛짓거리를 했다. 화가 났다.