코딩묻은 디자이너

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

문제

자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.

• 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열

입력

첫째 줄에 자연수 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8)

출력

한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다.

수열은 사전 순으로 증가하는 순서로 출력해야 한다.

풀이

dfs로 수를 하나하나 넣어주면서 풀었다

python코드

# 15649 N과 M (1)
def dfs(n):
    if len(arr) == M:
        print(*arr)
        return
    else:
        for i in range(1,N+1):
            if i not in arr:
                arr.append(i)
                dfs(i)
                arr.pop()

N, M = map(int,input().split())
arr = []
dfs(1)

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

문제

김형택은 탑문고의 직원이다. 김형택은 계산대에서 계산을 하는 직원이다. 김형택은 그날 근무가 끝난 후에, 오늘 판매한 책의 제목을 보면서 가장 많이 팔린 책의 제목을 칠판에 써놓는 일도 같이 하고 있다.

오늘 하루 동안 팔린 책의 제목이 입력으로 들어왔을 때, 가장 많이 팔린 책의 제목을 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 오늘 하루 동안 팔린 책의 개수 N이 주어진다. 이 값은 1,000보다 작거나 같은 자연수이다. 둘째부터 N개의 줄에 책의 제목이 입력으로 들어온다. 책의 제목의 길이는 50보다 작거나 같고, 알파벳 소문자로만 이루어져 있다.

출력

첫째 줄에 가장 많이 팔린 책의 제목을 출력한다. 만약 가장 많이 팔린 책이 여러 개일 경우에는 사전 순으로 가장 앞서는 제목을 출력한다.

풀이

딕셔너리(해시)를 사용했고,

lambda를 통해 정렬하였다

python 코드

#1302 베스트셀러

N = int(input())
books = {}
for n in range(N):
    book = input()
    if book in books:
        books[book] += 1
    else:
        books[book] = 1
ans = sorted(books.items(), key=lambda x:(-x[1],x[0]))
print(ans[0][0])

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

문제

위대한 해커 창영이는 모든 암호를 깨는 방법을 발견했다. 그 방법은 빈도를 조사하는 것이다.

창영이는 말할 수 없는 방법을 이용해서 현우가 강산이에게 보내는 메시지를 획득했다. 이 메시지는 숫자 N개로 이루어진 수열이고, 숫자는 모두 C보다 작거나 같다. 창영이는 이 숫자를 자주 등장하는 빈도순대로 정렬하려고 한다.

만약, 수열의 두 수 X와 Y가 있을 때, X가 Y보다 수열에서 많이 등장하는 경우에는 X가 Y보다 앞에 있어야 한다. 만약, 등장하는 횟수가 같다면, 먼저 나온 것이 앞에 있어야 한다.

이렇게 정렬하는 방법을 빈도 정렬이라고 한다.

수열이 주어졌을 때, 빈도 정렬을 하는 프로그램을 작성하시오.

입력

첫째 줄에 메시지의 길이 N과 C가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ C ≤ 1,000,000,000)

둘째 줄에 메시지 수열이 주어진다.

출력

첫째 줄에 입력으로 주어진 수열을 빈도 정렬한 다음 출력한다.

풀이

딕셔너리(해시)를 통해 풀었다

리스트로 값을 받아온 후 딕셔너리에 하나하나 넣고

lambda식을 이용하여 내림차순 정렬하였다

그러면 튜플을 가진 리스트가 생성되는데

해당 리스트의 길이만큼 돌고, 또 튜플 뒤에 값 만큼 돌며 앞의 값을 출력하였다...!

python 코드

# 2910 빈도 정렬

N, C = map(int,input().split())
arr = {}
text = list(map(int,input().split()))
for i in text:
    if i in arr:
        arr[i] += 1
    else:
        arr[i] = 1
ans = sorted(arr.items(),key=lambda x:-x[1])
for i in range(len(ans)):
    for j in range(ans[i][1]):
        print(ans[i][0],end=' ')

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

