Sad Puppy 3 'CodingTest/solved - Python' 카테고리의 글 목록 (7 Page) :: 개발자 아지트

https://school.programmers.co.kr/learn/courses/30/lessons/131127#

 

프로그래머스

코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.

programmers.co.kr

문제설명

XYZ 마트는 일정한 금액을 지불하면 10일 동안 회원 자격을 부여합니다. XYZ 마트에서는 회원을 대상으로 매일 한 가지 제품을 할인하는 행사를 합니다. 할인하는 제품은 하루에 하나씩만 구매할 수 있습니다. 알뜰한 정현이는 자신이 원하는 제품과 수량이 할인하는 날짜와 10일 연속으로 일치할 경우에 맞춰서 회원가입을 하려 합니다.

 

예를 들어, 정현이가 원하는 제품이 바나나 3, 사과 2, 2, 돼지고기 2, 냄비 1개이며, XYZ 마트에서 14일간 회원을 대상으로 할인하는 제품이 날짜 순서대로 치킨, 사과, 사과, 바나나, , 사과, 돼지고기, 바나나, 돼지고기, , 냄비, 바나나, 사과, 바나나인 경우에 대해 알아봅시다. 첫째 날부터 열흘 간에는 냄비가 할인하지 않기 때문에 첫째 날에는 회원가입을 하지 않습니다. 둘째 날부터 열흘 간에는 바나나를 원하는 만큼 할인구매할 수 없기 때문에 둘째 날에도 회원가입을 하지 않습니다. 셋째 날, 넷째 날, 다섯째 날부터 각각 열흘은 원하는 제품과 수량이 일치하기 때문에 셋 중 하루에 회원가입을 하려 합니다.

 

정현이가 원하는 제품을 나타내는 문자열 배열 want와 정현이가 원하는 제품의 수량을 나타내는 정수 배열 number, XYZ 마트에서 할인하는 제품을 나타내는 문자열 배열 discount가 주어졌을 때, 회원등록시 정현이가 원하는 제품을 모두 할인 받을 수 있는 회원등록 날짜의 총 일수를 return 하는 solution 함수를 완성하시오. 가능한 날이 없으면 0 return 합니다.

 

문제 해결 방법

해시를 통해 문제를 해결함

 

코드 구현

