ayoung0073 / ars-backend Goto Github PK

{
    status: 200,
    message: "검색 결과입니다.",
    data: [{
            title: "2878. 캔디캔디",
            step: 5,
            link: "https://www.acmicpc.net/problem/2878",
            createdDate: "2021-07-27",
            content: "진짜 너무 어려운 문제 문제 접근조차 어떻게 해야할지.. ㅠㅠ 막막했던 문제이다. 우선 사탕을 공평하게 나눠주도록 짜야한다. ``` import sys input = sys.stdin.readline m, n = map(int, input().split()) candy = [] for _ in range(n): candy.append(int(input())) candy.sort() no = sum(candy) - m # 사탕 못 받는 개수 ans = 0 # 최솟값으로 만들자 # 받지 못하는 사탕의 개수가 고르게 분포되는 것이 최적이다. -> 공평하게 나누도록 한다!!! for i in range(n): # 요구하는 사탕 개수만큼 못 받을지, 남은 사람들과 똑같이 못 받을지 결정한다. # 둘 중 더 많이 받을 수 있는 것을 선택한다. 둘 중 더 작은 값을 못 받도록 한다. num = min(candy[i], no // (n-i)) ans += num * num # 분노 게이지 제곱 no -= num print(ans % (2 ** 64)) ``` 먼저 원하는 사탕의 개수를 기준으로 오름차순 정렬을 한다. 원하는 개수가 적은 사람들을 그만큼 먼저 나눠주도록 한다. 나눠주지 못하는 사탕의 개수 변수를 `no`라고 설정하고, 자신보다 더 사탕을 많이 요구하는 사람들과 공평하게 사탕을 못 받을지, 요구하는 사탕 개수만큼 못 받을지를 결정한다. 둘 중 더 작은 값을 못 받아야 분노 게이지가 최소가 될 것이다. 그 후 `no -= [더 작은 값]`을 계산한다. 이렇게 모든 반복을 돌면 된다. 나는 생각을 못했다. .. 처음에 다 받거나 1개를 못 받아야지 가장 적게 되지 않을까? 하고 사탕을 하나씩 빼고 줘서 `ans - [남은 사탕의 개수]` 를 하려고 했지만 .. ㅋㅋ 네.. 이 문제는 내일 봐도 모를 것 같은.. 그런 느낌. ㅠㅠ 열심히 해야지.​[참고 링크](https://maivve.tistory.com/152)"
        },
        {
            title: "Passport Control",
            step: 2,
            link: "https://www.acmicpc.net/problem/16288",
            createdDate: "2021-07-26",
            content: "해당 큐(줄) 안에서 **오름차순 정렬**이 되어 있다면 YES, 정렬을 할 수 없다면 NO를 출력하면 된다. ``` import sys input = sys.stdin.readline n, k = map(int, input().split()) order = list(map(int, input().split())) max_arr = [0 for _ in range(k)] for i in range(n): check = False for j in range(k):   if order[i] > max_arr[j]:     max_arr[j] = order[i]     check = True     break if not check:   print("
            NO ")   exit(0) print("
            YES ") ``` 음 아이디어만 떠올린다면 쉽게 풀 수 있는 문제 알코리즘에서 듣고 풀 수 있었던 건지? 그니까 나중에 다시 풀어봐야할 듯하다. 근데 풀면서 한 가지 궁금한 게 있었다. 그냥 반복문을 돌고 바로 해당 최댓값보다 크면 갱신하고 다음 순서로 넘어가면 ``` 4 2 2 6 8 5 ``` 일 때는 "
            NO "가 출력되는 것 아닐까? 했지만 내 실수였다. 나는 2와 6이 다른 창구로 갈 줄 알았는데 생각해보니 한 창구에 주르륵 서겠구나 라는 것을 YES가 출력되고 바로 깨달았다."
        },
        {
            title: "신입사원",
            step: 3,
            link: "https://www.acmicpc.net/problem/1946",
            createdDate: "2021-07-22",
            content: "- 처음 코드 (시간 초과) ``` import sys input = sys.stdin.readline t = int(input()) for _ in range(t): ans = 1 n = int(input()) score = [] for _ in range(n):   score.append(list(map(int, input().split()))) score.sort(key=lambda x : (x[0], x[1])) for i in range(1, n):   check = True   for j in range(0, i):     if score[j][0] != score[i][0]:       if score[j][1] < score[i][1]:         check = False         break   if check:     ans += 1 print(ans) ``` 나는 계속 이중 for문으로 코드를 작성해서 계속 시간 초과가 났다. 저번에 푼 기록이 있어서 봤는데 두세번 보고 이해를 할 수 있었다. 이중 for문을 하지 않아도 충분히 신입사원이 가능한지 판별할 수 있다. 서류를 기준으로 먼저 오름차순을 하여, 그 중 순위가 가장 높은 사람부터 면접 전형 순위를 가장 높다고 일단 두는 것이다. 그 다음 사람을 비교할 때(서류 순위가 더 낮은 사람), 면접 점수가 더 높다면 그 사람은 신입사원이 될 수 있는 조건이 되고 면접 순위를 갱신한다. 이 과정을 반복하면 된다. - 최종 코드 ``` import sys input = sys.stdin.readline t = int(input()) for _ in range(t): ans = 1 n = int(input()) score = [] for _ in range(n):   score.append(list(map(int, input().split()))) score.sort(key=lambda x : x[0]) comp = score[0][1] for i in range(1, n):   if score[i][1] < comp:     comp = score[i][1]     ans += 1 print(ans) ``` 메모리: 50488KB, 시간: 4680ms로 통과!"
        },
        {
            title: "짝지어 제거하기",
            step: 1,
            link: "https://programmers.co.kr/learn/courses/30/lessons/12973",
            createdDate: "2021-07-15",
            content: "```python from collections import deque def solution(s):   q = deque(s[0])   print(q)   for i in range(1, len(s)):       if q and q[len(q) - 1] == s[i]:           q.pop()       else:           q.append(s[i])   if q:       return 0   else:       return 1 ``` 처음엔 단순 비교를 통해서 답을 구하려고 했다 배열을 하나 선언 (` list(s)`)하여 짝이 있는 경우 두 원소를 제거하고 다시 비교하는 식으로 답을 구하려고 했지만 실패 대신 deque 라이브러리를 이용하였다. 큐의 마지막 원소와 큐에 넣으려는 s의 문자가 같으면 큐의 마지막 원소를 pop 다르면 append를 한다. 주어진 예시 `baabaa`를 살펴보자. ``` 1. q = [b] 2. q = [b, a] # 큐의 마지막 원소 'b' 와 s[1] = 'a'를 비교 -> 다름 -> q.append('a') 3. q = [b]   # 큐의 마지막 원소 'a' 와 s[2] = 'a'를 비교 -> 같다 -> q.pop() 4. q = []     # 과정 반복 5. q = [a] 6. q = [] ``` 이렇게 큐를 이용하면 효율성을 높일 수 있다."
        }
    ]
}