문제

문자열 S가 주어졌을 때, S의 서로 다른 부분 문자열의 개수를 구하는 프로그램을 작성하시오.

부분 문자열은 S에서 연속된 일부분을 말하며, 길이가 1보다 크거나 같아야 한다.

예를 들어, ababc의 부분 문자열은 a, b, a, b, c, ab, ba, ab, bc, aba, bab, abc, abab, babc, ababc가 있고, 서로 다른것의 개수는 12개이다.

입력

첫째 줄에 문자열 S가 주어진다. S는 알파벳 소문자로만 이루어져 있고, 길이는 1,000 이하이다.

출력

첫째 줄에 S의 서로 다른 부분 문자열의 개수를 출력한다.

풀이

이번에도 역시 딕셔너리(해시)를 통해 풀었다!

처음에는 부분 문자열을 나열하는 것에 대한 고민을 했다.

'연속된'이라는 키워드가 있어서 어렵지 않게 부분 문자열의 리스트를 만들 수 있었다.

abcde라면

i가 첫 문자를, j가 뒤에 붙을 문자를 탐색하여 추가하는데

a, ab, abc, abcd, abcde, b, bc, bcd, bcde, c, cd, cde, d, de, e 이런 식으로 추가가 된다

a, b, c, d, e, ab, ... 이렇게 생각하는 것 보다 쉽게 짤 수 있었다.

처음 코드는 마지막에 set으로 중복을 제거해줬다

처음부터 set으로 받는게 더 효율 적일 것 같다고 생각했는데

처음부터 set으로 받아보니 큰 차이가 없었다

python코드

# 리스트로 받은 후 변환
S = input()
s_arr = []

for i in range(len(S)):
    text = ''
    for j in range(i,len(S)):
        text += S[j]
        s_arr.append(text)
set_arr = set(s_arr)
print(len(set_arr))

# set으로 바로 받기
S = input()
s_arr = set()

for i in range(len(S)):
    text = ''
    for j in range(i,len(S)):
        text += S[j]
        s_arr.add(text)
print(len(s_arr))

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

문제

준규는 숫자 카드 N장을 가지고 있다. 숫자 카드에는 정수가 하나 적혀있는데, 적혀있는 수는 -262보다 크거나 같고, 262보다 작거나 같다.

준규가 가지고 있는 카드가 주어졌을 때, 가장 많이 가지고 있는 정수를 구하는 프로그램을 작성하시오. 만약, 가장 많이 가지고 있는 정수가 여러 가지라면, 작은 것을 출력한다.

입력

