import sys
n, m = map(int, input().split())
answer = n * (n - 1) * (n - 2) // 6
nomat = [set() for _ in range(n)]
for _ in range(m):
a, b = map(int, sys.stdin.readline().split())
answer -= (n-2) - len(nomat[a-1] | nomat[b-1])
nomat[a-1].add(b)
nomat[b-1].add(a)
print(answer)
Idea
초기 answer 값은 \( {}_n \mathrm {C}_3 \) 을 수로 나타낸 것이다.
nomat 리스트에는 각 맛 별로 조합이 좋지 않은 맛을 넣는다.
2 가지가 정해진 상황에서 나머지 한 가지 맛을 고르는 경우의 수는 n - 2 이다.
그 전에 경우의 수에서 없앤 경우의 수는 합집합의 길이가 된다.
예제 입력을 넣었을 때를 예시로 들면 다음과 같다.
1. 모든 경우의 수는 5가지 맛 중 3가지를 뽑는 경우로 총 10이다.
2. 처음 (1, 2, X) 를 뽑는 경우의 수는 3가지이므로 전체 경우의 수에서 3을 빼준다.
3. (3, 4, X) 를 뽑는 경우의 수 중 전에 뽑은 경우가 없으므로 `nomat\[2\]`와 `nomat\[3\]`의 합집합의 길이는 0이다.
4. (1, 3, X) 를 뽑는 경우에는 (1, 2, 3) 인 경우와 (1, 3, 4) 인 경우를 그 전의 입력에서 뺐으므로 전체 경우의 수에서 1만 빼준다.
처음에 코드 제출했을 때는 파이썬 언어에서 시간 순위 1등이었는데 글 적을 때 되니까 밀려났다.
스택(Stack)은 마지막에 들어온 데이터가 가장 먼저 나가게 되는 후입선출(LIFO)의 자료구조이다. 스택도 결국에는 리스트의 특별한 케이스일 뿐이다. 입력과 출력이 한 쪽 끝단에서만 이루어진다.
스택의 구조
스택은 가장 위의 데이터를 알리는 top, 스택에 데이터를 삽입하는 push, top의 데이터를 내보내는 pop함수가 기본적인 구성이다. 이 외에도 peak나 is_empty를 구현하기도 하지만 이건 부수적인 것일 뿐이다.
Push(item)
push는 아이템을 스택에 삽입하는 함수이다. top은 1 증가시키고 top이 가리키는 위치에 아이템을 저장한다.
Pop()
pop은 아이템을 스택에서 꺼내는 함수이다. 단순 참조가 아니라 스택에서 아예 나오게 되는 것이다. top이 가리키는 위치의 아이템을 꺼낸 후 top을 1 감소시킨다.
두 함수 모두 시간 복잡도는 O(1)이고 스택은 원하는 아이템을 찾을 때는 top에서 부터 차례대로 찾아야해서 random 접근이 불가능하다.
스택의 예시
스택을 쉽게 설명하기 위해서 스택은 상자, 데이터는 상자와 너비가 같은 책이라고 예시를 든다 (책은 항상 눕혀서 상자에 넣는다). Top은 상자의 위에서 확인하는 것이라 생각한다.
스택이라는 상자에 처음 위에서 바라보면 상자의 밑바닥을 확인할 수 있다. 스택에 처음에는 자료구조라는 책을 넣는다. 상자를 위에서 봤을 때 우리는 자료구조가 있다는 것을 확인할 수 있다. 그 다음 운영체제 책을 넣고 컴퓨터 구조 책을 넣는다. 이 때 상자의 위에서 볼 수 있는 것은 컴퓨터 구조이다. Stack의 Top이 가리키는 것이 컴퓨터 구조라는 의미이다.
상자에서 우리가 꺼낼 수 있는 책은 마지막에 넣은 컴퓨터 구조이고 다른 책을 넣을 수 있는 공간 역시 컴퓨터 구조 위이다. 우리는 상자에서 컴퓨터구조, 운영체제, 자료구조 순으로 꺼낼 수 있으며 위에서 봤을 때 상자의 밑바닥이 보이면 책을 꺼내는 것이 불가능해진다.
빈 상자와 넣을 책이 3권일 때자료구조 책을 상자에 넣었을 때모든 책을 다 넣은 상태
상자에 자료구조가 있는 지 확인하려면 컴퓨터 구조 책부터 순서대로 꺼내가면서 확인을 해야한다.
Stack의 구현
이론적인 Stack (list자료형의 append(), pop() 사용하지 않음)
주소에 의한 참조가 가능하다는 조건에서 만들기 위해 dictionary 자료형을 사용했습니다. del 함수는 사전 자료형에서 시간복잡도가 1입니다.
class Stack:
def __init__(self): # 스택의 정의
self.stack = dict()
self.top = -1
def push(self, data):
self.top += 1
self.stack[self.top] = data
def pop(self):
if self.is_empty(): # 스택이 비었으면 pop이 불가능
return "Stack is Empty"
tmp = self.stack[self.top]
del self.stack[self.top]
self.top -= 1
return tmp
def size(self):
return self.top+1
def is_empty(self): # stack이 비어있는지 확인
if self.top == -1:
return True
else:
return False
def peak(self): # top이 가리키는 값
if not self.is_empty():
return self.stack[self.top]
else:
return "Stack is Empty"
def __repr__(self):
return repr(self.stack)
위의 코드는 이론적인 부분을 확인하기 위한 코드로 실제 파이썬에서는 list 자료형의 pop 과 append를 이용하여 구현하는 것이 쉽습니다.
Stack 객체 구현 (list자료형 pop(), append() 사용 )
class Stack:
def __init__(self):
self.stack = []
self.top = -1
def push(self, data):
self.stack.append(data)
self.top += 1
def pop(self):
if self.is_empty():
return "Stack is Empty"
self.top -= 1
return self.stack.pop()
def size(self):
return len(self.stack)
def is_empty(self):
if not self.stack:
return True
else:
return False
def peak(self):
if not self.is_empty():
return self.stack[-1]
else:
return "Stack is Empty"
def __repr__(self):
return repr(self.stack)
확인 코드 결과
파이썬에서 스택을 굳이 직접 구현해야하는가?
파이썬의 list자료형은 위의 예제에서 봤듯이 pop()함수가 사용가능하고 push대신 append() 함수를 사용하면 스택처럼 리스트의 사용이 가능하다. 두 함수 모두 시간 복잡도는 O(1)이기 때문에 스택에서의 구현과 동일하다. top 또한 len - 1로, peak 또한 list[-1] 로 구현이 가능한 만큼 제공되는 함수를 사용하는 것이 유리하다고 생각한다.
찾는 item이 있는지 확인하는 부분이 리스트는 앞에서 확인하지만 스택은 뒤에서부터 확인한다는 점이 조금 다르긴 할 것이다.
import sys
def recursive(x, y, count):
if count == 5:
number.append(numbers[x][y])
answer_set.add(tuple(number))
else:
number.append(numbers[x][y])
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
if -1 < nx < 5 and -1 < ny < 5:
recursive(nx, ny, count + 1)
number.pop()
numbers = [sys.stdin.readline().split() for _ in range(5)]
dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]
answer_set = set()
number = []
for r in range(5):
for c in range(5):
recursive(r, c, 0)
print(len(answer_set))
Idea
각각의 시작점에서 가능한 방향으로 모두 방문하며 list에 숫자를 추가
숫자 리스트를 집합 자료형에 입력함으로써 중복을 제거
재귀함수가 호출 되고나서 입력받은 리스트와 같은 새로운 리스트를 만들지 않고 기존의 리스트를 append와 pop을 사용해서 스택으로 사용
집합의 요소로는 리스트가 들어갈 수 없다. 그래서 집합에 add를 할 때 리스트를 tuple이나 str로 변환하여 입력해주어야 했다. 집합은 직접 수정이 불가능한 자료형인데 리스트는 주소에 의한 수정이 가능해져서가 아닐까 추측해본다.
