프로그래머스 level2 문제들(정답률 0%~40%)

- 혼자 놀기의 달인

def solution(cards):
    # 사용되지 않은 남은숫자들 집합으로 관리한다. 반복문이 끝나는지 판단하기 위해 사용됨
    remainNum = set([i+1 for i in range(len(cards))])
    # 각 상자 그룹 길이 저장
    boxGroupLen = []
    while len(remainNum) > 0:
        # 상자 그룹을 구한다.
        idx = min(list(remainNum))
        group = []
        while True:
            # 자신을 상자 그룹에 추가후 남은숫자에서 제외
            group.append(idx)
            remainNum.remove(idx)
            # 다음 카드가 이미 상자 그룹에 추가되었는지 확인
            if cards[idx-1] in group:
                break
            else:
                idx = cards[idx-1]
        boxGroupLen.append(len(group))
    if len(boxGroupLen) == 1:
        return 0
    boxGroupLen.sort(reverse=True)
    return boxGroupLen[0] * boxGroupLen[1]

- 과제 진행하기

24시가 지나도 작업을 계속한다. 이 조건때문에 헷갈렸다.

def solution(plans):
    answer = []
    # 00:00부터 1분씩 지난다.
    hour = 0
    minute = 0
    # 시작시간 기준으로 내림차순 정렬
    plans.sort(key=lambda x:x[1], reverse=True)
    for i in range(len(plans)):
        plans[i][2] = int(plans[i][2])
    # 멈춘 작업을 저장할 스택
    stop = []
    # 현재 진행중 과제
    current = None
    while not (current == None and len(stop) == 0 and len(plans) == 0):
        # 현재 과제 없음
        if current == None:
            # 새로운 과제 시작시간
            if len(plans) > 0 and int(plans[-1][1].split(':')[0]) == hour and int(plans[-1][1].split(':')[1]) == minute:
                current = plans.pop()
            # 멈춘 과제 있다면
            elif len(stop) > 0:
                current = stop.pop()
        # 현재 과제 있음
        else:
            # 새로운 과제 시작시간
            if len(plans) > 0 and int(plans[-1][1].split(':')[0]) == hour and int(plans[-1][1].split(':')[1]) == minute:
                stop.append(current)
                current = plans.pop()
                
        # 진행중 과제가 있다면 1분씩 줄어든다.
        if current != None:
            current[2] -= 1
            # 작업시간이 0이라면 종료작업에 추가
            if current[2] == 0:
                answer.append(current[0])
                current = None
        # 1분식 시간 경과.
        minute += 1
        if minute == 60:
            minute = 0
            hour += 1
    return answer

- 두 원 사이의 정수 쌍

def solution(r1, r2):
    import math
    # x가 0초과일때 y가 0이상인 정수인 점의 개수* 4를 하면 된다.
    answer = 0
    # x가 0초과일 때 반지름이 r2이하 r1이상
    for x in range(1, r2+1):
        yMax = int(math.sqrt(r2*r2 - x*x))
        yMin = 0
        if x < r1:
            yMin = math.ceil(math.sqrt(r1*r1 - x*x))
        answer += (yMax-yMin+1) * 4
    return answer

- 이모티콘 할인행사

def solution(users, emoticons):
    # 모두고려로 해보자.
    answer = [0, 0]
    # len(emoticons)개 만큼 각각 할인률이 있다. 초기값은 모두 10퍼씩 할인.
    discount = [10 for i in range(len(emoticons))]
    def nextDiscount(discount, i):
        if discount[i] == 40:
            discount[i] = 10
            nextDiscount(discount, i+1)
        else:
            discount[i] += 10
    # 모든 할인률을 고려하여 목표에 맞는지 확인한다.
    while True:
        # 한 할인률에 의한 결과값
        result = [0, 0]
        # 모든 사람마다 계산
        for [rate, price] in users:
            pay = 0
            # 모든 이모티콘마다 계산
            for k in range(len(emoticons)):
                # 비율 이상 할인하면 이모티곤 구매
                if discount[k] >= rate:
                    pay += emoticons[k] // 100 * (100-discount[k])
            if pay >= price:
                result[0] += 1
            else:
                result[1] += pay
        # 최대목표라면 교체.
        if answer[0] < result[0]:
            answer = result
        elif answer[0] == result[0] and answer[1] < result[1]:
            answer = result
        # 모두 40퍼 할인이라면 break
        if all(40 == d for d in discount):
            break
        # 다음 할인
        nextDiscount(discount, 0)
    return answer