첫째 줄에 준규가 가지고 있는 숫자 카드의 개수 N (1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개 줄에는 숫자 카드에 적혀있는 정수가 주어진다.

출력

첫째 줄에 준규가 가장 많이 가지고 있는 정수를 출력한다.

풀이

딕셔너리로 값을 받은 후 딕셔너리를 정렬하였다

lambda를 통해 정렬을 하였는데

s_cards = sorted(cards.items(),key=lambda x:x[0])
s_cards = sorted(cards.items(),key=lambda x:x[1],reverse=True)

이렇게 정렬을 했더니 시간 초과가 나왔다

s_cards = sorted(cards.items(),key=lambda x:(-x[1],x[0]))

이런식으로 lambda식에서 한번에 정렬을 할 수 있다는걸 알았다!

python 코드

import sys

N = int(input())
cards = {}

for i in range(N):
    card = int(sys.stdin.readline())
    if card in cards:
        cards[card] += 1
    else:
        cards[card] = 1
s_cards = sorted(cards.items(),key=lambda x:(-x[1],x[0]))

print(s_cards[0][0])

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

문제

총 N개의 문자열로 이루어진 집합 S가 주어진다.

입력으로 주어지는 M개의 문자열 중에서 집합 S에 포함되어 있는 것이 총 몇 개인지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 문자열의 개수 N과 M (1 ≤ N ≤ 10,000, 1 ≤ M ≤ 10,000)이 주어진다.

다음 N개의 줄에는 집합 S에 포함되어 있는 문자열들이 주어진다.

다음 M개의 줄에는 검사해야 하는 문자열들이 주어진다.

입력으로 주어지는 문자열은 알파벳 소문자로만 이루어져 있으며, 길이는 500을 넘지 않는다. 집합 S에 같은 문자열이 여러 번 주어지는 경우는 없다.

출력

첫째 줄에 M개의 문자열 중에 총 몇 개가 집합 S에 포함되어 있는지 출력한다.

풀이

딕션너리를 사용해 풀이하였다.

첫 디버깅에서 바로 답이 나와서 기쁨!

일단 S 문자열에 들어갈 값을 딕셔러니 key값으로 해서 넣고, M만큼  문자열을 받아서 key값과 일치하면 ans가 올라가게 했다.

python코드

# 14425 문자열 집합

N, M = map(int,input().split())
S = {}
ans = 0
for n in range(N):
    S[input()] = 'o'
for m in range(M):
    text = input()
    if text in S:
        ans += 1
print(ans)

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

문제

숫자 카드는 정수 하나가 적혀져 있는 카드이다. 상근이는 숫자 카드 N개를 가지고 있다. 정수 M개가 주어졌을 때, 이 수가 적혀있는 숫자 카드를 상근이가 몇 개 가지고 있는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10,000,000보다 작거나 같다.

셋째 줄에는 M(1 ≤ M ≤ 500,000)이 주어진다. 넷째 줄에는 상근이가 몇 개 가지고 있는 숫자 카드인지 구해야 할 M개의 정수가 주어지며, 이 수는 공백으로 구분되어져 있다. 이 수도 -10,000,000보다 크거나 같고, 10,000,000보다 작거나 같다.

출력

첫째 줄에 입력으로 주어진 M개의 수에 대해서, 각 수가 적힌 숫자 카드를 상근이가 몇 개 가지고 있는지를 공백으로 구분해 출력한다.

풀이

해시로 풀려고 했다.

처음에는

# 10816 숫자 카드 2

M = int(input())
cards = list(map(int,input().split()))
N = int(input())
arr = list(map(int,input().split()))
arrs = {}

for i in range(N):
    arrs[arr[i]] = 0

for i in range(M):
    if cards[i] in arrs:
        arrs[cards[i]] += 1

for i in arrs.values():
    print(i,end=' ')

이런식으로 우선 찾아야 하는 숫자를 우선 딕셔너리로 변환하고 value 값을 0을 준 다음에

가지고 있는 카드 중에서 해당 값이 있다면 += 1 을 하는 코드를 짰더니

'틀렸습니다' 가 나왔다

왜...?

그래서 가지고 있는 숫자를 숫자가 없으면 1, 있으면 +1로 만들어 딕셔너리를 가지고 있다가

찾아야 하는 숫자에 해당하면 해당 숫자를, 없다면 0을 출력하도록 바꿨더니 된다

왜...?

python코드

# 10816 숫자 카드 2

M = int(input())
cards = list(map(int,input().split()))
N = int(input())
arr = list(map(int,input().split()))
arrs = {}
# print(cards)
# print(arr)

for i in cards:
    if i in arrs:
        arrs[i] += 1
    else:
        arrs[i] = 1
for i in arr:
    if i in arrs:
        print(arrs[i], end=' ')
    else:
        print(0, end=' ')

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

문제

상근이는 세계적인 소프트웨어 회사 기글에서 일한다. 이 회사의 가장 큰 특징은 자유로운 출퇴근 시간이다. 따라서, 직원들은 반드시 9시부터 6시까지 회사에 있지 않아도 된다.

각 직원은 자기가 원할 때 출근할 수 있고, 아무때나 퇴근할 수 있다.

상근이는 모든 사람의 출입카드 시스템의 로그를 가지고 있다. 이 로그는 어떤 사람이 회사에 들어왔는지, 나갔는지가 기록되어져 있다. 로그가 주어졌을 때, 현재 회사에 있는 모든 사람을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 로그에 기록된 출입 기록의 수 n이 주어진다. (2 ≤ n ≤ 106) 다음 n개의 줄에는 출입 기록이 순서대로 주어지며, 각 사람의 이름이 주어지고 "enter"나 "leave"가 주어진다. "enter"인 경우는 출근, "leave"인 경우는 퇴근이다.

회사에는 동명이인이 없으며, 대소문자가 다른 경우에는 다른 이름이다. 사람들의 이름은 알파벳 대소문자로 구성된 5글자 이하의 문자열이다.

출력

현재 회사에 있는 사람의 이름을 사전 순의 역순으로 한 줄에 한 명씩 출력한다.

풀이

해시, 딕셔너리가 많이 많이 많이 많이 부족하다는걸 느껴서(해시 나오면 프로그래머스 1단계도 힘듦) 찾아서 풀어본 해시문제

처음부터 해시로 접근했다.

key값으로 이름을 넣고 value값으로 뭘...넣어야 하지...? 고민했는데 생각해보니 그냥 아무 값을 넣어도 될 것 같았다.

이럴거면 리스트를 써도 되지 않을까 했지만 시간 초과가 나기 때문에... 이대로 진행

keys값을 기준으로 정렬을 하고나자 리스트가 되었다...!

python 코드

# 7785 회사에 있는 사람

N = int(input())
arr = {}

for t in range(N):
    a, b = map(str,input().split())
    if b == 'enter':
        arr[a] = 'work'
    else:
        del arr[a]
arr = sorted(arr.keys(), reverse=True)
for i in arr:
    print(i)

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

문제

N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수는 모두 다른 수이다.

• N개의 자연수 중에서 M개를 고른 수열
• 같은 수를 여러 번 골라도 된다.
• 고른 수열은 비내림차순이어야 한다.
  • 길이가 K인 수열 A가 A1 ≤ A2 ≤ ... ≤ AK-1 ≤ AK를 만족하면, 비내림차순이라고 한다.

입력

첫째 줄에 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8)

