Loading [MathJax]/jax/output/CommonHTML/jax.js
반응형

문제풀이

30의 배수가 될 조건은 아래와 같다.

1. 0이 한개 이상 들어가야한다.

2. 모든 수의 합이 3의 배수여야한다.(1230 이면, 1230의 합은 1+2+3+0 = 6)

 

1. collections.Counter 를 이용하여 받은 숫자들을 한자리씩 잘라 센다.(위의 조건2를 위한 과정)

2. 1에서 센 딕셔너리의 key*value 의 합이 3의 배수인지 확인한다.(조건2)

3. 조건1, 2를 만족한다면 숫자들을 큰 수부터 붙여나간다.

 

Python Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
import sys,collections
 
def sol(n):
    dic = collections.Counter(n)
    check = sum(int(k)*v for k,v in dic.items())
    if "0" not in dic or check%3!=0:
        return -1
    else :
        ans = ""
        for i in range(9,-1,-1):
            str_i = str(i)
            if str_i in dic :
                for _ in range(dic[str_i]):
                    ans += str_i
        return ans
 
if __name__ == "__main__":
    n=sys.stdin.readline().split()[0]
    print(sol(n))
 cs

Line 4 : 주어진 숫자를 하나씩 잘라 개수를 센다.

Line 5 : 숫자들의 합을 계산한다.

Line 6 : 조건 1 만족 여부를 확인한다.

Line 8 : 조건1, 2를 모두 만족한 경우로 큰 숫자부터(9부터) 붙여나간다.

문제 링크

 

10610번: 30

문제 어느 날, 미르코는 우연히 길거리에서 양수 N을 보았다. 미르코는 30이란 수를 존경하기 때문에, 그는 길거리에서 찾은 수에 포함된 숫자들을 섞어 30의 배수가 되는 가장 큰 수를 만들고 싶어한다. 미르코를 도와 그가 만들고 싶어하는 수를 계산하는 프로그램을 작성하라. 입력 N을 입력받는다. N는 최대 105개의 숫자로 구성되어 있으며, 0으로 시작하지 않는다. 출력 미르코가 만들고 싶어하는 수가 존재한다면 그 수를 출력하라. 그 수가 존재하지 않는

www.acmicpc.net

 

반응형

'알고리즘 > 백준' 카테고리의 다른 글

백준 1002 터렛  (0) 2020.04.09
백준 11048 이동하기  (0) 2020.03.30
백준 2436 공약수  (0) 2020.03.24
백준 2559 수열  (0) 2020.03.23
백준 1058 친구  (0) 2020.03.19
반응형

문제풀이

 1. 공백 이후의 첫자가 알파벳이면 대문자로 바꾼다.

 2. 두번째 이후의 글자가 알파벳이면 소문자로 바꾼다.

 

* 주의해야 할 예제 : 공백이 두번 이상 나오는 경우를 고려해야 한다.

Java Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
package programmers;
 
class Solution {
    public String solution(String s) {
        StringBuilder sb = new StringBuilder();
        boolean first = true;
        for (int i =0; i<s.length() ; i++) {
            char c = s.charAt(i);
            if(first) {
                if(isAlpha(c)) {
                    sb.append(Character.toUpperCase(c));
                    first=false;
                }else if(c==' ') {
                    sb.append(c);
                }
                else {
                    sb.append(c);
                    first=false;
                }
            }else {
                if(isAlpha(c)) {
                    sb.append(Character.toLowerCase(c));
                }else if(c == ' ') {
                    sb.append(c);
                    first=true;
                }else {
                    sb.append(c);
                }
            }
        }
        
        return sb.toString();
    }
    public boolean isAlpha(char c) {
        if((c>='a' && c<='z') || (c>='A' && c<='Z')) {
            return true;
        }else {
            return false;
        }
    }
}
 cs

Line 6 : first 변수는 해당 문자가 공백 이후 첫번째 문자인지를 알려주는 변수이다.

Line 13 : 연속으로 빈칸이 나오는 경우에 first 변수에 대해서 주의해야 한다.

Line 34 : isAlpha 메소드는 해당 문자가 알파벳인지 확인하는 메소드이다.

문제 링크

 

프로그래머스

코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.

programmers.co.kr

 

반응형

'알고리즘 > 프로그래머스' 카테고리의 다른 글