- N-Queen

처음에 시간초과한 코드. 1시간 반동안 했는데 시간초과가 나오니 포기할 뻔 했다.

def solution(n):
    import copy
    from collections import deque
    # dfs 또는 bfs로 완전탐색하면 될것 같다.
    # 시간초과가 나니 dp도 하자.
    answer = set()
    dp = set()
    array = [[0 for x in range(n)] for y in range(n)]
    deq = deque()
    deq.append([copy.deepcopy(array), n, []]) # [배열, 남은 q개수, q좌표들]
    count = 0
    while len(deq) > 0:
        [arr, cnt, coordinate] = deq.popleft()
        # 고려한적 있는 좌표라면 고려하지 않음.
        if tuple(coordinate) in dp:
            continue
        else:
            dp.add(tuple(coordinate))
        # 남은 q개수가 없다면 answer에 추가. 중복 검사를 해야한다.
        if cnt == 0:
            if tuple(coordinate) not in answer:
                answer.add(tuple(coordinate))
            continue
        # 남은 q개수가 있다면 검사하여 q를 넣을 것이다.
        # 위에서 아래로, 왼쪽에서 오른쪽으로 0이 있는지 확인. 0이 있다면 q를 넣는다.
        for y in range(n):
            for x in range(n):
                if arr[y][x] == 0:
                    # q는 상하좌우 대각선으로 칸을 1로 점령한다.
                    arr2 = copy.deepcopy(arr)
                    # 상하좌우
                    for i in range(n):
                        arr2[y][i] = 1
                        arr2[i][x] = 1
                    # 왼쪽위
                    for i in range(1, n):
                        if (y-i)<0 or (x-i)<0:
                            break
                        arr2[y-i][x-i] = 1
                    # 오른쪽위
                    for i in range(1, n):
                        if (y-i)<0 or (x+i)>=n:
                            break
                        arr2[y-i][x+i] = 1
                    # 왼족아래
                    for i in range(1, n):
                        if (y+i)>=n or (x-i)<0:
                            break
                        arr2[y+i][x-i] = 1
                    # 오른쪽아래
                    for i in range(1, n):
                        if (y+i)>=n or (x+i)>=n:
                            break
                        arr2[y+i][x+i] = 1
                    coordinate2 = copy.deepcopy(coordinate)
                    coordinate2.append((y, x))
                    deq.append([arr2, cnt-1, sorted(coordinate2)])
    return len(answer)

나중에 코드. 한 줄에 하나의 퀸만 들어갈 수 있다는 특수성을 이용하면 1차원 배열만으로 구현 가능하다.

def solution(n):
    answer = 0
    # 한줄에 하나의 퀸만 들어갈 수 있으므로 1차원 배열로 가능하다. [1, 3, 0, 2]같이.
    stack = []
    for i in range(n):
        stack.append([i])
    while len(stack) > 0:
        arr = stack.pop()
        if len(arr) == n:
            answer += 1
        # y좌표는 겹치는걸 생각하지 않아도 된다. 다음 인덱스가 다음 y좌표를 의미한다.
        for x in range(n):
            # 값이 x좌표를 의미하므로 겹치지 않으면 된다.
            # x좌표도 안겹치고 대각선으로도 만나지 않으면 퀸을 놓을 수 있다.
            if x not in arr:
                for i in range(len(arr)):
                    # |놓을 x좌표 - 놓여있는 x좌표| == |놓을 y좌표 - 놓여있는 y좌표|
                    if abs(arr[i] - x) == abs(i - len(arr)):
                        break
                else:
                    stack.append(arr+[x])
    return answer

- 혼자서 하는 틱택토

실수의 조건을 잘 정의한 후에 코드를 짜면 된다.