둘째 줄에 N개의 수가 주어진다. 입력으로 주어지는 수는 10,000보다 작거나 같은 자연수이다.

출력

한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다.

수열은 사전 순으로 증가하는 순서로 출력해야 한다.

풀이

dfs를 통해 풀었다.

숫자는 받은 후 sort 하여 오름차순 정렬하였으며, 인덱스로 접근했다

python 코드

# 15657 N과 M (8)

def dfs(n):
    if len(arr) == M:
        print(*arr)
        return
    else:
        for i in range(n, N):
            arr.append(num[i])
            dfs(i)
            arr.pop()

N, M = map(int,input().split())
num = list(map(int,input().split()))
num.sort()
arr = []

dfs(0)

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

문제

N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수는 모두 다른 수이다.

• N개의 자연수 중에서 M개를 고른 수열

입력

첫째 줄에 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8)

둘째 줄에 N개의 수가 주어진다. 입력으로 주어지는 수는 10,000보다 작거나 같은 자연수이다.

출력

한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다.

수열은 사전 순으로 증가하는 순서로 출력해야 한다.

풀이

dfs로 풀었다.

수열에는 인덱스 값을 통해 접근했다

python코드

# 15654 N과 M (5)
def dfs():
    if len(arr) == M:
        print(*arr)
        return
    else:
        for i in range(N):
            if num[i] not in arr:
                arr.append(num[i])
                dfs()
                arr.pop()


N, M = map(int,input().split())
num = list(map(int,input().split()))
num.sort()
arr = []

dfs()