def solution(want, number, discount):     
    hyeon = { }
    cnt = 0
    
    for i in want:
        if i in hyeon:
            continue
        else:
            hyeon[i] = number[cnt]; 
            cnt+=1
    
    total = len(discount)
    if total <= 10:
        cnt = 1
    else:
        cnt = total % 10
        cnt += 1
        if total>=20:
            cnt += ((total//10)-1)*10
    
    check = 0
    day = 0
    
    while(1):
        if cnt == 0:
            break
        
        ndiscount = []
        for i in range(check, check + 10):
            ndiscount.append(discount[i])
        
        disHash = {}
        
        for i in ndiscount:
            if i in disHash:
                disHash[i] += 1
            else:
                disHash[i] = 1
                
        if disHash == hyeon:
            day+=1
        
        cnt-=1
        check+=1
        
    return day

 

시간/공간 복잡도

O(N^2)

 

최적화 및 개선

따로 하지않음

 

어려웠던 점

discount의 원소들이 20개 이상 넘어가는 경우를 헤아리지 못했음 

https://school.programmers.co.kr/learn/courses/30/lessons/42576

 

프로그래머스

코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.

programmers.co.kr

문제설명

수많은 마라톤 선수들이 마라톤에 참여하였습니다. 단 한 명의 선수를 제외하고는 모든 선수가 마라톤을 완주하였습니다.

 

마라톤에 참여한 선수들의 이름이 담긴 배열 participant와 완주한 선수들의 이름이 담긴 배열 completion이 주어질 때, 완주하지 못한 선수의 이름을 return 하도록 solution 함수를 작성해주세요.

문제 해결 방법

해시는 딕셔너리로 구현하였다. 

코드 구현

def solution(participant, completion):
    # 참가 participant, 완주 completion
    p = { }
    
    for i in participant:
        if i in p: 
            p[i] += 1
        else:
            p[i] = 1
    
    for i in completion:
        if i in p:
            p[i] -= 1

    for key in p.keys():
        if p[key]> 0:
            return key

 

시간/공간 복잡도

O(N)

최적화 및 개선

따로 하지 않음

 

어려웠던 점

참 순전히 딕셔너리 제대로 쓸줄 몰라서 못푼 문제였다.. 

남의 코드를 보는것은 내 기준에서 80% 이상 도움되는 일이다.. 그동안 왜 고집부리면서 안봤는지..

지난 세월이 아쉽구만.. 

https://school.programmers.co.kr/learn/courses/30/lessons/159994

 

프로그래머스

코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.

programmers.co.kr

 

문제설명

코니는 영어 단어가 적힌 카드 뭉치 두 개를 선물로 받았습니다. 코니는 다음과 같은 규칙으로 카드에 적힌 단어들을 사용해 원하는 순서의 단어 배열을 만들 수 있는지 알고 싶습니다.

 

원하는 카드 뭉치에서 카드를 순서대로 한 장씩 사용합니다.

한 번 사용한 카드는 다시 사용할 수 없습니다.

카드를 사용하지 않고 다음 카드로 넘어갈 수 없습니다.

기존에 주어진 카드 뭉치의 단어 순서는 바꿀 수 없습니다.

 

예를 들어 첫 번째 카드 뭉치에 순서대로 ["i", "drink", "water"], 두 번째 카드 뭉치에 순서대로 ["want", "to"]가 적혀있을 때 ["i", "want", "to", "drink", "water"] 순서의 단어 배열을 만들려고 한다면 첫 번째 카드 뭉치에서 "i"를 사용한 후 두 번째 카드 뭉치에서 "want" "to"를 사용하고 첫 번째 카드뭉치에 "drink" "water"를 차례대로 사용하면 원하는 순서의 단어 배열을 만들 수 있습니다.

 

문자열로 이루어진 배열 cards1, cards2와 원하는 단어 배열 goal이 매개변수로 주어질 때, cards1 cards2에 적힌 단어들로 goal를 만들 있다면 "Yes", 만들 수 없다면 "No" return하는 solution 함수를 완성해주세요.


문제 해결 방법

덱을 활용하여 문제를 해결함 


코드 구현

from collections import deque

def solution(cards1, cards2, goal):
    answer = ''
    
    cards1Q = deque()
    cards2Q = deque()
    
    for i in range(len(cards1)):
        cards1Q.append(cards1[i])
        
    for i in range(len(cards2)):
        cards2Q.append(cards2[i])
        
    cnt = 0
    check = 0
        
    while(1):
        check = 0
        
        if cnt >= len(goal):
            return "Yes"

        if len(cards1Q) != 0:
            if goal[cnt] == cards1Q[0]:
                cnt+=1
                check +=1
                cards1Q.popleft()

        if len(cards2Q) != 0:
            if goal[cnt] == cards2Q[0]:
                cnt+=1
                check +=1
                cards2Q.popleft()
                
        if check == 0:
            return "No"

    return answer

 

시간/공간 복잡도

O(N)

최적화 및 개선

따로 하지 않음

어려웠던 점

없음

https://school.programmers.co.kr/learn/courses/30/lessons/42586

 

프로그래머스

코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.

programmers.co.kr

문제설명

프로그래머스 팀에서는 기능 개선 작업을 수행 중입니다. 각 기능은 진도가 100%일 때 서비스에 반영할 수 있습니다.

 

, 각 기능의 개발속도는 모두 다르기 때문에 뒤에 있는 기능이 앞에 있는 기능보다 먼저 개발될 수 있고, 이때 뒤에 있는 기능은 앞에 있는 기능이 배포될 때 함께 배포됩니다.

 

먼저 배포되어야 하는 순서대로 작업의 진도가 적힌 정수 배열 progresses와 각 작업의 개발 속도가 적힌 정수 배열 speeds가 주어질 때 각 배포마다 몇 개의 기능이 배포되는지를 return 하도록 solution 함수를 완성하세요.

 

*제한 사항

 

작업의 개수(progresses, speeds배열의 길이) 100개 이하입니다.

작업 진도는 100 미만의 자연수입니다.

작업 속도는 100 이하의 자연수입니다.

배포는 하루에 한 번만 할 수 있으며, 하루의 끝에 이루어진다고 가정합니다. 예를 들어 진도율이 95%인 작업의 개발 속도가 하루에 4%라면 배포는 2일 뒤에 이루어집니다.

문제 해결 방법

 

큐 구현을 위해 collections의 deque를 이용함

코드 구현

from collections import deque

def solution(progresses, speeds):
    answer = []
    
    progressesQ = deque()
    speedsQ = deque()

    cnt = 0
    
    for i in range(len(progresses)):
        progressesQ.append(progresses[i])
        speedsQ.append(speeds[i])

    while(1):
        
        if progressesQ[0]>=100:
            for i in range(len(progressesQ)):
                if progressesQ[i] >= 100:
                    cnt+=1
                else:
                    break
            
            answer.append(cnt)
            for i in range(cnt):
                progressesQ.popleft()
                speedsQ.popleft()
            cnt = 0
        
        if(len(progressesQ)==0):
            break

        
        for i in range(len(progressesQ)):
            progressesQ[i] += speedsQ[i]
    
    return answer

 

시간/공간 복잡도

O(N^2)


최적화 및 개선

파이썬 list의 pop()대신 deque의 popleft()를 사용함 


어려웠던 점

없음

https://school.programmers.co.kr/learn/courses/30/lessons/64061

 

프로그래머스

코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.

programmers.co.kr

문제설명

게임개발자인 "죠르디"는 크레인 인형뽑기 기계를 모바일 게임으로 만들려고 합니다.

"죠르디"는 게임의 재미를 높이기 위해 화면 구성과 규칙을 다음과 같이 게임 로직에 반영하려고 합니다.

게임 화면은 "1 x 1" 크기의 칸들로 이루어진 "N x N" 크기의 정사각 격자이며 위쪽에는 크레인이 있고 오른쪽에는 바구니가 있습니다. (위 그림은 "5 x 5" 크기의 예시입니다). 각 격자 칸에는 다양한 인형이 들어 있으며 인형이 없는 칸은 빈칸입니다. 모든 인형은 "1 x 1" 크기의 격자 한 칸을 차지하며 격자의 가장 아래 칸부터 차곡차곡 쌓여 있습니다. 게임 사용자는 크레인을 좌우로 움직여서 멈춘 위치에서 가장 위에 있는 인형을 집어 올릴 수 있습니다. 집어 올린 인형은 바구니에 쌓이게 되는 데, 이때 바구니의 가장 아래 칸부터 인형이 순서대로 쌓이게 됩니다. 다음 그림은 [1, 5, 3] 위치에서 순서대로 인형을 집어 올려 바구니에 담은 모습입니다.

만약 같은 모양의 인형 두 개가 바구니에 연속해서 쌓이게 되면 두 인형은 터뜨려지면서 바구니에서 사라지게 됩니다. 위 상태에서 이어서 [5] 위치에서 인형을 집어 바구니에 쌓으면 같은 모양 인형 두 개가 없어집니다.

크레인 작동 시 인형이 집어지지 않는 경우는 없으나 만약 인형이 없는 곳에서 크레인을 작동시키는 경우에는 아무런 일도 일어나지 않습니다. 또한 바구니는 모든 인형이 들어갈 수 있을 만큼 충분히 크다고 가정합니다. (그림에서는 화면표시 제약으로 5칸만으로 표현하였음)

 

게임 화면의 격자의 상태가 담긴 2차원 배열 board와 인형을 집기 위해 크레인을 작동시킨 위치가 담긴 배열 moves가 매개변수로 주어질 때, 크레인을 모두 작동시킨 후 터트려져 사라진 인형의 개수를 return 하도록 solution 함수를 완성해주세요.

 

[제한사항]

board 배열은 2차원 배열로 크기는 "5 x 5" 이상 "30 x 30" 이하입니다.

board의 각 칸에는 0 이상 100 이하인 정수가 담겨있습니다.

  • 0은 빈 칸을 나타냅니다.
  • 1 ~ 100의 각 숫자는 각기 다른 인형의 모양을 의미하며 같은 숫자는 같은 모양의 인형을 나타냅니다.

moves 배열의 크기는 1 이상 1,000 이하입니다.

moves 배열 각 원소들의 값은 1 이상이며 board 배열의 가로 크기 이하인 자연수입니다.

 

입출력 예

board                                                                                  moves                result

[[0,0,0,0,0],[0,0,1,0,3],[0,2,5,0,1],[4,2,4,4,2],[3,5,1,3,1]]    [1,5,3,5,1,2,1,4]    4

 

입출력 예에 대한 설명

 

입출력 예 #1

인형의 처음 상태는 문제에 주어진 예시와 같습니다. 크레인이 [1, 5, 3, 5, 1, 2, 1, 4] 번 위치에서 차례대로 인형을 집어서 바구니에 옮겨 담은 후, 상태는 아래 그림과 같으며 바구니에 담는 과정에서 터트려져 사라진 인형은 4개 입니다.

문제 해결 방법

스택 자료구조를 이용하여 문제를 해결하였음

코드 구현

def solution(board, moves):
    #시간 복잡도는 O(N^3)까지 가능함.
    answer = 0
    # 바구니의 크기는 무한대 
    basket = []
    cnt=0
    for move in moves:
        for i in board:
            if i[move-1] != 0: #만약 i 줄 배열에 move칸에 값이 0이 아니라면
                try: # 바스켓이 비었을 때, pop하는 것을 방지하기 위함
                    a=basket.pop() # 바구니에서 뽑아서 현재 넣을 것과 비교
                    if a == i[move-1]: # 공통된다면 지우고 카운트 증가 시키기
                        cnt+=2
                        i[move-1] = 0
                    else:
                        basket.append(a)
                        basket.append(i[move-1]) # 바구니에 추가해줌
                        i[move-1] = 0 # 바구니에 추가한 것은 0으로 처리함
                except: #만약 바스켓이 비어있다면? 예외구문으로 
                    basket.append(i[move-1]) # 바구니에 추가해줌
                    i[move-1] = 0 # 바구니에 추가한 것은 0으로 처리함
                
                break # 해당 반복문 탈출 후, 다음 move조회
            else:# 만약 0이면
                continue #  다음 줄로 넘겨서 조회함 

    return cnt

시간/공간 복잡도

구현은 O(N^2)으로 하였음.

문제의 제한시간을 보면 O(N^3)으로 구현해도 문제 없을듯함.

최적화 및 개선

하지않음

어려웠던 점

없음

https://school.programmers.co.kr/learn/courses/3-/lessons/42584

 

프로그래머스

코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.

programmers.co.kr

 

문제설명

초 단위로 기록된 주식가격이 담긴 배열 prices가 매개변수로 주어질 때, 가격이 떨어지지 않은 기간은 몇 초인지를 return 하도록 solution 함수를 완성하세요.

 

제한사항

prices의 각 가격은 1 이상 10,000 이하인 자연수입니다.

prices의 길이는 2 이상 100,000 이하입니다.

 

입출력 예

prices    return

[1, 2, 3, 2, 3]      [4, 3, 1, 1, 0]

 

입출력 예 설명

1초 시점의 ₩1은 끝까지 가격이 떨어지지 않았습니다.

2초 시점의 ₩2은 끝까지 가격이 떨어지지 않았습니다.

3초 시점의 ₩3 1초뒤에 가격이 떨어집니다. 따라서 1초간 가격이 떨어지지 않은 것으로 봅니다.

4초 시점의 ₩2 1초간 가격이 떨어지지 않았습니다.

5초 시점의 ₩3 0초간 가격이 떨어지지 않았습니다.

문제 해결 방법

아 이문제는 참 어렵다! 시간 복잡도는 O(N^2)에 맞추면 안되고 O(NlogN)까지 가능하다. 

그런데 이 문제 아무리생각해봐도 O(NlogN)로 풀기 어려웠다. 그래서 O(N^2)로 풀어봤는데,,, 끝이 안난다. 

이조건 맞추면 저 조건 안맞고, 저 조건 맞추면 이 조건 안맞고 그랬다. 

 

그래서 결국 답을 보고 이해했다. 

 

이 문제는 효율성을 해결하기 위해서는 반드시 스택으로 풀어야한다. 그런데 이 문제 스택을 어디에 적용할지 떠올리기가 참 어렵다. 

 

코드 주석으로 설명하였다. 

 

코드 구현

 

기존 코드 - 미해결

def solution(prices):
    #O(N)으로 구현
    answer = []
    
    prices=list(prices)
    stackk=[]
    newPrices=[]
    newPrices = list(prices)

    for i in range(len(prices)):
        
        if i == 0:
            stackk.append(prices[i])
        else:
            
            newPrices.reverse()
            if len(newPrices)==0:
                break
            
            newPrices.pop()
            newPrices.reverse()
            cnt=0

            #print('prices[i]', prices[i-1], 'newPrices', newPrices)
            for price in newPrices:
                #print('price', price)
                if prices[i-1]<=price:
                     cnt+=1
            
            answer.append(cnt)
            
    answer.append(0)  
    #print(answer)
    
    
    
    return answer

 

개선 코드 - 해결

 

def solution(prices):
    answer = []
    total = len(prices)
    answer = [0] * total
    #각 초 시점의 길이를 넣을 배열
    stackk = [0] 

    # 스택을 0으로 초기화 한 이유는 순회를 인덱스 1부터 하기 위해서임 
    # prices의 0번 인덱스는 스택에 넣고 시작한다. 
    
    for i in range(1, total):
        # 1부터 total까지 순회한다. 
        # 0번 인덱스부터 total 인덱스까지 순회할 때, 가격의 증가만 있다면,
        # 계속 stackk에 넣는다. 
        # 만약 가격이 떨어진다면 그때부터는 스택에서 꺼내어서 하락한 가격의 인덱스로부터 길이를 구한다. 
        while stackk and prices[stackk[-1]]>prices[i]:
            a=stackk.pop()
            answer[a]=i-a
        stackk.append(i)
        
    while stackk: # 스택이 빌 때까지 순회하여 길이를 찾아준다. 
    #이 스택은 최종적으로 증가한 값들만 남아있다. 
        a=stackk.pop()
        answer[a]=total-a-1
        
    #print(answer)
    
    return answer

 

시간/공간 복잡도

O(NlogN)

최적화 및 개선

많은 개선을 했다. 음 로직을 아예 뜯어고침 

어려웠던 점/느낀점

답지를 안보고 혼자 코드 로직을 생각할 수 있을때 까지 연습하는것 까지 했다. 

다음에 또 풀때는 잘 풀었으면 좋겠다. 

https://school.programmers.co.kr/learn/courses/30/lessons/12973

 

프로그래머스

코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.

programmers.co.kr

문제설명

짝지어 제거하기는, 알파벳 소문자로 이루어진 문자열을 가지고 시작합니다. 먼저 문자열에서 같은 알파벳이 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을 반환합니다.


문제 해결 방법

주어진 str을 list로 바꿔서 list 요소를 순회시킨다. 

스택으로 쓸 배열을 하나 만든다. 

첫번째 요소는 스택에 넣고,

두번째 요소부터는 스택에 있는 값을 꺼내어 비교한 후 같으면 아무 동작하지 않고 넘어간다. 

만약 같지 않으면, 꺼낸 값을 스택에 다시 넣고, 현재 보고있는 list 요소도 스택에 같이 넣는다. 

 

순회가 끝나고, 스택의 길이를 재봤을때, 길이가 0이면 1을 반환, 길이가 0보다 크면 0을 반환한다. 


코드 구현

def solution(s):
    #O(nLogN)으로 구현
    stakk =[]
    newS=s
    newS=list(newS)
    
    for i in range(len(newS)):
        if i == 0 or len(stakk)==0:
            stakk.append(newS[i])
        else:
            a = stakk.pop()
            if newS[i] == a:
                continue
            else:
                stakk.append(a)
                stakk.append(newS[i])
    
    if len(stakk)==0:
        return 1
    else:
         return 0


시간/공간 복잡도

문제 제한 사항을 보니 O(NlogN)으로 풀어야 할 것 같았다. 

나는 O(N)으로 구현하게 되었다. 


최적화 및 개선

안함


어려웠던 점

머릿속으로 확신을 가지고 구현한게 아니라 이게 맞나 싶었는데 풀렸다. 

이런식으로 풀면 안좋다 그러던데,,, 담엔 확신 가질만큼 종이에 로직을 써보고 문제 풀어야겠다.

https://school.programmers.co.kr/learn/courses/30/lessons/76502#

 

프로그래머스

코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.

programmers.co.kr

문제 설명

다음 규칙을 지키는 문자열을 올바른 괄호 문자열이라고 정의합니다.

 

(), [], {} 는 모두 올바른 괄호 문자열입니다.

만약 A가 올바른 괄호 문자열이라면, (A), [A], {A} 도 올바른 괄호 문자열입니다. 예를 들어, [] 가 올바른 괄호 문자열이므로, ([]) 도 올바른 괄호 문자열입니다.

만약 A, B가 올바른 괄호 문자열이라면, AB 도 올바른 괄호 문자열입니다. 예를 들어, {} ([]) 가 올바른 괄호 문자열이므로, {}([]) 도 올바른 괄호 문자열입니다.

대괄호, 중괄호, 그리고 소괄호로 이루어진 문자열 s가 매개변수로 주어집니다. s를 왼쪽으로 x (0 ≤ x < (s의 길이)) 칸만큼 회전시켰을 때 s가 올바른 괄호 문자열이 되게 하는 x의 개수를 return 하도록 solution 함수를 완성해주세요.

 

제한사항

s의 길이는 1 이상 1,000 이하입니다.

 

입출력 예

s         result

"[](){}"    3

"}]()[{"    2

"[)(]"     0

"}}}"      0

 

입출력 예 설명

입출력 예 #1

 

다음 표는 "[](){}" 를 회전시킨 모습을 나타낸 것입니다.

x         s를 왼쪽으로 x칸만큼 회전          올바른 괄호 문자열?

0         "[](){}"    O

1         "](){}["    X

2         "(){}[]"    O

3         "){}[]("    X

4         "{}[]()"    O

5         "}[](){"    X

올바른 괄호 문자열이 되는 x 3개이므로, 3 return 해야 합니다.

 

입출력 예 #2

 

다음 표는 "}]()[{" 를 회전시킨 모습을 나타낸 것입니다.

x         s를 왼쪽으로 x칸만큼 회전          올바른 괄호 문자열?

0         "}]()[{"    X

1         "]()[{}"    X

2         "()[{}]"    O

3         ")[{}]("    X

4         "[{}]()"    O

5         "{}]()["    X

올바른 괄호 문자열이 되는 x 2개이므로, 2 return 해야 합니다.

 

입출력 예 #3

 

s를 어떻게 회전하더라도 올바른 괄호 문자열을 만들 수 없으므로, 0 return 해야 합니다.

 

입출력 예 #4

 

s를 어떻게 회전하더라도 올바른 괄호 문자열을 만들 수 없으므로, 0 return 해야 합니다.

 

문제 해결 방법

문제가 스택 자료구조로 풀어야 할 문제임에도 불구하고, 스택으로 풀 생각을 구체적으로 하지않고 그냥 단순히 함수만 쓸 생각으로 코드를 짰다. 아니나 다를까 문제는 거진 통과인데 제일 마지막 테스트케이스에서 딱 멈췄다. 

아~~ 테스트케이스를 추가하고 나서 어떻게 풀지 다시 생각해봤다. 

 

추가한 테스트 케이스는 다음과 같다. 

마지막 테스트 케이스를 풀기위해서는.. 아무리 생각해봐도 ... 스택적으로 문제를 풀 방법이 없다는 것을 깨달았다...

 

코드를 전면 수정했다. 기존 코드는 싹 지우고 다시 시작했다. 

 

주어진 string을 순회 시키고, 

 

각 string에서 한자 한자씩 읽는다. 

(, {, [ 를 왼쪽 괄호라고 부르겠다. 배열 하나를 새로 만들고

왼쪽 괄호가 나오면 그 배열에 왼쪽 괄호를 PUSH 한다. 

), }, ] 가 나오면 그 배열에서 POP한 것과 읽고 있는 글자가 같으면 넘어가고 카운트 한다

만약 글자가 같지 않으면 올바르지 않은 괄호 문자열이라고 판단한다. 

 

코드 구현

 

개선된 코드

def solution(s):
    left1 = [] 
    left2 = [] 
    left3 = [] 
    
    check = [0]*3
    pass1=0
    pass2=0
    
    for i in s:
        if i == '(':
            check[0]+=1
        elif i == '[':
            check[1]+=1
        elif i == '{':
            check[2]+=1
        elif i ==')':
            check[0]-=1
        elif i == ']':
            check[1]-=1
        elif i == '}':
            check[2]-=1
    
    if check[0] ==0 and check[1]==0 and check[2]==0:
        pass1=1
    
    mylist=list(s)
    
    if pass1==0:
        return 0
    
    else:
        thisis = 0
        for i in range(len(s)):
            stakk = [] 

            
            word = mylist.pop()
            mylist.insert(0, word)
            #print(mylist)
            #print("---")
            breakk=0
            for i in mylist:
                #print(i)
                if i == ']':
                    try: 
                        word = stakk.pop()
                        if word == '[':
                            continue
                        else:
                            breakk=1
                            break
                    except:
                        breakk=1
                        break
                elif i == ')':
                    try: 
                        word = stakk.pop()
                        if word == '(':
                            continue
                        else:
                            breakk=1
                            break
                    except:
                        breakk=1
                        break
                elif i == '}':
                    try: 
                        word = stakk.pop()
                        if word == '{':
                            continue
                        else:
                            breakk=1
                            break
                    except:
                        breakk=1
                        break
                elif i == '[':
                    stakk.append('[')
                elif i == '(':
                    stakk.append('(')
                elif i == '{':
                    stakk.append('{')
            
            if len(stakk)==0 and len(stakk)==0 and len(stakk)==0 and breakk==0:
                thisis+=1

        return thisis

 

기존 코드

def solution(s):
    left = [0] * 3
    
    check = [0]*3
    pass1=0
    pass2=0
    
    for i in s:
        if i == '(':
            check[0]+=1
        elif i == '[':
            check[1]+=1
        elif i == '{':
            check[2]+=1
        elif i ==')':
            check[0]-=1
        elif i == ']':
            check[1]-=1
        elif i == '}':
            check[2]-=1
    
    if check[0] ==0 and check[1]==0 and check[2]==0:
        pass1=1
    
    mylist=list(s)
    
    if pass1==0:
        return 0
    
    else:
        thisis = 0
        for i in range(len(s)):
            left = [0] * 3
            
            word = mylist.pop()
            mylist.insert(0, word)
            #print(mylist)
            #print("---")
            for i in mylist:
                #print(i)
                if i == ']':
                    left[0]-=1
                elif i == ')':
                    left[1]-=1
                elif i == '}':
                    left[2]-=1
                elif i == '[':
                    left[0]+=1
                elif i == '(':
                    left[1]+=1
                elif i == '{':
                    left[2]+=1
            
                if left[0]<0 or left[1]<0 or left[2]<0:
                    break
            #print('left[0]', left[0], 'left[1]', left[1], 'left[2]', left[2])
            
            if left[0]>=0 and left[1]>=0 and left[2]>=0:
                thisis+=1

            
                

        return thisis


시간/공간 복잡도

제한 사항을 보아하니 O(N^2)으로 구현해도 되겠다 싶었다. 

구현도 O(N^2)로 맞춰서 했다. 


최적화 및 개선

이렇게 되면 사실상 개선된 코드에서 짝맞추는 코드는 없애도 될 것 같다. 


어려웠던 점

생각하기,, 자료구조를 적용해서 생각하기,, 

https://school.programmers.co.kr/learn/courses/30/lessons/49994

 

프로그래머스

코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.

programmers.co.kr

문제설명

게임 캐릭터를 4가지 명령어를 통해 움직이려 합니다. 명령어는 다음과 같습니다.

 

U: 위쪽으로 한 칸 가기

 

D: 아래쪽으로 한 칸 가기

 

R: 오른쪽으로 한 칸 가기

 

L: 왼쪽으로 한 칸 가기

 

캐릭터는 좌표평면의 (0, 0) 위치에서 시작합니다. 좌표평면의 경계는 왼쪽 위(-5, 5), 왼쪽 아래(-5, -5), 오른쪽 위(5, 5), 오른쪽 아래(5, -5)로 이루어져 있습니다.

 

제한사항

dirs string형으로 주어지며, 'U', 'D', 'R', 'L' 이외에 문자는 주어지지 않습니다.

dirs의 길이는 500 이하의 자연수입니다.

 

입출력 예

dirs      answer

"ULURRDLLU"     7

"LULLLLLLU"       7

 

입출력 예 설명

입출력 예 #1

문제의 예시와 같습니다.

 

입출력 예 #2

문제의 예시와 같습니다.

 

문제 해결 방법

1. 우선 음수 좌표의 끝(-5,-5)를 (0,0)으로 생각하고 구현했다. 

2. set() 함수를 통해 중복을 제거함

3. U,D,L,R은 조건문을 통해서 처리되게 하였고, 제한하는 영역을 벗어나면 돌아올 수 있게 해줌

4. 지나간 거리는 예를들어 하나의 거리를 왼쪽에서 오른쪽으로 지나든, 오른쪽에서 왼쪽으로 지나든 방향 상관이 없기 때문에 해당 부분을 잘 체크해주었음 


코드 구현

개선한 코드 

def solution(dirs):
    answer = 0
    
    c = [[0]*11 for _ in range(11)]
    # 나는 (5, 5)에 있다. 거기서부터 시작한다. 
    arr=[]
    now = [5, 5]
    
    result = set()
    
    for dir in dirs:

        n1, n2 = now[0], now[1]
        if dir == "U":
            now[1]+=1
            if now[1]==11:
                now[1]=10
                
        elif dir == "D":
            now[1]-=1
            if now[1]==-1:
                now[1]=0
                
        elif dir == "L":
            now[0]-=1
            if now[0]==-1:
                now[0]=0
                
        elif dir == "R":
            now[0]+=1
            if now[0]==11:
                now[0]=10
        xtox, ytoy = now[0], now[1]

        if n1==xtox and n2==ytoy:
            pass
        else:
            result.add((n1, n2, xtox, ytoy))
            result.add((xtox, ytoy, n1, n2))
        
    answer=len(result)/2
    
    return answer

 

 

기존의 코드 

def solution(dirs):
    answer = 0
    
    c = [[0]*11 for _ in range(11)]
    # 나는 (5, 5)에 있다. 거기서부터 시작한다. 
    
    print(c)
    
    arr=[]
    
    now = [5, 5]
    arr.append([5,5])
    
    for dir in dirs:
        if dir == "U":
            now[1]+=1
            if now[1]==11:
                now[1]=10
                
        elif dir == "D":
            now[1]-=1
            if now[1]==-1:
                now[1]=0
                
        elif dir == "L":
            now[0]-=1
            if now[0]==-1:
                now[0]=0
                
        elif dir == "R":
            now[0]+=1
            if now[0]==11:
                now[0]=10
                
        print(now)    
        one=now[0]
        two=now[1]
        c[one][two]=1
        arr.append([one, two])
        
    print(arr)
    #중복제거를 먼저하고
    #이전에 갖고있던 원소랑 
    
    cnt=0
    for i in c:
        cnt += i.count(1)
        
    print("cnt:", cnt)
    
    return answer

 

 

시간/공간 복잡도

O(N)


최적화 및 개선

처음에는 좌표만큼의 이차원 배열을 0으로 채워 구현하고 그 좌표를 지나면 좌표에 대한 자리를 1로 바꿔주었다. 그런데 문제 예시 1번과 2번의 케이스에 대해 답이 다르게 나왔다. 이 케이스를 공통적으로 해결하기 위해서는 반드시 어디에서 출발했는지도 포함이 되어야 답이 나오는 문제였다. 

따라서 어떤 좌표에 도착했는지만 메기던 기존 코드에서 어디에서 출발했는지도 추가해서 4요소를 set을 통해서 추가하였다. 

어려웠던 점

아직 내공이 부족하구나~ 혼자 힘으로 해결하는 것도 좋지만, 안되겠다 싶으면 빠르게 인정하고 배움의 자세로 바로 공부하고 다음에 또 도전하는 것이 나에게 더 좋은 방법인것 같다~ 고집 이제 안녕~

https://school.programmers.co.kr/learn/courses/30/lessons/42889

 

프로그래머스

코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.

programmers.co.kr

문제설명

슈퍼 게임 개발자 오렐리는  고민에 빠졌다. 그녀가 만든 프랜즈 오천성이 대성공을 거뒀지만, 요즘 신규 사용자의 수가 급감한 것이다. 원인은 신규 사용자와 기존 사용자 사이에 스테이지 차이가 너무  것이 문제였다.

 문제를 어떻게 할까 고민  그녀는 동적으로 게임 시간을 늘려서 난이도를 조절하기로 했다. 역시 슈퍼 개발자라 대부분의 로직은 쉽게 구현했지만, 실패율을 구하는 부분에서 위기에 빠지고 말았다. 오렐리를 위해 실패율을 구하는 코드를 완성하라.

실패율은 다음과 같이 정의한다.

스테이지에 도달했으나 아직 클리어하지 못한 플레이어의  / 스테이지에 도달한 플레이어 

전체 스테이지의 개수 N, 게임을 이용하는 사용자가 현재 멈춰있는 스테이지의 번호가 담긴 배열 stages 매개변수로 주어질 , 실패율이 높은 스테이지부터 내림차순으로 스테이지의 번호가 담겨있는 배열을 return 하도록 solution 함수를 완성하라.

 

제한사항

 

스테이지의 개수 N 1 이상 500 이하의 자연수이다.

stages 길이는 1 이상 200,000 이하이다.

stages에는 1 이상 N + 1 이하의 자연수가 담겨있다.

 자연수는 사용자가 현재 도전 중인 스테이지의 번호를 나타낸다.

, N + 1  마지막 스테이지(N 번째 스테이지) 까지 클리어  사용자를 나타낸다.

만약 실패율이 같은 스테이지가 있다면 작은 번호의 스테이지가 먼저 오도록 하면 된다.

스테이지에 도달한 유저가 없는 경우 해당 스테이지의 실패율은 0 으로 정의한다.

 

입출력 

 

N                 stages        result

5                  [2, 1, 2, 6, 2, 4, 3, 3]           [3,4,2,1,5]

4                  [4,4,4,4,4]                    [4,1,2,3]

 

입출력  설명

 

입출력  #1

 

1 스테이지에는  8명의 사용자가 도전했으며,   1명의 사용자가 아직 클리어하지 못했다. 따라서 1 스테이지의 실패율은 다음과 같다.

1  스테이지 실패율 : 1/8

2 스테이지에는  7명의 사용자가 도전했으며,   3명의 사용자가 아직 클리어하지 못했다. 따라서 2 스테이지의 실패율은 다음과 같다.

2  스테이지 실패율 : 3/7

마찬가지로 나머지 스테이지의 실패율은 다음과 같다.

3  스테이지 실패율 : 2/4

4 스테이지 실패율 : 1/2

5 스테이지 실패율 : 0/1

 스테이지의 번호를 실패율의 내림차순으로 정렬하면 다음과 같다.

[3,4,2,1,5]

 

입출력  #2

 

모든 사용자가 마지막 스테이지에 있으므로 4 스테이지의 실패율은 1이며 나머지 스테이지의 실패율은 0이다.

[4,1,2,3]

문제 해결 방법

 

처음에는 for문 안에서 for문이 돌때 마다 도전한 사용자와 클리어하지 못한 사용자를 체크했었다. 

이 부분에서 5, 9, 22번 테스트케이스에서 계속 시간초과가 났다. 

 

이 문제를 해결하기 위해서 스테이지별로 도전하는 사용자의 수를 따로 체크하고, 실패한 사용자를 따로 체크해야했다. 


코드 구현

통과한 코드 

def solution(N, stages):
    answer = []
    # 도전 
    # 스테이지 별 도전자 수를 구함 
    challenger = [0] * (N+2)
    for stage in stages:
        challenger[stage] += 1
    
    fails = { }
    total = len(stages)
    
    for i in range(1, N+1):
        if challenger[i]==0:
            fails[i] = 0
        else:
            fails[i] = challenger[i] / total
            total=total-challenger[i]
            
    #print(fails)
    
    result = sorted(fails, key=lambda x: fails[x], reverse=True)
    #값을 기준으로 키를 정렬해서 반환함 
    
    #print(result)
    
    return result​

 

이 부분에서 5, 9, 22번 테스트케이스에서 계속 시간초과가 났던 코드 

def solution(N, stages):
    # 실패율을 구하는 코드를 완성하라 
    # 스테이지에 도달했으나 아직 클리어하지 못한 플레이어의 수 / 스테이지에 도달한 플레이어 수
    
    # 전체 스테이지의 개수 N
    # 사용자가 현재 멈춰있는 스테이지의 번호가 담긴 배열 stages
    
    
    # 실패율이 높은 스테이지부터 내림차순으로 스테이지의 번호가 담겨있는 배열을 return
    answer = []
    
    start = 1
    over_count = 0
    target_count = 0
    
    my_answer = { }
    
    while(1):
        if start > N:
            break
        
        for i in range(len(stages)):
            if stages[i] == start: # 스테이지를 진행중인 사람 
                target_count += 1
                over_count += 1 
            elif stages[i] > start: # 스테이지를 클리어 한 사람 
                over_count += 1
            
        if target_count == 0:
            my_answer[start] = 0
        else:
            my_answer[start] = target_count / over_count    
        #print(target_count, "/", over_count)
        
        #print(my_answer)
        
        over_count = 0
        target_count = 0
        start += 1
    
    result = sorted(my_answer, key=lambda x : my_answer[x], reverse=True)
    return result

 

시간/공간 복잡도

문제에서 200,000의 입력이 주어지므로써 이를 무난하게 통과하기 위해서는 NlogN의 시간복잡도가 나오는 알고리즘을 짜야 했다. 

 

 

최적화 및 개선

개선을 위해서 코드짤 때 관점과 구현 방법을 바꿔야했다. 

기존에는 사용자가 stages 배열을 를 구성하는 사용자들에 대해서 start 변수를 통해 순차적으로 스테이지를 증가시키고 stages 요소들을 돌면서 이를 넘겼느냐를 체크했다.

 

스테이지의 개수를 기준으로 도전하는 사용자와 실패한 사용자를  각각 반복문을 통해 메기면 굳이 이중 반복문을 사용하지 않아도됐다. 


어려웠던 점

한번 코드를 작성하려고 생각한 구현 관점을 수정하기가 어려웠다. 

이런 부분은 시간이 엄청 오래걸린다. 

 

그리고 확실히 시간복잡도를 미리 고려하고 코드의 효율성을 잘 확인하고 구현할 생각을 해야할 것 같다. 

문제를 어떻게 풀어야 겠다는 생각과 구현을 어떻게 해야하겠다는 생각은 다른 생각이고, 구현에 대한 생각을 굳이 하지 않았는데, 앞으로 문제 통과를 위해서 제대로 해야겠다는 생각이 든다. 

 

 

+ Recent posts