Awesome

programmers.co.kr/learn/courses/30/lessons/42576

from collections import Counter


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

Level 1 문제라 그런지 코드가 매우 짧다. 파이썬으로 이 문제를 푸는 방법은 두 가지가 있다. 완전탐색, 그리고 딕셔너리끼리의 뺄셈.

완전탐색은 for문 안에 if ~ in 문을 넣어서 풀면 된다.

for c in completion:
    if c in participant:
        participant.remove(c)
return participant[0]

participant는 참가자 전원의 리스트이고 completion은 완주한 선수들의 리스트이다. participant보다 한 명이 적다.

졸려서 그랬는지 처음에는 participant를 순회하려고 했다. 그렇게 하면 participant를 순회하는 도중에 participant에서 remove를 하게 되어 에러가 발생한다. 리스트를 순회하는 도중에 값의 변경이 일어나면 안되기 때문이다.

대신에, completion을 순회하면서 그 값이 participant에 존재하면 participant에서 remove해주는 방식으로 해야 한다.

즉, 완주한 선수들의 이름을 하나씩 부르면서 참가자 전원 리스트에서 하나씩 소거해 나가는 것이다.

완주한 선수들의 이름을 모두 다 불렀는데도 참가자 리스트에 남아있는 선수가 바로 완주하지 못한 선수가 된다.

아무튼 설명이 길었지만 결론은 완전탐색 방식으로 하면 시간이 O(n^2)이 걸리게 되어 시간초과가 난다.

그럼 어떻게 해야 할까? 파이썬에서는 collections 모듈에서 Counter 함수를 제공한다.

Counter 함수에는 여러가지 사용법이 있는데, 매개변수로 리스트를 넣어주면 {값: 갯수}의 형태의 딕셔너리를 반환한다.

ex) collections.Counter(["leo", "kiki", "eden"]) ----> {"leo": 1, "kiki": 1, "eden": 1}

중요한 점이 여기서 등장한다. 원래 파이썬에서 set과는 달리 딕셔너리끼리 뺄셈을 지원하지 않는다.

그런데 Counter로 반환된 딕셔너리 모양의 오브젝트끼리는 더하기, 빼기, 차집합, 합집합이 가능하다.

따라서, 참가자 전원 Counter에서 완주한 선수 Counter를 빼 주면 이름이 중복되는 선수까지 다 계산해서 최종적으로 완주하지 못한 선수가 리턴된다.

맨 처음에 올린 코드처럼!

Counter 개념을 익혀놓자.

http://boj.kr/2252 

위상 정렬 기본 문제이다.

위상 정렬이 무엇인가 하면, 어떤 유향 그래프가 있을 때 선후 관계를 해치지 않도록 노드를 정렬하는 것이다. 

당연하게도 이 유향 그래프에는 사이클이 있으면 안 된다. 사이클이 있으면 선후 관계라는 게 있을 수가 없기 때문이다.

위상 정렬을 하는 방법은 두 가지가 있다. 하나는 재귀를 사용하는 방법, 다른 하나는 재귀를 사용하는 방법이다.

조금 더 직관적이지만 구현이 복잡한 노 재귀 방법부터 보자.

다음과 같은 사이클이 없는 유향그래프가 있고, 정렬된 배열을 S라고 하자.

첫 번째 방법은 한 마디로 설명하면 '시작 노드를 그래프에서 빼서 순서대로 놓는 것'이다.

시작노드들이란 그 노드로 들어오는 간선이 없는 노드들을 말한다.

즉 인접 리스트 등에서 어떤 노드보다 뒤에 있다고 설명되지 않는 노드들이다.

초기 그래프와 정렬된(텅 빈) 배열 S이다.

여기서 시작노드들은 1과 5이다. 노드 1이나 5로 들어오는 간선이 없기 때문에 1과 5는 시작 노드이다.

위상 정렬을 하기 위해서는 이 시작 노드 중 하나를 선택해서, 그 노드와 그 노드로부터 출발하는 진출 간선을 모두 삭제한다. 1을 선택해보자.

1과 1의 진출 간선이 삭제되었다. 그리고 1이 정렬된 배열 S의 맨 뒤에 추가되었다. 

간단하게도 이것을 계속 반복하면 된다.

삭제된 1의 진출 간선과 연결되어 있던 2는 진입 간선을 하나 잃었다. (1의 진출 간선=2의 진입 간선)

이제 진입 간선이 없는 시작 노드는 2, 5가 되었다. 다시 그 중에서 하나를 선택해 그 노드와 진출 간선을 모두 삭제한다. 이번에는 2를 선택해보자.

2를 삭제하고 2로부터 출발하는 진출 간선들을 모두 삭제했다. 그리고 2를 정렬된 배열 S의 맨 뒤에 추가했다.

이제 시작 노드는 5 하나이다.

