IT-garden

문제 설명

수포자는 수학을 포기한 사람의 준말입니다. 수포자 삼인방은 모의고사에 수학 문제를 전부 찍으려 합니다. 수포자는 1번 문제부터 마지막 문제까지 다음과 같이 찍습니다.

1번 수포자가 찍는 방식: 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, ...
2번 수포자가 찍는 방식: 2, 1, 2, 3, 2, 4, 2, 5, 2, 1, 2, 3, 2, 4, 2, 5, ...
3번 수포자가 찍는 방식: 3, 3, 1, 1, 2, 2, 4, 4, 5, 5, 3, 3, 1, 1, 2, 2, 4, 4, 5, 5, ...

1번 문제부터 마지막 문제까지의 정답이 순서대로 들은 배열 answers가 주어졌을 때, 가장 많은 문제를 맞힌 사람이 누구인지 배열에 담아 return 하도록 solution 함수를 작성해주세요.

제한조건

• 시험은 최대 10,000 문제로 구성되어있습니다.
• 문제의 정답은 1, 2, 3, 4, 5중 하나입니다.
• 가장 높은 점수를 받은 사람이 여럿일 경우, return하는 값을 오름차순 정렬해주세요.

입출력 예

입출력 예 설명

입출력 예 #1

• 수포자 1은 모든 문제를 맞혔습니다.
• 수포자 2는 모든 문제를 틀렸습니다.
• 수포자 3은 모든 문제를 틀렸습니다.

따라서 가장 문제를 많이 맞힌 사람은 수포자 1입니다.

입출력 예 #2

• 모든 사람이 2문제씩을 맞췄습니다.

나의 풀이

def solution(answers):
    a1 = [1, 2, 3, 4, 5]
    a2 = [2, 1, 2, 3, 2, 4, 2, 5]
    a3 = [3, 3, 1, 1, 2, 2, 4, 4, 5, 5]
    c1, c2, c3=0, 0, 0
    for i in range(len(answers)):
        s1 = i % 5
        s2 = i % 8
        s3 = i % 10

        if a1[s1] == answers[i]:
            c1 += 1
        if a2[s2] == answers[i]:
            c2 += 1
        if a3[s3] == answers[i]:
            c3 += 1
            
    k=max(c1,c2,c3)
    answer=[]

    if k == c1:
        answer.append(1)
    if k == c2:
        answer.append(2)
    if k == c3:
        answer.append(3)
    
    return answer

1. 각 수포자가 찍는 방식을 a1, a2, a3에 저장합니다.

2. 문제에 따라 찍을 숫자와 정답이 같은 경우 맞춘 횟수를 올려줍니다.

3. 가장 많이 맞춘 횟수를 k에 저장해주고 리스트에 담아 출력해줍니다. 

다른 사람의 풀이

def solution(answers):
    pattern1 = [1,2,3,4,5]
    pattern2 = [2,1,2,3,2,4,2,5]
    pattern3 = [3,3,1,1,2,2,4,4,5,5]
    score = [0, 0, 0]
    result = []

    for idx, answer in enumerate(answers):
        if answer == pattern1[idx%len(pattern1)]:
            score[0] += 1
        if answer == pattern2[idx%len(pattern2)]:
            score[1] += 1
        if answer == pattern3[idx%len(pattern3)]:
            score[2] += 1

    for idx, s in enumerate(score):
        if s == max(score):
            result.append(idx+1)

    return result

enumerate를 이용해 answer의 값과 찍은 숫자가 같은 경우 맞춘 횟수를 올려줍니다.

enumerate를 이용해 가장 많이 맞춘 횟수의 값들을 리스트에 넣어줍니다.

프로그래머스 '모의고사' : programmers.co.kr/learn/courses/30/lessons/42840?language=python3

문제 설명

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

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

제한조건

• 마라톤 경기에 참여한 선수의 수는 1명 이상 100,000명 이하입니다.
• completion의 길이는 participant의 길이보다 1 작습니다.
• 참가자의 이름은 1개 이상 20개 이하의 알파벳 소문자로 이루어져 있습니다.
• 참가자 중에는 동명이인이 있을 수 있습니다.

입출력 예

입출력 예 설명

예제 #1
leo는 참여자 명단에는 있지만, 완주자 명단에는 없기 때문에 완주하지 못했습니다.

예제 #2
vinko는 참여자 명단에는 있지만, 완주자 명단에는 없기 때문에 완주하지 못했습니다.

예제 #3
mislav는 참여자 명단에는 두 명이 있지만, 완주자 명단에는 한 명밖에 없기 때문에 한명은 완주하지 못했습니다.

나의 풀이

def solution(participant, completion):
    participant.sort()
    completion.sort()
    
    answer = participant[-1]
    for i in range(len(completion)):
        if participant[i] != completion[i]:
            answer = participant[i]
            break
            
    return answer

1. 참여한 선수들의 배열과 완주한 선수들의 배열을 정렬합니다.
2. 두 배열을 비교하여 값이 다른 경우 참여한 선수 배열의 값을 출력해줍니다.