프로그래머스 SQL 없어진 기록 찾기  (0) 2020.04.17
프로그래머스 Lv3 자물쇠와 열쇠  (0) 2020.04.16
프로그래머스 Lv2 뉴스 클러스터링  (0) 2020.03.27
프로그래머스 SQL 오랜 기간 보호한 동물(2)  (0) 2020.03.23
프로그래머스 SQL 중성화 여부 확인하기  (0) 2020.03.23
반응형

2018 KAKAO BLIND RECRUITMENT 문제이다.

문제 풀이

 1. 먼저 문자열을 2자씩 끊은 후, 정규표현식을 이용하여 두자가 모두 알파벳으로 되어있는지 확인한다.

 2. 두자 모두 알파벳으로 되어있다면 str1, str2 각각의 리스트에 모두 소문자로 바꾸어 넣어준다.("FR"과 "fr"을 같은 단어로 인식하기 위함으로 꼭 소문자가 아니더라도 둘의 양식을 맞춰주면 된다.)

 3. 합집합과 교집합의 원소의 수를 세어 자카드 유사도를 반환한다.

Python Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
import re
 
def solution(str1, str2):
    checker = re.compile('[a-zA-Z]{2}')
    answer = 0
    
    token1 = []
    token2 = []
    # tokenize
    for i in range(len(str1)-1):
        t1 = str1[i:i+2]
        if checker.match(t1) != None:
            token1.append(t1.lower())
    for i in range(len(str2)):
        t2 = str2[i:i+2]
        if checker.match(t2) != None:
            token2.append(t2.lower())
    
    intersection = 0
    union = 0
    
    for t in token1:
        if t in token2:
            intersection+=1
            union += 1
            token2.remove(t)
        else :
            union+=1
    union += len(token2)
    return int((intersection/union) * 65536) if intersection+union != 0 else 65536
 cs

문제 링크

 

프로그래머스

코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.

programmers.co.kr

 

반응형

'알고리즘 > 프로그래머스' 카테고리의 다른 글

프로그래머스 Lv3 자물쇠와 열쇠  (0) 2020.04.16
프로그래머스 Lv2 JadenCase 문자열 만들기  (0) 2020.03.27
프로그래머스 SQL 오랜 기간 보호한 동물(2)  (0) 2020.03.23
프로그래머스 SQL 중성화 여부 확인하기  (0) 2020.03.23
프로그래머스 Lv2 압축  (0) 2020.03.22
반응형

2011 정보올림피아드 초등부 2번 문제이다.

문제 풀이

 주어진 두 수를 a, b, 두 수의 최대공약수를 g, 최소공배수를 l이라 하면, a, b, g, l의 관계는 다음과 같다.

 A=ag

 B=bg

 l=g×A×B

 위의 관계를 이용하면 B는 다음과 같이 쓸 수 있다.

 B=lg×A

 따라서, 가능한 A에 대하여 B를 구하고 A와 B가 서로소인지 확인하면 된다.

Python Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
import sys, math
def gcd(a, b):
  while (b != 0):
    temp = a % b
    a = b
    b = temp
  return abs(a)
