AndroidTeacher

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

문제 설명

문제의 설명이 굉장히 길어 위 링크를 참고하시는 것을 추천드립니다.

수식 ex ("100-200*300-500+20") 이 주어졌을 때 +, -, *의 우선순위를 매번 다르게 하여 나타나는 값들 중 최댓값을 구하는 문제입니다.

원래는 * > +,- 의 우선순위를 갖지만, 이 문제에서는 *>+>- 가 될 수도 있고 +>->* 가 될 수도 있습니다.

풀이 과정

permutations(순열)을 통해 "*", "+", "-"로 만들 수 있는 우선순위 3! = 6 가지에 대해 수행합니다.

먼저 문자열 수식을 숫자와 기호로 분리를 해주기 위해

수식(expression)을 처음부터 끝까지 돌면서 리스트로 분리합니다. ( ["100", "-", "200", "*" ...] 이런 식으로 나오도록 )

그 다음, 리스트를 돌면서 해당 우선순위에 맞게 수식 계산을 하면 됩니다.

예시로, 가장 처음 우선순위가 ["*", "+", "-"] 라고 한다면, 리스트를 돌다가 *를 만나면 *의 앞뒤 숫자를 곱해줍니다.

(곱하기를 한 후에는 곱했던 수들을 제거해줘야 하기 때문에 앞 뒤 수를 제거합니다)

*를 끝냈다면 그 다음 +를 만나면 같은 방식으로 계산을 해주면 됩니다. 그 다음은 "-"에 대해 수행하고...

이렇게 한 우선순위에 대해 계산을 마쳤다면 최댓값을 저장합니다.

이렇게 첫 번째 우선순위 ["*", "+", "-"]에 대해 수행을 완료했다면, 다음 우선순위로 넘어가서 다시 반복하면 됩니다.

from itertools import permutations

def solution(expression):
    answer = 0
    oper = ["*", "+", "-"]
    mymax = int(-1e9)

    for per in permutations(oper, 3):
        perm = list(per)
        exp = ''
        tmp = []
        for i in range(len(expression)):
            if str(0) <= expression[i] <= str(9):
                exp += expression[i]
            else:
                tmp.append(exp)
                tmp.append(expression[i])
                exp = ''
            if i == len(expression) - 1:
                tmp.append(exp)


        for j in range(len(perm)):
            i = 0
            while i < len(tmp):
                if tmp[i] == perm[j]:
                    tmp[i-1] = eval(str(tmp[i-1])+perm[j]+str(tmp[i+1]))
                    del tmp[i]
                    if i < len(tmp):
                        del tmp[i]
                else:
                    i+=1

        mymax = max(mymax, abs(tmp[0]))
        
    return mymax

print(solution("100-200*300-500+20"))

https://github.com/HongEunho 

전체 문제 & 코드는 위의 깃에 정리되어 있습니다.

팔로우 & 맞팔은 환영입니다 !

www.acmicpc.net/problem/1593

문제 설명

W를 이루고 있는 g개의 문자와, 문자열 S가 주어졌을 때, 단어 W가 문자열 S에 들어있을 수 있는 모든 가짓수를 계산하는 프로그램을 작성하시오. 즉, 문자열  S안에서 문자열 W의 순열 중 하나가 부분 문자열로 들어있는 모든 경우의 수를 계산하라는 뜻이다.

예를 들어, W = cAda S = AbrAcadAbRa 이라면 W로 만들 수 있는 순열이 S안에 몇개 등장하는지 세면 됩니다.

( 자세한 설명은 위 링크 참고 바랍니다 )

풀이 과정

처음에는 permutations를 이용해서 w의 모든 순열을 s와 비교하는 방식으로 풀었지만 시간초과 오류가 발생하였다.

그래서, 알파벳 52개를 배열을 이용하여 비교하는 식으로 풀었다.

먼저, w의 각각의 알파벳의 등장횟수를 그 알파벳에 해당하는 칸에 +1을 해줍니다.

그리고 s의 처음부터 w길이만큼 끊어서 비교를 하게되는데,