다른 사람의 풀이

import collections

def solution(participant, completion):
    answer = collections.Counter(participant) - collections.Counter(completion)
    return list(answer.keys())[0]

Counter로 리스트의 원소들을 각각 세서 원소들을 key로, 등장하는 개수를 value로 하여 dictionary를 만들어 빼주었습니다. 그리고 마라톤에 참여했지만 완주하지 못한 선수를 key값으로 출력해주었습니다.

프로그래머스 '완주하지 못한 선수' : programmers.co.kr/learn/courses/30/lessons/42576?language=python3

문제

2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오.

아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다.

입력

첫째 줄에 n이 주어진다. (1 ≤ n ≤ 1,000)

출력

첫째 줄에 2×n 크기의 직사각형을 채우는 방법의 수를 10,007로 나눈 나머지를 출력한다.

예제 입력과 출력

알고리즘 분류

다이나믹 프로그래밍

정답

def _11726(n):
    if n == 1:
        return 1
    if n == 2:
        return 2
    if a[n] != 0:
        return a[n]
    
    a[n]= ( _11726(n-2) + _11726(n-1) ) % 10007
    return a[n]

a=[0]*1001

n=int(input())

print(_11726(n))

백준 알고리즘 11726번 : www.acmicpc.net/problem/11726

문제

정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 7가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다.

• 1+1+1+1
• 1+1+2
• 1+2+1
• 2+1+1
• 2+2
• 1+3
• 3+1

정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 n이 주어진다. n은 양수이며 11보다 작다.

출력

각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다.

예제 입력과 출력

알고리즘 분류

다이나믹 프로그래밍

정답

t=int(input())

def _9095(n):
    if n == 1:
        return 1
    if n== 2:
        return 2
    if n ==3:
        return 4
    
    return _9095(n-1)+_9095(n-2)+_9095(n-3)

for i in range(t):
    print(_9095(int(input())))

백준 알고리즘 9095번 : www.acmicpc.net/problem/9095

문제

동혁이는 나무 조각을 5개 가지고 있다. 나무 조각에는 1부터 5까지 숫자 중 하나가 쓰여져 있다. 또, 모든 숫자는 다섯 조각 중 하나에만 쓰여 있다.

동혁이는 나무 조각을 다음과 같은 과정을 거쳐서 1, 2, 3, 4, 5 순서로 만들려고 한다.

1. 첫 번째 조각의 수가 두 번째 수보다 크다면, 둘의 위치를 서로 바꾼다.
2. 두 번째 조각의 수가 세 번째 수보다 크다면, 둘의 위치를 서로 바꾼다.
3. 세 번째 조각의 수가 네 번째 수보다 크다면, 둘의 위치를 서로 바꾼다.
4. 네 번째 조각의 수가 다섯 번째 수보다 크다면, 둘의 위치를 서로 바꾼다.
5. 만약 순서가 1, 2, 3, 4, 5 순서가 아니라면 1 단계로 다시 간다.

처음 조각의 순서가 주어졌을 때, 위치를 바꿀 때 마다 조각의 순서를 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 조각에 쓰여 있는 수가 순서대로 주어진다. 숫자는 1보다 크거나 같고, 5보다 작거나 같으며, 중복되지 않는다. 처음 순서는 1, 2, 3, 4, 5가 아니다.

출력

두 조각의 순서가 바뀔때 마다 조각의 순서를 출력한다.

예제 입력과 출력

알고리즘 분류

버블 정렬

정답

import sys

n=sys.stdin.readline().split()

for j in range(len(n)):
    for i in range(1,len(n)):
        if n[i] < n[i-1]:
            n[i], n[i-1] = n[i-1], n[i]
            print(' '.join(n))

백준 알고리즘 2947번 : www.acmicpc.net/problem/2947

문제

민식이는 다음과 같은 폴리오미노 2개를 무한개만큼 가지고 있다. AAAA와 BB

이제 '.'와 'X'로 이루어진 보드판이 주어졌을 때, 민식이는 겹침없이 'X'를 모두 폴리오미노로 덮으려고 한다. 이때, '.'는 폴리오미노로 덮으면 안 된다.

폴리오미노로 모두 덮은 보드판을 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 보드판이 주어진다. 보드판의 크기는 최대 500이다.

출력

첫째 줄에 사전순으로 가장 앞서는 답을 출력한다. 만약 덮을 수 없으면 -1을 출력한다.

예제 입력과 출력

알고리즘 분류

그리디 알고리즘

정답

n=input()
a=0
i=0

while True:
    if i >= len(n):
        break
    
    if n[i:i+4] == 'XXXX':
        i=i+4
        n=n.replace('X','A',4)
    elif n[i:i+2] == 'XX':
        i=i+2
        n=n.replace('X','B',2)
    elif n[i] == '.':
        i=i+1
    else:
        n=-1
        break
        
print(n)

백준 알고리즘 1343번 : www.acmicpc.net/problem/1343