def solution(citations): answer = 0 citations.sort(reverse=True) h = citations[0] for h in range(citations[0], 0, -1): cnt_up = 0 for c in citations : if c >= h : cnt_up += 1 if cnt_up >= h : answer = h break return answer 처음에는 문제 그대로 풀이하였다. 근데 이중 for문이 맘에 안 들었고, 다른 풀이 방법이 있을 것 같았다. def solution(citations) : citations.sort() l = len(citations) for i in range(l) : if citations[i] >= l-i : return ..

문제가 길다... 백트래킹 방식으로 풀 수 있다. N-queen문제의 접근 방법과 비슷한데, 가로, 세로, 3x3 박스 각각 체크할 수 있도록 체크 배열을 만들면 된다. 1. 가로를 체크하는 check_row 배열의 경우 몇번째 줄에 어떤 숫자가 들어갔는지를 체크하도록 해야 한다. 즉, check_row[3][2] = True 라면, 네번째 줄 (첫번째 줄은 0번 index니까)에 2라는 숫자가 존재한다는 것. 2. 세로를 체크하는 check_col 배열도 동일하다. 3. 3x3 박스를 체크하는 check_box 배열의 경우 몇번째 box에 어떤 숫자가 들어갔는지를 체크해야 한다. 몇번째 박스인지를 어떻게 알까? \ 3개씩 끊어주면 되니까 3으로 나눈 값을 잘 사용하면 나타낼 수 있을 것 같다. 난 각 ..

백트래킹 문제이다. 문제의 핵심은 사이클이 만들어지기 때문에 어디서 시작해도 같은 사이클을 가지게 되니 시작 지점을 고정해놓아도 상관이 없다는 것이다. 따라서 무조건 0으로 시작하도록 고정하였다. 또 하나 내가 실수한 점이 있는데, 함수 안에서 cost 함수를 대입연산자를 사용하여 더해지는 경우, 그 함수 내에서 cost 값이 i가 변할 때마다 누적된다는 것을 간과하였다. 이 문제를 해결하기 위해서는 cost값에 대입연산자를 사용하여 더하지 말고 함수 호출 시에만 더해주어야 한다. import sys input = sys.stdin.readline def get_routine(start, cnt, cost) : global min_cost if cost > min_cost : return if cnt =..

Backtracking으로 풀 수 있다. 문제에는 없지만 체스 퀸 이동에 대해서 알고 있어야 한다. 퀸은 상하좌우, 대각선 어느 방향으로든 이동할 수 있기에 공격할 수 없게 놓으기 위해서는 새로 놓고자 하는 퀸이 이미 놓여진 퀸들과 같은 열이나, 행에 있어서도 안되고 대각선 경로에 존재해서도 안된다. 여기서 이미 놓여진 퀸들과 "같은 열이나, 행에 있어서는 안 된다"는 것이 핵심이다. 그럼 각 행에는 퀸이 한개밖에 올 수 없다는 소리이므로 각 행에 퀸을 하나씩 놓아가면서 탐색할 수 있다. 예를 들어 0번 행의 0번째 열에 1번 퀸을 놓았다면, 1번 행에서는 1번째 열과 대각선 경로에 퀸을 놓지 못한다. 2번째 열에 퀸을 놓았다고 가정하면 대각선 경로와 겹치게 되므로 3번 열에 2번 퀸을 놓을 수 있을 것..

처음엔 단순히 for문 돌려가면서 풀었는데, 문제를 읽으면서 놓친 부분이 꽤나 많았다. 예를 들어 예제 입력 4 처럼 n이 0인 경우에는 무조건 1이 나와야 한다는 점이나, 등수는 p보다 작지만 동점자로 인해 랭킹 리스트에 들지 못할 수 있다는 점 등등... "틀렸습니다"를 확인해가며 고쳤다. 코드는 아래와 같다. import sys input = sys.stdin.readline def get_rank(new, scores, p) : cnt = 0 before_rank = 1 for i, score in enumerate(scores) : if cnt == p : return -1 if new > score : if scores[i-1] == new : return before_rank else : r..

사실 어려운 문제는 아니다. 정리하는 이유는 바보같이 틀려가지고.... ㅋㅋ 처음에 문제만 보고 음~ 쉽군~ 하면서 그냥 a**b를 계산했고 당연히 시간초과가 떴음 당연함 제곱을 바로 해주면 b의 범위도 크고 수의 크기도 너무 커지기 때문! 그래서 제곱할 때 일의 자리 끼리의 규칙이 있다는 걸 사용하기로 했다. 2부터 9까지 값을 거듭제곱 했을 때의 일의자리 패턴이 4개 단위로 반복되거나, 2개 단위로 반복되거나, 1개 단위로 반복되는 것을 알아낼 수 있었다. 그럼 숫자를 다섯제곱 했을 때의 일의 자릿수와 일제곱 했을 때의 일의 자릿수가 같을 수 밖에 없다는 소리다. 여섯제곱 했을 때의 일의 자릿수와 제곱 했을 때의 일의 자릿수가 같을 수 밖에 없다는 소리다. 위의 방법을 사용한 코드는 이렇다. impo..

문제 자체는 어렵지 않으나, 새로운 방법이 있어 기록해두고자 작성한다. 처음엔 정말 직관적으로 set 자료형을 사용해서 정직하게 구현하였다. # 집합 import sys input = sys.stdin.readline def set_add(s, x) : s.add(x) return s def set_remove(s, x) : try : s.remove(x) return s except : return s def set_check(s, x) : if x in s : print("1") else : print("0") def set_toggle(s, x) : if x in s : s.remove(x) else : s.add(x) return s def set_all() : return {i for i in ..

1. 처음 생각한 방법 - 검은색으로 시작할지 흰색으로 시작할지 알 수 없으니 두 개의 샘플은 만들어놓고 각 경우의 새로 칠하는 횟수를 비교하여 더 적은 횟수인 경우를 남긴다. import sys input = sys.stdin.readline lines1 = ["WBWBWBWB", "BWBWBWBW"] lines2 = ["BWBWBWBW", "WBWBWBWB"] def calc_paint(r_start, c_start, tiles) : count_1 = 0 count_2 = 0 for i in range(r_start, r_start+8, 1) : for j in range(c_start, c_start+8, 1) : if tiles[i][j] != lines1[(i%8)%2][j%8] : count_..