미야's Day

이 문제를 풀면서 정말 많은 시도를 했던 문제였다...

처음에는 14번부터 테케가 통과가 안되더니

다시 수정후, 17번 테케만 유독 안되었다...

그렇게 방법을 찾던 중, 질문하기에 누군가가 17번 테케를 남겨놓은 댓글을 보았고,

해당 테케를 추가했더니 딱 그 테케에서 오류가 났다!

이 부분에 대한 원인을 찾아서 수정하고 나니 통과할 수 있었다. 후후....

혹시나 저처럼 17번 테스트케이스에서 계속 틀리는 분들을 위하여 포스팅을 남겨놓겠슴다..

문제설명:

제한사항:

나의 풀이:

저는 이렇게 풀었다 정도로만 생각해주세요...ㅎㅎ

def solution(keymap, targets):
    answer = [0] * len(targets)
    key_count = 0
    
    for word in range(len(targets)):
        for i in targets[word]:
            key_count = 0
            for key in keymap:
                if i in key:
                    if key_count != 0:
                        if key_count >= key.index(i) + 1:
                            key_count = key.index(i) + 1
                    else:
                        key_count = key.index(i) + 1          
                else:
                    continue 
            if key_count == 0:
                answer[word] = -1
            else:
                if answer[word] != -1:
                    answer[word] += key_count
    

    return answer

추가한 테스트케이스:

오류났던 원인?

오류가 발생했던 코드는 첫문장 for word in range(len(targets)) -> for word in targets로 설정하여 answer에 index값을 word에 해당하는 인덱스로 지정하여 값을 넣어주었더니

위와 같이 targets의 원소가 같을 경우 항상 첫번째 인덱스에 값을 넣어주어 [27, 0, 0]으로 값이 나와 오류가 났던 것이었다.

내 코드)

from fractions import Fraction
def solution(N, stages):
    answer = []
    success = []
    cnt = 0
    for i in range(1, N + 1):
        if i in stages:
            a = stages.count(i)
            b = len(stages) - cnt 
            cnt += a 
            success.append([i, float(Fraction(a, b))])
        if i not in stages:
            success.append([i, 0])
    success.sort(key = lambda x : (-x[1], x[0]))  #x[1]은 내림차순, 같은 값일 경우 x[0] 오름차순 정렬
                
    for i in range(N):
        answer.append(success[i][0])    
    return answer

*오늘의 배움!

ⓐ리스트.sort(key = lambda x : ( -x[1] , x[0]))  

>> 앞에 -1을 붙이면 reverse=True 역순을 의미함. 즉, x[1]키를 기준으로 역순으로 정렬하고, x[1]이 같은 값일 경우 x[0]을 기준으로 정렬한다. 

ⓑ리스트.sort(key = lambda x : -x[1])

>> 같은 값이 없거나 계산할 필요 없을 경우 이런식으로 조건 하나만 써줘도 됨.

ⓒsorted(리스트, key= len) 

>> 이런식으로 sorted로 계산해줘도 된다.

프로그래머스 level1. 소수찾기 

원래 풀이대로 하면 시간 초과가 되었다. n의 조건이 2<= n <= 1000000이므로 이 문제는 에라토스테네스의 체를 이용하여 구해야 한다. 

풀이방법:

def solution(n):
    answer = 0
    #에라토스테네스의 체 
    a = [False, False] + [True]*(n-1)   #0,1을 제외한 모든 수를 소수라고 지정 
    primes = []
    
    for i in range(2, n+1):
        if a[i] == True:
            primes.append(i)
            answer += 1
            for j in range(2*i, n+1, i):     #i의 배수 모두 삭제 
                a[j] = False
                
    return answer

프로그래머스 level1. 기사단원의 무기 (약수)

이 문제 또한 약수의 개수를 구하는 문제인데, 루트를 사용하여 시간 복잡도를 줄이는 방향으로 문제를 풀어줘야 한다.