그 구간에 w와 s에 등장하는 알파벳의 횟수가 일치한다면 w의 순열로 s를 만들 수 있다는 뜻이기 때문에

정답을 +1 해주면 됩니다.

길이만큼 비교를 한 후에는, s의 비교 시작부분을 한 칸씩 뒤로 옮기면서 비교를 이어나갑니다.

즉, S의 1~4칸까지 비교를 했다면 다음에는 2~5칸을 비교해야 하기 때문에

비교 후에는 S의 칸을 한 칸씩 뒤로 옮겨줘야 합니다.

모두 비교를 한 후에 정답을 출력하면 됩니다.

import sys
from itertools import permutations
n, m = map(int, input().split())
w = sys.stdin.readline().strip()
s = sys.stdin.readline().strip()

wl = [0] * 52
sl = [0] * 52

# w의 각 알파벳마다 등장하는 부분 +1
for i in range(n):
    if 'a' <= w[i] <= 'z':
        wl[ord(w[i]) - ord('a')] += 1
    else:
        wl[ord(w[i]) - ord('A') + 26] += 1

start, length, count = 0, 0, 0

for i in range(m):
    if 'a' <= s[i] <= 'z':
        sl[ord(s[i]) - ord('a')] += 1
    else:
        sl[ord(s[i]) - ord('A') + 26] += 1
    length += 1

    if length == n:
        if wl == sl:
            count+=1
        if 'a' <= s[start] <= 'z':
            sl[ord(s[start]) - ord('a')] -= 1
        else:
            sl[ord(s[start]) - ord('A') + 26] -= 1
        start += 1
        length -= 1


print(count)

https://github.com/HongEunho

전체 문제 & 코드는 위의 깃에 정리되어 있습니다.

팔로우 & 맞팔은 환영입니다 !

www.acmicpc.net/problem/17413

문제 설명

문자열 S가 주어졌을 때, 이 문자열에서 단어만 뒤집으려고 한다.

먼저, 문자열 S는 아래와과 같은 규칙을 지킨다.

1. 알파벳 소문자('a'-'z'), 숫자('0'-'9'), 공백(' '), 특수 문자('<', '>')로만 이루어져 있다.
2. 문자열의 시작과 끝은 공백이 아니다.
3. '<'와 '>'가 문자열에 있는 경우 번갈아가면서 등장하며, '<'이 먼저 등장한다. 또, 두 문자의 개수는 같다.

태그는 '<'로 시작해서 '>'로 끝나는 길이가 3 이상인 부분 문자열이고, '<'와 '>' 사이에는 알파벳 소문자와 공백만 있다. 단어는 알파벳 소문자와 숫자로 이루어진 부분 문자열이고, 연속하는 두 단어는 공백 하나로 구분한다. 태그는 단어가 아니며, 태그와 단어 사이에는 공백이 없다.

풀이 과정

괄호 사이의 문자열은 뒤집으면 안되기 때문에 "<" 를 만나면 ">" 를 만날 때 까지는 그대로 둔다.

알파벳이나 숫자일 경우, 뒤집어야 하기 때문에

단어를 구분짓는 공백이나, 혹은 괄호를 만나기 전까지 뒤집어준다.

또한, 띄어쓰기를 만나게 되면 그냥 i +=1 을 통해 지나간다.

import sys
word = list(sys.stdin.readline().rstrip())

i = 0
start = 0

while i < len(word):
    if word[i] == "<":       # 열린 괄호를 만나면
        i += 1 
        while word[i] != ">":      # 닫힌 괄호를 만날 때 까지
            i += 1 
        i += 1               # 닫힌 괄호를 만난 후 인덱스를 하나 증가시킨다
    elif word[i].isalnum(): # 숫자나 알파벳을 만나면
        start = i
        while i < len(word) and word[i].isalnum():
            i+=1
        tmp = word[start:i] # 숫자,알파벳 범위에 있는 것들을
        tmp.reverse()       # 뒤집는다
        word[start:i] = tmp
    else:                   # 괄호도 아니고 알파,숫자도 아닌것 = 공백
        i+=1                # 그냥 증가시킨다

print("".join(word))

https://github.com/HongEunho

