저별이의 초보 코딩

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

문제

정수를 저장하는 덱(Deque)를 구현한 다음, 입력으로 주어지는 명령을 처리하는 프로그램을 작성하시오.

명령은 총 여덟 가지이다.

• push_front X: 정수 X를 덱의 앞에 넣는다.
• push_back X: 정수 X를 덱의 뒤에 넣는다.
• pop_front: 덱의 가장 앞에 있는 수를 빼고, 그 수를 출력한다. 만약, 덱에 들어있는 정수가 없는 경우에는 -1을 출력한다.
• pop_back: 덱의 가장 뒤에 있는 수를 빼고, 그 수를 출력한다. 만약, 덱에 들어있는 정수가 없는 경우에는 -1을 출력한다.
• size: 덱에 들어있는 정수의 개수를 출력한다.
• empty: 덱이 비어있으면 1을, 아니면 0을 출력한다.
• front: 덱의 가장 앞에 있는 정수를 출력한다. 만약 덱에 들어있는 정수가 없는 경우에는 -1을 출력한다.
• back: 덱의 가장 뒤에 있는 정수를 출력한다. 만약 덱에 들어있는 정수가 없는 경우에는 -1을 출력한다.

입력

첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 않은 명령이 주어지는 경우는 없다.

출력

출력해야하는 명령이 주어질 때마다, 한 줄에 하나씩 출력한다.

예제 입력

15
push_back 1
push_front 2
front
back
size
empty
pop_front
pop_back
pop_front
size
empty
pop_back
push_front 3
empty
front

예제 출력

2
1
2
0
2
1
-1
0
1
-1
0
3

코드 및 설명

from collections import deque
import sys
case=deque()
n=int(sys.stdin.readline())
for i in range(n):
    tell=list(sys.stdin.readline().split())
    #print(list)
    if tell[0]=='push_front':
        case.appendleft(tell[1])
    elif tell[0]=='push_back':
        case.append(tell[1])
    elif tell[0]=='pop_front':
        if len(case)!=0:
            print(case.popleft())
        else:
            print(-1)
    elif tell[0]=='pop_back':
        if len(case)!=0:
            print(case.pop())
        else:
            print(-1)
    elif tell[0]=='size':
        print(len(case))
    elif tell[0]=='empty':
        if len(case)==0:
            print(1)
        else:
            print(0)
    elif tell[0]=='front':
        if len(case)!=0:
            print(case[0])
        else:
            print(-1)
    elif tell[0]=='back':
        if len(case)!=0:
            print(case[-1])
        else:
            print(-1)

이 문제는 덱의 개념을 익히는 문제라고 볼 수 있다.

처음에 덱이라는 개념이 생소하긴 했는데 찾아보니 디큐의 형식을 따르되 일부 코드만 알면 되는 문제였다.

일단 from collections import deque 명령어를 통해 디큐를 만들 수 있도록 하고 import sys를 해주었다.

입력을 받을 때 시간 초과가 났기 때문에 input이 아닌 sys.stdin.readline()을 하는 것이 맞다는 생각이 들었다.

또한 tell을 입력 받을때 명령어와 숫자 분리를 위해 리스트를 선택했다. 띄어쓰기로 구분되는 방식이다.

문제는 앞의 스택, 큐 기본 문제와 다르지는 않았다.

먼저 push_front 명령어를 보게 되면 덱의 앞쪽에 넣으라는 것을 볼 수 있다.

여기서 .appendleft를 통해 뒤쪽이 아닌 덱의 앞쪽으로(가로로 보면 왼쪽에) 배치하였다.

그리고 push_back은 일반적인 숫자 추가(가로로 보면 오른쪽에) 배치이므로 append를 통해 넣어주었다.

pop_front 역시 덱의 앞쪽의 숫자를 뽑는 방식이므로 길이를 재준 뒤 0이 아니라면 .popleft를 이용해 숫자를 뽑아주었다. pop_back도 마찬가지로 숫자를 빼는 것이므로 오른쪽에서 뽑기 위해 pop을 이요해 뽑아주었다.

size를 재주는 것은 파이썬의 기본 문법인 len(리스트)를 이용해 길이를 재주어 출력해주었고 empty도 마찬가지로 길이를 재준 뒤 0인지 아닌지로 출력 명령을 따라주었다.

마지막으로 front와 back에서는 리스트에서 앞쪽,뒤쪽 숫자를 출력하는 것이므로 front는 tell 배열의 앞인 0번째 숫자를 출력하게 하였고 뒤쪽은 정확한 길이를 해서 빼주어도 되지만 깔끔하게 배열에서 -1위치를 출력하도록 하였다.