def solution(number, limit, power):
    answer = 0
    prime = [0] * number
    for i in range(1, number+1):
        for j in range(1, int(i**(1/2))+1):
            if i % j == 0:
                prime[i-1] += 1
                if (j**2) != i:
                    prime[i-1] += 1
        if prime[i-1] > limit:
            prime[i-1] = power
    answer = sum(prime)
        
    return answer

처음으로 시간 복잡도를 활용해서 문제를 풀어야 통과가 되는 경험을 하면서 이전보다 문제를 풀이할 때 시간 복잡도를 고려한 방식으로 생각하게 되는 계기가 된 문제들이었다. 

이 문제는 구현 유형 중에 하나인데, 풀이 방법은 여러가지가 있는 것 같다.

후보 수 N명이 주어지고, 각 후보자에 대한 지지하는 사람 수가 주어진다.

그 중 1번 후보자를 지지하는 사람 수가 가장 많아지도록 다른 후보자 지지자 수에서 한 번씩 빼와서 더할 때마다 카운트를 하여 최댓값을 만들 수 있는 카운트의 최솟값을 구하는 문제다.

-나의 풀이 방법:

import sys
input = sys.stdin.readline

n = int(input())    #후보자 수
people = []    #후보자를 지지하는 사람 수를 담을 리스트 
cnt = 0    #연산 횟수 
for _ in range(n):    #각 후보자를 지지하는 사람 수를 입력받아 people리스트에 넣는다. 
    people.append(int(input()))  

while True:
    if people[0] == max(people):    #1번 후보자(people[0]) 지지자 수가 가장 큰 수일때
        for i in range(1, len(people)):    #1번 후보자 외의 후보자 지지자 수를 비교하여 
            if people[i] == people[0]:     #1번 후보자 지지자 수와 동일한 후보자가 있을 때
                cnt += 1          #연산 한 번 수행 후 종료 
                break
        break
    else:                #1번 후보자 지지자 수가 가장 큰 수가 아닐 때
        people[people.index(max(people))] -= 1      #가장 많은 지지자 수를 1감소
        people[0] += 1           #1번 후보자 지지자 수 1증가
        cnt += 1      #연산 1회 증가 
        if max(people) == people[0]:      #1번 후보자 지지자 수가 가장 큰 수가 됬을 때 종료
            for i in range(1, len(people)):    #다른 후보자 지지자 수 중 같은 값이 있을 시
                if people[i] == people[0]:
                    cnt += 1            #연산 1회 증가 후 중료 
                    break
            break
print(cnt)                 #cnt연산값 출력

아직은 if문과 for문을 많이 쓰는 방법으로 구현하고 있다.....ㅎㅎ

이 방법이 시간 복잡도 면에서 좋지 않은 방법이라고 해서 다른 사람들 코드를 보며 계속 공부해야 할 것 같다.

내 생각에 파이썬으로 계속 알고리즘을 풀어본 결과, 내장 함수나 문법을 많이 알고 있을수록 더 효율적이고 시간을 절약할 수 있는 코드를 작성할 수 있는 것 같다. 결국엔 지식의 중요성.....?!!

이와 같이 생각한 이유는 밑에 다른 사람의 코드를 보면 이해할 수 있다. 

하지만 이렇게 손코딩으로 1부터 10까지 직접 풀어보며 원리를 이해해나가는 것도 지금 단계에서는 중요하다고 생각한다.

-다른 사람 풀이

import heapq

n = int(input())

hq = []
for i in range(n):
    votes = int(input())
    if i == 0:
        dasom_votes = votes
        continue

    heapq.heappush(hq, -votes)

bribe_count = 0
while hq:
    votes = -heapq.heappop(hq)
    if votes < dasom_votes:
        break

    dasom_votes += 1
    bribe_count += 1
    heapq.heappush(hq, -(votes - 1))

print(bribe_count)