전체 문제 & 코드는 위의 깃에 정리되어 있습니다.

팔로우 & 맞팔은 환영입니다 !

www.acmicpc.net/problem/1431

문제 설명

다솜이는 기타를 많이 가지고 있다. 그리고 각각의 기타는 모두 다른 시리얼 번호를 가지고 있다. 다솜이는 기타를 빨리 찾아서 빨리 사람들에게 연주해주기 위해서 기타를 시리얼 번호 순서대로 정렬하고자 한다.

모든 시리얼 번호는 알파벳 대문자 (A-Z)와 숫자 (0-9)로 이루어져 있다.

시리얼번호 A가 시리얼번호 B의 앞에 오는 경우는 다음과 같다.

1. A와 B의 길이가 다르면, 짧은 것이 먼저 온다.
2. 만약 서로 길이가 같다면, A의 모든 자리수의 합과 B의 모든 자리수의 합을 비교해서 작은 합을 가지는 것이 먼저온다. (숫자인 것만 더한다)
3. 만약 1,2번 둘 조건으로도 비교할 수 없으면, 사전순으로 비교한다. 숫자가 알파벳보다 사전순으로 작다.

시리얼이 주어졌을 때, 정렬해서 출력하는 프로그램을 작성하시오.

풀이 과정

문제의 정렬과정을 순서대로 구현해주면 되는 문제이다.

나는 다음과 같은 두 가지 풀이 방법을 이용하였다.

① sort 내장함수를 이용하여 짧게 풀이

② 직접 sort를 구현하여 풀이

실제 코딩테스트에서는 ①의 풀이가 훨씬 짧고 효율적이다.

하지만, 연습할 때에는 ②처럼 직접 소트를 구현해보는 것도 추천하는 방법이다.

풀이 ① sort 이용

n = int(input())

def sum_num(inputs):
    result = 0
    for i in inputs:
        if i.isdigit():
            result+=int(i)
    return result

arr = []
for i in range(n):
    a = input()
    arr.append(a)

arr.sort(key = lambda x:(len(x), sum_num(x), x))
for i in arr:
    print(i)

풀이 ② 직접 각 조건의 소트 구현

n = int(input())

arr = []
for i in range(n):
    a = input()
    arr.append(a)


for i in range(n-1):
    for j in range(i+1, n):
        # 짧은 것이 먼저
        if len(arr[i]) > len(arr[j]):
            arr[i], arr[j] = arr[j], arr[i]

        elif len(arr[i]) == len(arr[j]):
            suma=0
            sumb=0
            for x,y in zip(arr[i],arr[j]):
                if x.isdigit():
                    suma+=int(x)
                if y.isdigit():
                    sumb+=int(y)
            if suma > sumb:
                arr[i],arr[j] = arr[j], arr[i]

            elif suma == sumb:
                for x,y in zip(arr[i], arr[j]):
                    if x > y:
                        arr[i],arr[j] = arr[j], arr[i]
                        break
                    elif x < y:
                        break


for i in arr:
    print(i)

https://github.com/HongEunho

전체 문제 & 코드는 위의 깃에 정리되어 있습니다.

팔로우 & 맞팔은 환영입니다 !

www.acmicpc.net/problem/9375

문제 설명

해빈이는 패션에 매우 민감해서 한번 입었던 옷들의 조합을 절대 다시 입지 않는다.

예를 들어 오늘 해빈이가 안경, 코트, 상의, 신발을 입었다면, 다음날은 바지를 추가로 입거나 안경대신 렌즈를 착용하거나 해야한다.

해빈이가 가진 의상들이 주어졌을때 과연 해빈이는 알몸이 아닌 상태로 며칠동안 밖에 돌아다닐 수 있을까?

첫째 줄에 테스트 케이스가 주어진다. 테스트 케이스는 최대 100이다.

• 각 테스트 케이스의 첫째 줄에는 해빈이가 가진 의상의 수 n(0 ≤ n ≤ 30)이 주어진다.
• 다음 n개에는 해빈이가 가진 의상의 이름과 의상의 종류가 공백으로 구분되어 주어진다. 같은 종류의 의상은 하나만 입을 수 있다.