def solution(board):
    # 실수1 : O의 개수 - X의 개수가 0또는 1이 아닐경우
    oCnt = 0
    xCnt = 0
    for b in board:
        for c in b:
            if c == 'O':
                oCnt += 1
            elif c == 'X':
                xCnt += 1
    if not ((oCnt-xCnt) == 0 or (oCnt-xCnt) == 1):
        return 0
    # 실수2 : O와 X가 둘다 우승한 경우, O가 이긴경우 oCnt-xCnt!=1, X가 이긴경우 oCnt!=xCnt
    oWin = False
    xWin = False
    # 가로로 3개가 같을경우
    if board[0][0] == board[0][1] == board[0][2] != '.':
        if board[0][0] == 'O':
            oWin = True
        else:
            xWin = True
    if board[1][0] == board[1][1] == board[1][2] != '.':
        if board[1][0] == 'O':
            oWin = True
        else:
            xWin = True
    if board[2][0] == board[2][1] == board[2][2] != '.':
        if board[2][0] == 'O':
            oWin = True
        else:
            xWin = True
    # 세로로 3개가 같을 경우
    if board[0][0] == board[1][0] == board[2][0] != '.':
        if board[0][0] == 'O':
            oWin = True
        else:
            xWin = True
    if board[0][1] == board[1][1] == board[2][1] != '.':
        if board[0][1] == 'O':
            oWin = True
        else:
            xWin = True
    if board[0][2] == board[1][2] == board[2][2] != '.':
        if board[0][2] == 'O':
            oWin = True
        else:
            xWin = True
    # 대각선으로 3개가 같을 경우
    if board[0][0] == board[1][1] == board[2][2] != '.':
        if board[0][0] == 'O':
            oWin = True
        else:
            xWin = True
    if board[0][2] == board[1][1] == board[2][0] != '.':
        if board[0][2] == 'O':
            oWin = True
        else:
            xWin = True
    if oWin and xWin:
        return 0
    elif oWin:
        if oCnt-xCnt != 1:
            return 0
    elif xWin:
        if oCnt != xCnt:
            return 0
    return 1

- 요격 시스템

풀어본 결과 s를 기준으로 정렬하던 e를 기준으로 정렬하던 둘다 정답은 구할 수 있다. 
s를 기준으로 정렬하면, 제일 큰 s를 target들의 e들과 비교하면 되고, 
e를 기준으로 정렬하면, 제일 작은 e를 target들의 s들과 비교하면 된다.

def solution(targets):
    # 앞을 기준으로 정렬하고, 뒤에서부터 겹치는것을 제거하면 된다.
    # s, e기준으로 정렬 후 앞에서부터 겹치는것을 제거
    targets.sort()
    answer = 0
    while len(targets) > 0:
        # s구함. 제일 큰 s를 구한것이기 때문에 다음 것들은 e만 비교하면 된다.
        s = targets[-1][0]
        # e가 제일 큰 s보다 작은 target들은 제외시킨다.
        while targets:
            if s < targets[-1][1]:
                targets.pop()
            else:
                break
        answer += 1
    return answer

- 숫자 블록