이 분은 파이썬 표준 라이브러리 중 하나인 힙을 이용해서 구현해냈다. 정말 다른 분들 코드를 볼 수록 대단한 분들이 많은 것 같다...ㅎㅎ 나도 열심히 공부해서 나중엔 한 줄로 알고리즘을 풀 수 있는...날이 오길...ㅎㅎ?

시험 및 서류 접수랑 면접보는 일정도 드디어 다 끝나서 오늘은 하루종일 알고리즘만 주구장창 풀었다.

그랬더니 20문제정도 풀었다..ㅎㅎ

그리고 등급도 하나 올려서 실버4로 등극했다..

하나하나씩 올라가는 실력이 느껴져서 뿌듯하고 또 알고리즘은 풀면 풀수록 재밌고 어려운것 같다.. ㅎㅎ

지금은 파이썬으로 풀고 있지만 좀더 익숙해지면 자바스크립트로도 같이 풀어봐야겠다.

네이버 코테 뚫을 수 있을 때까지 아자아자! 이제 매일 꾸준히 조금씩이라도 알고리즘을 풀면서 컴퓨팅적 사고 능력을 길러야겠다.

코테 준비를 위해 알고리즘 기초를 다시 탄탄히 다지며 복습할 겸 코드업 기초 100제 파이썬 문제를 쭉 풀었다.

앞 부분은 확실히 예전에 비해 쉽게 풀렸으나, 뒷부분으로 갈수록 20분 정도 푸는데 시간이 걸렸고, 실패도 몇 번했으나, 결국 통과되었다.ㅎㅎ

이 문제는 파이썬의 기본인 출력함수 그리고 좌표문제에 유용하게 쓰일 수 있는 내용이라 담아보았다.

[6097] 설탕과자 뽑기

부모님과 함께 놀러간 영일이는
설탕과자(설탕을 녹여 물고기 등의 모양을 만든 것) 뽑기를 보게 되었다.
길이가 다른 몇 개의 막대를 바둑판과 같은 격자판에 놓는데,
막대에 있는 설탕과자 이름 아래에 있는 번호를 뽑으면 설탕과자를 가져가는 게임이었다.

(잉어, 붕어, 용 등 여러 가지가 적혀있다.)

격자판의 세로(h), 가로(w), 막대의 개수(n), 각 막대의 길이(l),
막대를 놓는 방향(d:가로는 0, 세로는 1)과
막대를 놓는 막대의 가장 왼쪽 또는 위쪽의 위치(x, y)가 주어질 때,
격자판을 채운 막대의 모양을 출력하는 프로그램을 만들어보자.

입력:

첫 줄에 격자판의 세로(h), 가로(w) 가 공백을 두고 입력되고,
두 번째 줄에 놓을 수 있는 막대의 개수(n)
세 번째 줄부터 각 막대의 길이(l), 방향(d), 좌표(x, y)가 입력된다.
1 <= w, h <= 100
1 <= n <= 10
d = 0 or 1
1 <= x <= 100-h
1 <= y <= 100-w

출력:

모든 막대를 놓은 격자판의 상태를 출력한다.
막대에 의해 가려진 경우 1, 아닌 경우 0으로 출력한다.
단, 각 숫자는 공백으로 구분하여 출력한다.

입력 예시:

5 5

3

2 0 1 1

3 1 2 3

4 1 2 5

출력 예시:

1 1 0 0 0

0 0 1 0 1

0 0 1 0 1

0 0 1 0 1

0 0 0 0 1

<나의 코드>

h, w = map(int, input().split())
A = [[0] * w for _ in range(h)]

n = int(input())
for _ in range(n):
    l, d, x, y = map(int, input().split())
    for i in range(l):
        if d == 0:
            A[x - 1][y + i - 1] = 1
        else:
            A[x + i - 1][y - 1] = 1

for i in range(h):
    for j in range(w):
        print(A[i][j], end=' ')
    print()

<코드 설명>

1) 먼저, h, w로 격자판의 세로(h), 가로(w)길이를 공백으로 입력받는다. map함수를 사용해서 바로 입력받은 데이터를 정수형으로 변환시켜 주었다.