이 문제는 덱의 개념을 학습하고 이해하는 데에 도움이 되는 문제라는 생각이 들었다. 

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

2
3
hat headgear
sunglasses eyewear
turban headgear
3
mask face
sunglasses face
makeup face

5
3

코드 및 설명

n=int(input())
for i in range(n):
    m=int(input())
    ctype={}#각 타입 수 저장 딕셔너리
    for j in range(m):
        name,type=input().split()
        if type in ctype:
            ctype[type].append(name)
        else:
            ctype[type]=[name]
    cnt=1

    for k in ctype:
        cnt*=(len(ctype[k])+1)
    print(cnt-1)

오랜만에 딕셔너리를 이용한 문제.

같은 거를 처리해주어야 하기 때문에 리스트보다는 딕셔너리가 낫다고 판단했는데 그 방식이 헷갈렸던 문제

처음에는 []로 해서 추가해주고 안에 키가 존재한다면 append를 통해 ()에 변수를 넣어서 처리를 해 주어야 한다.

그리고 경우의 수를 구하는 식이 중요한데

식은

각 종류 키의 길이+1을 해서 다 곱해주어야 한다.

이 이유는 하나만 입어도 된다고 했기 때문.

그리고 알몸인 상태는 빼주어야 하므로 전체에서 -1을 해주기

마지막으로 그 전체 횟수를 출력해주면 끝!

이 문제 역시 각 시도마다 출력을 해주어야 해서 for문 안에서 처리를 해주었다.

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

앞에 나오는 최소공배수와 최대공약수 구하기 문제는 쉽게 풀었다.

일반적으로 나오는 수학원리에 의해서 말이다.

이 문제는 조금 다르다.

이 문제는 유클리드 호제법을 활용하라고 한다.

먼저 문제를 살펴보자.

3
1 45000
6 10
13 17

45000
30
221

코드 및 설명

이렇게 문제가 제시 되었다.

코드를 보면서 하나 하나 풀어나가보자

cnt=int(input())
def BResult(n1, n2):
    if(n1%n2==0):
        return n2
    else:
        return BResult(n2,n1%n2)
def SResult(n1, n2):
    return int(n1*n2/BResult(n1,n2))
for _ in range(cnt):
    n1,n2=map(int,input().split())
    #if(n1<n2):
    #    n1,n2=n2,n1
    print(SResult(n1,n2))

이 문제를 재귀함수로 풀었다.

처음에 이해가 잘 안되서 다른 사람의 다른 프로그래밍 언어를 보면서 고쳐나간 코드이다.

일단 함수를 두개 선언했다. 최소공배수 문제인데 유클리드 호제법에서는 최대공약수를 바탕으로 최소공배수를 구할 수 있기 때문이다. 최대공약수를 BResult라고 함수를 만들었고 최소공배수를 SResult라고 만들어주었다.

여기서 다른 것 보다는 최대공약수 구하는 과정을 명확히 해야 할 필요가 있다.

유클리드 호제법은 n1,n2가 있다면 n1%n2가 0이 될때까지 무한히 재귀를 해주어야 하는 것이다. 그렇게 해서 n2를 리턴해준다. 그렇지 않는다면 n1의 자리에 n2의 값을 옮겨넣고 n2자리에는 나머지 값인 n1%n2값을 넣어준다.

이렇게 자리이동이 일어나게 된다. 

원리를 알아봤으니 최소 공배수를 구하는 과정을 알아보도록 하자

최소공배수를 유클리드 호제법으로 풀려고 한다면 n1*n2/(n1,n2의 최대공약수)가 식이라고 한다. 그래서 n1,n2와 함께 기존에 만들었던 함수인 BResult를 호출해서 만든 뒤 그 값을 리턴해주는 형태로 만들었다. 

리턴을 할 때 나는 int형으로 바뀌는 것을 포함시켰는데 그 이유는 나누기로 인해 소수점이 표시되었기 때문이다.

출력 예시에서는 int형이기에 이렇게 바꿔주었고 그렇게 리턴한 값을 메인에서 출력하도록 해주었다.

여기서는 유클리드 호제법이 무엇이고 어떻게 풀어나가야 하는지 설계를 하는 것이 중요한 문제인것 같다.

나의 결론은 유클리드 호제법은

n1,n2의 나머지 값이 0이될때까지 반복해서 계산해주는 것

이라고 생각한다. 아직 완벽하게 유클리드 호제법을 이해하지는 못했지만 코드를 짜면서 생각한 결과이다.