5를 삭제하고 배열 S에 추가했고, 5로부터 출발하는 5의 진출 간선들을 모두 삭제했다. 

이제 시작 노드는 4와 6이다. 이 중 4를 선택해보자.

4를 삭제하고 배열 S에 추가한 뒤, 4의 진출 간선들을 모두 삭제했다. 

이제 시작 노드는 6 하나 뿐이다.

6을 삭제하고 배열 S에 추가했다. 그리고 배열 S에 추가했다.

이제 시작 노드는 3 하나 뿐이다.

3을 삭제하고 배열 S의 맨 뒤에 추가했다. 이제 남은 노드가 없으므로 배열 S가 위상 정렬이 완료된 배열이 되었다.

import sys


def solution():
    for _ in range(N):
        u = start_v.pop()  # 시작 노드 중 하나를 꺼낸다
        answer.append(u+1)  # 배열의 맨 뒤에 삽입
        for node in out[u]:  # 노드 u와 연결된 간선들을 삭제하면 그 간선들과 연결된 노드들의 진입 간선 수가 줄어든다
            in_num[node] -= 1
            if in_num[node] == 0:  # 진입 간선이 0이 된 간선은 시작 노드 배열에 추가
                start_v.append(node)


answer = []
input = sys.stdin.readline
N, M = map(int, input().split())  # N = 학생수, M = 비교횟수
start_v = []  # 진입 간선이 0인 시작 노드
in_num = [0 for _ in range(N)]  # 진입 간선의 수. in_num=0인 노드가 시작 노드가 된다

out = [[] for _ in range(N)]  # 모든 노드에 대해 선후 관계를 정리한 배열

# 노드들의 선후 관계가 입력으로 들어온다. 배열의 인덱스는 0부터 시작이므로 각각 1씩 마이너스해서 배열에 담는다.
for _ in range(M):
    a, b = map(int, input().split())
    out[a-1].append(b-1)
    in_num[b-1] += 1

for idx, num in enumerate(in_num):
    if num == 0:
        start_v.append(idx)  # 진입간선이 0인 정점들은 먼저 줄세운다

solution()

for a in answer:
    print(a, end=' ')

두 번째 방법은 재귀를 이용하는 것이다. 모습이 DFS를 닮았기 때문에 DFS 방법이라고 한다.

이번에는 아무 노드나 선택한 후, 그 노드와 연결된 노드들을 재귀로 찾아서 배열의 맨 앞에 삽입하면 된다.

import sys
from collections import deque


def solution():
    for i in range(N):
        if not visited[i]:
            dfs(i)


def dfs(v):
    visited[v] = True
    for next_v in out[v]:
        if not visited[next_v]:
            dfs(next_v)
    answer.appendleft(v+1)


answer = deque()
input = sys.stdin.readline
N, M = map(int, input().split())  # N = 학생수, M = 비교횟수
visited = [False for _ in range(N)]
out = [[] for _ in range(N)]  # 인접 리스트. 진출 간선들을 정리한 리스트.
for _ in range(M):
    a, b = map(int, input().split())
    out[a-1].append(b-1)
    
solution()
for a in answer:
    print(a, end=' ')

a = [1, 2, 3, 4]
b = [5, 6, 7, 8]
a = b  # 얕은 복사(주소 같음)
print("a의 주소:", id(a))
print("b의 주소:", id(b))

b = [100, 100, 100, 100]  # b를 새로운 객체로 대체하면

print("a:", a)
print("a의 주소:", id(a))  # a의 값에는 영향이 없고,
print("b의 주소:", id(b))  # b는[100, 100, 100, 100] 이라는 새로운 객체를 가리킴


# 평범한 shallow copy를 보여주는 예
a = b
b[0] = 0
print(a)

a = b를 하면, a -> b -> [리스트]가 아니라

a -> [리스트] <- b 가 되므로, 

b에게 다른 값을 넣어도

a -> [리스트]

b -> [다른리스트]

가 되는 거다.

https://www.acmicpc.net/problem/2003

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int main(void) {
	int n, m;
	scanf("%d %d\n", &n, &m);
	int arr[n];

	for (int i=0; i<n; i++) {
		scanf("%d", &arr[i]);
	}

	int start = 0, end = 0, sum = 0, count = 0;

	/*
	while (start < n) {
		if (sum >= m) {
			sum -= arr[start];
			start ++;
		}
		else if (end == n) {
			break; // 이미 end가 n까지 왔다는 것은 sum이 작다는 것
		}
		else {
			sum += arr[end];
			end ++;  // end가 가리키는 부분은 포함 안 함
		}
		if (sum == m)
			count ++;
	}
	*/

	while (start < n) {
		if (sum == m)
			count ++;
		if (sum >= m) {
			sum -= arr[start];
			start ++;
		}
		else if (end > n) {
			break;
		}
		else {
			end ++;
			sum += arr[end-1];
		}
	}

	printf("%d\n", count);
	return 0;
}