def solution(g,l):
    ans = (l,l)
    temp = (0,0)
    for A in range(math.ceil(math.sqrt(l//g)),0,-1):
      if l%(g*A) == 0:
        B = l//(g*A)
        temp = (A*g,B*g)
        if gcd(A,B) == 1 and sum(temp) < sum(ans):
          ans = temp
                
    print(min(ans),max(ans))
if __name__ == "__main__":
    g,l = map(int,sys.stdin.readline().split())
    solution(g,l)
 cs

Line 11 : 가능한 A에 대하여

Line 13 : B를 구하고

Line 15 : A와 B가 서로소인지 확인한다.

 

For 문 (가능한 A)의 범위에 대하여

 첫번째 풀이에서는 for문을 아래와 같이 작성하였고, 3784 ms가 걸렸다. 통과 후, 다른 사람들의 기록을 보니 52ms로 약 60배가 빨라서 뭔가 확인해보니 for문의 범위가 문제였다.

 아래의 풀이의 경우에는 A를 1부터 l//g 까지 모든 A, B 쌍에 대하여 계산하였는데, 위의 a, b, g, l의 관계를 이용하면 A와 B가 같을 때, 즉 A2=lg 인 경우가 산술기하평균으로부터 합이 가장 작은 A, B 쌍인 것을 알 수 있으므로, A를 √lg 부터 1씩 내리며 만족하는 A와 B를 찾으면 바로 리턴하는 것이 최적해 임을 알 수 있다. 위의 풀이의 경우 60 ms가 걸렸다.

1
2
3
4
5
6
7
8
9
def solution(g,l):
    ans = (l,l)
    for A in range(1,l//g+1):
        if l%(A*g) == 0:
            a = A*g
            B = l//(A*g)
            b = B*g
            if gcd(A,B) == 1 and a+b < sum(ans):
                ans = (a,b)
 cs

문제 링크

 

2436번: 공약수

첫째 줄에 두 개의 자연수가 빈칸을 사이에 두고 주어진다. 첫 번째 수는 어떤 두 개의 자연수의 최대공약수이고, 두 번째 수는 그 자연수들의 최소공배수이다. 입력되는 두 자연수는 2 이상 100,000,000 이하이다.

www.acmicpc.net

 

반응형

'알고리즘 > 백준' 카테고리의 다른 글

백준 11048 이동하기  (0) 2020.03.30
백준 10610 30  (0) 2020.03.28
백준 2559 수열  (0) 2020.03.23
백준 1058 친구  (0) 2020.03.19
백준 2469 사다리 타기  (0) 2020.03.19
반응형

문제 풀이

1. ANIMAL_IN 과 ANIMAL_OUT 테이블을 ANIMAL_ID 컬럼으로 이너 조인 한 후, 두 테이블의 DATETIME 컬럼의 차를 구한다.

2. DATETIME 컬럼의 차를 기준으로 내림차순 정렬한다.

3. 2로 구한 테이블에서 상위 2개를 출력한다.

ORACLE Code

1
2
3
4
5
6
7
8
SELECT ANIMAL_ID, NAME
FROM 
(SELECT I.ANIMAL_ID, I.NAME, O.DATETIME - I.DATETIME AS 시간
FROM ANIMAL_INS I INNER JOIN ANIMAL_OUTS O
ON I.ANIMAL_ID = O.ANIMAL_ID
ORDER BY 시간 DESC
)
WHERE ROWNUM < 3
 cs

 

문제 링크

 

프로그래머스

코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.

programmers.co.kr

 

반응형

'알고리즘 > 프로그래머스' 카테고리의 다른 글

프로그래머스 Lv2 JadenCase 문자열 만들기  (0) 2020.03.27
프로그래머스 Lv2 뉴스 클러스터링  (0) 2020.03.27
프로그래머스 SQL 중성화 여부 확인하기  (0) 2020.03.23
프로그래머스 Lv2 압축  (0) 2020.03.22
프로그래머스 Lv3 타일 장식물  (0) 2020.03.22
반응형

문제 풀이

SEX_UPON_INTAKE 의 도메인은 (Neutered, Spayed, Intact) + (Male, Female) 이므로, 첫자가 N이나 S이면 중성화가 된것이다. 따라서 substr 함수를 이용하여 첫자만 따서 확인한다.

Code

1
2
3
4
5
6
SELECT ANIMAL_ID, NAME, 
(CASE WHEN SUBSTR(SEX_UPON_INTAKE,1,1) IN ('N','S') THEN 'O'
ELSE 'X'
END) AS '중성화'
FROM ANIMAL_INS
ORDER BY ANIMAL_ID
 cs

문제 링크

 

프로그래머스

코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.

programmers.co.kr

 

반응형

'알고리즘 > 프로그래머스' 카테고리의 다른 글

프로그래머스 Lv2 뉴스 클러스터링  (0) 2020.03.27
프로그래머스 SQL 오랜 기간 보호한 동물(2)  (0) 2020.03.23
프로그래머스 Lv2 압축  (0) 2020.03.22
프로그래머스 Lv3 타일 장식물  (0) 2020.03.22
프로그래머스 Lv3 N-Queen  (0) 2020.03.22
반응형

2011 정보올림피아드 초등부 1번문제이다.

문제풀이

 수열의 연속된 요소들의 합 중 가장 큰 값을 찾는 문제로, 수열을 t라 하면 sum(t[i:i+k])의 최댓값을 구하면 된다.

 1. sum(t[0:k])를 먼저 구한다.

 2. for 문을 k부터 n까지 가며, for 문의 변수가 i라 하면 1의 값에서 t[i]를 더하고 t[i-k]를 빼준다. 이렇게 하면 sum(t[i+k])가 된다.

 3. 2의 값과 1의 값을 비교해 가며 가장 큰 값을 가지고 있다가 for문이 끝나면 반환해준다.

 

시간 복잡도는 수열의 길이만큼의 for문 한번으로 끝나므로, 수열의 길이를 N이라 하면 O(N)이 된다.

주의해야 할 예제로는 n == k인 경우와, 정답이 음수인 경우 정도이다(처음에 ans를 0으로 초기화했다가 틀렸다).

Python Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
import sys
def solve(n,k,t):
    temp = sum(t[:k])
    ans = temp
    for i in range(k,n):
        temp += t[i]
        temp -= t[i-k]
        if temp > ans:
            ans = temp
    return ans if n != k else temp
if __name__ == "__main__":
    n, k = map(int,sys.stdin.readline().split())
    t = list(map(int,sys.stdin.readline().split()))
    print(solve(n,k,t))
 cs

 

문제 링크

 

2559번: 수열

첫째 줄에는 두 개의 정수 N과 K가 한 개의 공백을 사이에 두고 순서대로 주어진다. 첫 번째 정수 N은 온도를 측정한 전체 날짜의 수이다. N은 2 이상 100,000 이하이다. 두 번째 정수 K는 합을 구하기 위한 연속적인 날짜의 수이다. K는 1과 N 사이의 정수이다. 둘째 줄에는 매일 측정한 온도를 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -100 이상 100 이하이다. 

www.acmicpc.net

 

반응형

'알고리즘 > 백준' 카테고리의 다른 글

백준 10610 30  (0) 2020.03.28
백준 2436 공약수  (0) 2020.03.24
백준 1058 친구  (0) 2020.03.19
백준 2469 사다리 타기  (0) 2020.03.19
백준 2468 안전 영역  (0) 2020.03.17
반응형

2018 KAKAO BLIND RECRUITMENT 문제로 LZW 압축을 구현하는 문제이다.

 

문제 풀이

 1. 먼저 각 문자열에 대한 색인 번호를 넣을 사전을 선언한다.

 2. A - Z 까지를 색인 번호 1 - 26 으로 넣어준다.

 3. 맨 앞 문자부터 사전에서 찾아보며 사전에 있으면 문자열의 길이를 늘려가며 찾는다. 문자열이 사전에서 없어지면 해당 문자열을 색인번호의 최댓값에 1을 더해 넣는다. 

 4. 3과정에서 사전에 있는 가장 긴 문자열을 answer에 넣는다.

 5. 다음 문자부터 3-4과정을 반복한다.

 예를 들면, 'KAKAO'의 경우, K를 먼저 찾고 있으면 KA를 찾고 또 있으면 KAK를 찾는 식으로 진행하며 해당 문자열이 사전에 없을 때 까지 진행하여, 해당 문자열이 사전에 없으면 사전에 넣고, 다음 문자부터 다시 시작한다. KA까지 사전에 있다면 KAK를 사전에 넣고, KA의 색인 번호를 answer에 넣는다.

Python Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
from string import ascii_uppercase
def solution(msg):
    dic = {}
    idx=1
    for a in ascii_uppercase:
        dic[a] = idx
        idx+=1
    answer = []
 
    i=0
    j=i+1
    while i < len(msg)-1:
        j=i+1
        while j<= len(msg) and msg[i:j] in dic:
            j+=1
        #msg[i:j-1]는 dic에 있다
        answer.append(dic[msg[i:j-1]])
        dic[msg[i:j]]=idx
        idx += 1
        i=j-1
        #print(dic)
    if i == len(msg)-1:
        answer.append(dic[msg[-1]])
    return answer
 cs

 

문제 링크

 

프로그래머스

코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.

programmers.co.kr

 

반응형

'알고리즘 > 프로그래머스' 카테고리의 다른 글

프로그래머스 SQL 오랜 기간 보호한 동물(2)  (0) 2020.03.23
프로그래머스 SQL 중성화 여부 확인하기  (0) 2020.03.23
프로그래머스 Lv3 타일 장식물  (0) 2020.03.22
프로그래머스 Lv3 N-Queen  (0) 2020.03.22
프로그래머스 Lv3 베스트앨범  (0) 2020.03.20

+ Recent posts

티스토리툴바