모든 문자열은 1이상 20이하의 알파벳 소문자로 이루어져있으며 같은 이름을 가진 의상은 존재하지 않는다.

풀이 과정

같은 종류의 의상은 하나씩만 착용할 수 있으며, 알몸이 아니어야 하므로 꼭 1종류 이상의 의상은 착용해야 한다.

예를 들어, 3종류의 의상이 있으면 1종류만 착용해도 되며, 2종류를 착용해도 되고, 3종류를 착용해도 되지만

0종류를 착용하는건 안된다.

그렇다면 다음과 같은 식을 세울 수 있다.

(a종류수 + 1) * (b종류수 + 1) * (c종류수 + 1)... - 1

여기서 종류수에 +1을 해준 이유는 그 종류의 의상을 착용해도 되고 안해도 되기 때문이고

마지막에 -1을 해준 이유는 모든 의상을 착용하지 않은 경우를 제외시켜줘야 하기 때문이다.

의상의 종류와 그 종류에 있는 의상 이름을 나타내기 위해 딕셔너리를 이용하였다.

t = int(input())

for i in range(t):
    n = int(input())
    weardict = {}
    for j in range(n):
        wear = list(input().split())
        if wear[1] in weardict:
            weardict[wear[1]].append(wear[0])
        else:
            weardict[wear[1]] = [wear[0]]

    cnt = 1 # 각 종류마다 항목의 개수

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

아래의 풀이는 파이썬의 Counter모듈을 이용하여

딕셔너리를 직접 제작하지 않아도 자동으로 개수를 세주는 기능을 이용하였다.

from collections import Counter
t = int(input())

for i in range(t):
    n = int(input())
    wear = []
    for j in range(n):
        a, b = input().split()
        wear.append(b)

    wear_Counter = Counter(wear)
    cnt = 1 # 각 종류마다 항목의 개수

    for key in wear_Counter:
        cnt *= wear_Counter[key] + 1

    print(cnt-1)

https://github.com/HongEunho

전체 문제 & 코드는 위의 깃에 정리되어 있습니다.

팔로우 & 맞팔은 환영입니다 !

문제 설명

어떤 수와 그 수의 숫자 순서를 뒤집은 수가 일치하는 수를 팰린드롬이라 부른다. 예를 들어 79,197과 324,423 등이

팰린드롬 수이다.

어떤 수 N (1 ≤ N ≤ 1,000,000)이 주어졌을 때, N보다 크거나 같고, 소수이면서 팰린드롬인 수 중에서, 가장 작은 수를 구하는 프로그램을 작성하시오.

풀이 과정

소수란 1과 자기자신을 제외한 수로는 나누어 떨어지지 않는 수를  말하는데,

이 소수를 구하는 방법에는 대표적으로 세가지가 있다.

① i를 2부터 n-1까지 돌면서 i로 나누어 떨어지는 경우가 존재하지 않으면 소수

② i를 2부터 루트n까지 돌면서 i로 나누어 떨어지는 경우가 존재하지 않으면 소수

③ 에라토스테네스의 체

①번과 ②번의 경우에는, 명확하게 ②번의 경우의 범위가 더 좁기 때문에 더 빠른것이 명확하다.

③에라토스테네스의 체 의 경우에는 구하는 방법을 미리 알고있어야 하기 때문에 이 문제에서는 ②를 이용하여 풀었다.

펠린드롬의 경우에는 문자열을 그대로 뒤집어서 일치하면 True 처리를 해주었다.

import math
n = int(input())

def isPrime(x):
    if x == 1:
        return False
    for i in range(2, int(math.sqrt(x)+1)):
        if x % i == 0:
            return False
    return True

def isPalindrome(x):
    xs = str(x)
    xsr = xs[::-1]
    if xs == xsr:
        return True
    else:
        return False

start = n
while True:
    if isPalindrome(start) and isPrime(start):
        print(start)
        break
    else:
        start+=1

https://github.com/HongEunho

전체 문제 & 코드는 위의 깃에 정리되어 있습니다.

팔로우 & 맞팔은 환영입니다 !