def solution(begin, end):
    def block(num):
        # 숫자를 약수로 나눈 수 중에 10000000보다 작으면서 가장 큰 수를 구한다.
        import math
        if num == 1:
            return 0
        arr = [1]
        for i in range(2, int(math.sqrt(num))+1):
            if num % i == 0:
                arr.append(i)
                if num//i <= 10000000:
                    arr.append(num//i)
        return max(arr)
    answer = []
    for x in range(begin, end+1):
        answer.append(block(x))
    return answer

- 조이스틱

그리디 문제라고 되어있지만 사실은 그렇지 않은 문제이다.

def solution(name):
    import copy
    # 다음 이전 알파벳은 딕셔너리를 사용하면 된다.
    # 왼쪽 오른쪽으로 옮기는것을 최소로 하는 방법을 고려하는 문제이다.
    # 처음에는 그리디인줄 알았지만 그리디가 아니다. dfs로 해보자.
    answer = 100
    length = len(name)
    cntDict = {"A":0,"B":1,"C":2,"D":3,"E":4,"F":5,"G":6,"H":7,"I":8,"J":9,"K":10,"L":11,"M":12,"N":13,"O":12,"P":11,"Q":10,"R":9,"S":8,"T":7,"U":6,"V":5,"W":4,"X":3,"Y":2,"Z":1,}
    # 다음 이전 알파벳 조이스틱 카운트
    alphaCnt = 0
    for n in name:
        alphaCnt += cntDict[n]
    name = list(name)
    # 길이가 1이면 반환
    if length==1:
        return alphaCnt
    # 왼쪽 오른쪽 조이스틱 카운트
    name[0] = 'A'
    stack = [[name, 0, 0]] #[name, idx, cnt]
    while len(stack)>0:
        [name, idx, cnt] = stack.pop()
        # 모든 알파벳이 A라면 종료
        if all(n=='A' for n in name):
            if answer > cnt:
                answer = cnt
            continue
        # 좌우로 가까운 A가 아닌 알파벳 탐색
        # 우로 탐색
        for x in range(1, length):
            if name[(idx+x)%length] != 'A':
                name2 = copy.deepcopy(name)
                name2[(idx+x)%length] = 'A'
                stack.append([name2, (idx+x)%length, cnt+x])
                break
        # 좌로 탐색
        for x in range(1, length):
            if name[idx-x] != 'A':
                idx -= x
                if idx < 0:
                    idx += length
                name3 = copy.deepcopy(name)
                name3[idx] = 'A'
                stack.append([name3, idx, cnt+x])
                break
    return answer + alphaCnt

- 양궁대회

처음 코드. n=10일때 시간초과가 난다.

import copy
from collections import deque
def solution(n, info):
    # 최대 점수차와 최대의 과녁판.
    maxD = 0
    maxScore = [-1]
    # 0점 ~ 10점까지의 순서로 바꾼다.
    info.reverse()
    # bfs로 모든 경우의 수를 알아낸다.
    deq = deque()
    deq.append([0,0,0,0,0,0,0,0,0,0,0])
    dp = set()
    possible = []
    while len(deq) > 0:
        score = deq.popleft()
        # 쏜 횟수가 n이면 경우의 수에 추가 후 continue
        if (sum(score) >= n):
            possible.append(score)
            continue
        # 0~10점까지 과녁을 맞추는 경우 push
        for i in range(11):
            nextScore = copy.deepcopy(score)
            nextScore[i] += 1
            if tuple(nextScore) in dp:
                continue
            deq.append(nextScore)
            dp.add(tuple(nextScore))
    # 모든 경우의 수에서 점수를 구한다.
    for score in possible:
        a = 0 # 어피치 점수
        r = 0 # 라이언 점수
        # 점수차를 구한다.
        for i in range(11):
            if score[i] == 0 and info[i] == 0:
                continue
            elif score[i] > info[i]:
                r += i
            else:
                a += i
        d = r - a # 점수차
        if d > maxD:
            maxD = d
            maxScore = score
    maxScore.reverse()
    return maxScore

모든 경우의 수를 구할 필요가 없다. 라이언이 이기는 경우를 구하는 것이기 때문에, 점수마다 0발 또는 (어피치가 맞춘 개수 +1)발 맞추는 경우만 고려하면 된다. 버리는 화살일 경우만 아니면 말이다.

import copy
from collections import deque
def solution(n, info):
    # 최대 점수차와 최대의 과녁판.
    maxD = 1
    maxScore = [-1]
    # 0점 ~ 10점까지의 순서로 바꾼다.
    info.reverse()
    # bfs로 모든 경우의 수를 알아낸다.
    deq = deque()
    deq.append([0,0,0,0,0,0,0,0,0,0,0])
    dp = set()
    possible = []
    while len(deq) > 0:
        score = deq.popleft()
        scoreSum = sum(score)
        # 쏜 횟수가 n이면 경우의 수에 추가 후 continue
        # n 이상이면 경유의 수에 넣지 않는다.
        if (scoreSum >= n):
            if (scoreSum == n):
                possible.append(score)
            continue
        # 0~10점까지 과녁을 맞추는 경우 push
        for i in range(11):
            # i번째에 숫자가 있다면 제외.
            if (score[i] > 0):
                continue
            nextScore = copy.deepcopy(score)
            # i번째에 어피치보다 1개 많게 쏜다. 그래야 점수를 얻을 수 있으니까.
            # 총 n개를 넘어간다면 합쳐서 n개인 화살 수만 더한다.
            nextScore[i] += min([(info[i]+1), (n-scoreSum)])
            if tuple(nextScore) in dp:
                continue
            deq.append(nextScore)
            dp.add(tuple(nextScore))
    # 모든 경우의 수에서 점수를 구한다.
    for score in possible:
        a = 0 # 어피치 점수
        r = 0 # 라이언 점수
        # 점수차를 구한다.
        for i in range(11):
            if score[i] == 0 and info[i] == 0:
                continue
            elif score[i] > info[i]:
                r += i
            else:
                a += i
        d = r - a # 점수차
        if d > maxD:
            maxD = d
            maxScore = score
        # 가장 낮은 점수를 더 많이 맞힌 경우의 수라면 maxScore바꿈.
        elif d == maxD:
            for i in range(11):
                if score[i] > maxScore[i]:
                    maxScore = score
                    break
                elif score[i] < maxScore[i]:
                    break
    maxScore.reverse()
    return maxScore