2) 세로, 가로 길이가 h, w인 0으로 채워진 격자판 배열 A를 선언한다. 이중 배열 형식으로 선언했다.

3) 막대 개수 정수형 n개를 입력받는다.

4) 막대 개수 n개 만큼 반복하면서 l, d, x, y를 입력받는다.

5) 입력받을 때마다 i를 막대 길이 l만큼 반복하면서 d가 0이면(가로), 

    y에 i를 더하여 오른쪽 옆으로 l길이만큼 1을 대입한다. 

6) 이 때 각 x, y 자리에 1씩 빼는 이유는 격자 길이는 0이없고 1부터 시작하지만, 배열의 인덱스는 0부터 시작하므로 -1씩 각각 빼주는 것이다. 

이 과정을 빼먹으면 list out of range 에러가 발생한다. (이것때문에 몇 분 날렸음 ㅎㅎ)

7) 그리고 마지막에 h(세로) 범위의 w(가로) 범위만큼 돌면서 A[i][j]를 출력하고, end=' '는 파이썬 자동 줄바꿈 기능을 방지하고 공백으로 이어준다. 그리고 밑에 print()를 하여 띄어쓰기를 해주어 격자처럼 다음줄에 두번째 h범위의 값들이 출력되게 해준다. 

sep=' ' vs end=' '

end=' ' 대신에 sep=' ' 을 입력하면 출력결과가 가로로 나오는 것이 아닌 세로로 출력된다. 즉 줄바꿈이 된다는 것이다.

따라서 줄바꿈을 하지 않고 가로로 입력하고 싶을 땐 end=' ' 를 사용하쟈! 

작성한 코드

import sys
sys.setrecursionlimit(100000)

def gcd(a, b):
    while b > 0:
        a, b = b, a % b
    return a


N = int(input())
graph = []
for _ in range(N):
    graph.append(int(input()))
graph.sort()

tmp = []
for k in range(1, N):
    tmp.append(graph[k] - graph[k - 1])

num = tmp[0]

for i in range(1, N - 1):
    num = gcd(num, tmp[i])

ans = []
for j in range(2, num + 1):
    if num % j == 0:
        ans.append(j)
ans.sort()

for p in ans:
    print(p, end=' ')

첫줄에 런타임에러에 대한 코드를 써주었는데도 시간 초과가 난다..

입출력값은 잘 나오는데 ㅠㅠ 왜이런 것일까..

알아봐야겠다.

하하 ..

자신감있게 문제 풀고 제출 했는데 계속 틀려서 영문을 모르다가..

다른 분들 코드를 살짝 보고 예외값이 있다는 것을 깨달았다!!

ㅇㅖ로, L, P, V 가 3, 8, 20 일 경우

V % P 값(4) 이 L(3)값보다 커서 원래 답인 9가 아닌 10이 나오게 된다.

따라서 그 부분을 if문으로 넣어 수정해주었다. 

먼저 처음 제출했던 오답 코드

i = 1
while True:
    L, P, V = list(map(int, input().split()))
    if L == 0 and P == 0 and V == 0:
        break
    answer = int(L * (V // P) + (V % P))

    print('Case ' + str(i) + ': ' + str(answer))
    i += 1

수정코드1:

i = 0
while True:
    i += 1
    L, P, V = list(map(int, input().split()))
    if L == 0 and P == 0 and V == 0:
        break

    # 나머지가 V값 보다 크면 나머지에 V값을 넣어서 계산한다.
    rest = V % P
    if rest > L:
        rest = L
    answer = int(L * (V // P) + (rest))
    print('Case ' + str(i) + ': ' + str(answer))

수정코드2:

#다른 식
i = 0
while True:
    i += 1
    L, P, V = list(map(int, input().split()))
    if L == 0 and P == 0 and V == 0:
        break

    answer = int(L * (V // P) + min((V % P), L))
    print('Case ' + str(i) + ': ' + str(answer))