www.acmicpc.net/problem/5525

문제 설명

N+1개의 I와 N개의 O로 이루어져 있으면, I와 O이 교대로 나오는 문자열을 PN이라고 한다.

• P1 IOI
• P2 IOIOI
• P3 IOIOIOI
• PN IOIOI...OI (O가 N개)

I와 O로만 이루어진 문자열 S와 정수 N이 주어졌을 때, S안에 PN이 몇 군데 포함되어 있는지 구하는 프로그램을 작성하시오.

풀이 과정

문자열 S를 for문을 돌면서 i를 만날 경우 현재 인덱스를 stack에 넣어준다.

(예를 들어, ooioi일 경우 스택에 2, 4가 들어있을 것이다.)

stack의 각 원소들의 차이가 2인 경우는 i가 한 칸을 띄어져있다는 뜻이므로

이런 경우에 cnt를 하나씩 늘려준다.

이 때, cnt가 n이상일 경우 answer을 하나씩 추가해준다.

import sys
n = int(input())
m = int(input())
s = sys.stdin.readline()

cnt = 0
answer = 0
stack=[]

for i in range(m):
    if s[i] == "O":
        continue
    else:
        stack.append(i)

for i in range(1, len(stack)):
    if stack[i] - stack[i-1] == 2:
        cnt += 1
    else:
        cnt = 0

    if cnt >= n:
        answer += 1


print(answer)

https://github.com/HongEunho

전체 문제 & 코드는 위의 깃에 정리되어 있습니다.

팔로우 & 맞팔은 환영입니다 !

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

문제 설명

user_id 중에서 banned_id에 의해 필터링되는 user_id 목록의 경우의 수를 구하는 문제입니다.

문제의 설명이 꽤 길어서 링크를 함께 첨부하였습니다

자세한 문제 설명은 위 링크를 참조하세요!

풀이 과정

문제에서 배열의 범위가 굉장히 작기 때문에, 완전탐색을 이용하여 풀어도 됩니다!

그래서 저는 순열(permutation)을 이용하여 user_id로 만들 수 있는 모든 경우의 수를 banned_id와 비교하였습니다.

아래 코드의 solution부분부터 보게되면,

permutations(user_id, len(banned_id))를 통해 banned_id 배열의 길이만큼을 user_id에서 뽑아냅니다.

예를들어, banned_id = ["fr*d*", "abc1**"] 이면 user_id에서 두 개를 뽑아내겠죠?

그 다음 뽑은 user_id와 banned_id를 비교합니다. 그 부분이 check함수입니다.

check 함수로 이동하여,

banned_id의 원소와 candidates의 원소를 하나씩 비교하는데,

두 원소의 길이가 다르다면, 당연히 일치하지 않기 때문에 False처리를 해주고

일치하는 경우, 문자 하나하나 따져가며 검사합니다.

banned_id[i]의 n번째 인덱스가 별표인경우는 그 인덱스는 모든 문자가 가능하므로 continue해주고,

두 원소의 똑같은 인덱스의 문자가 일치하지 않는 경우, False 처리를 해줍니다.

모든 for문을 통과하면 True를 리턴합니다.

다시 solution의 check로 돌아와보면, if문을 True로 통과했기 때문에

candidates라는 변수를 set형식으로 바꿔줍니다. ( 중복 방지를 위해 )

그리고 이 candidates가 answer에 없으면, answer에 추가해주면 됩니다.

from itertools import permutations

def check(candidates, banned_id):
    for i in range(len(banned_id)):
        if len(candidates[i]) != len(banned_id[i]):
            return False
        for a, b in zip(candidates[i], banned_id[i]):
            if b == "*":
                continue
            if a != b:
                return False
    return True


def solution(user_id, banned_id):
    answer = []

    for candidates in permutations(user_id, len(banned_id)):
        if check(candidates, banned_id):
            candidates = set(candidates)
            if candidates not in answer:
                answer.append(candidates)

    return len(answer)

https://github.com/HongEunho

전체 문제 & 코드는 위의 깃에 정리되어 있습니다.

팔로우 & 맞팔은 환영입니다 !