CodeDrive

문제:

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이 몇 군데 포함되어 있는지 구하는 프로그램을 작성하시오.

입력:

첫째 줄에 N이 주어진다. 둘째 줄에는 S의 길이 M이 주어지며, 셋째 줄에 S가 주어진다. (1<=N<=1,000,000 , 2N+1 <= M <= 1,000,000)

출력:

S에 Pn이 몇 군데 포함되어 있는지 출력한다.

풀이방법:

Pn은 I와 O가 교대로 나오는 문자열이다. 따라서 index로 비교해서 IOI 패턴을 만족하는지 확인하고 이렇게 연속된 횟수를 세고 N과 일치할 경우 answer를 1 증가시킨다.

문제링크:

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

문제:

어떤 숫자 n이 자신을 제외한 모든 약수들의 합과 같으면, 그 수를 완전수라고 한다.

예를 들어 6은 6 = 1 + 2 + 3 으로 완전수이다.

n이 완전수인지 아닌지 판단해주는 프로그램을 작성하라.

입력:

입력은 테스트 케이스마다 한 줄 간격으로 n이 주어진다. (2 < n < 100,000)

입력의 마지막엔 -1이 주어진다.

출력:

테스트케이스마다 한줄에 하나씩 출력해야 한다.

n이 완전수라면, n을 n이 아닌 약수들의 합으로 나타내어 출력한다. (예제 출력 참고).

이때, 약수들은 오름차순으로 나열해야 한다.

n이 완전수가 아니라면 n is NOT perfect. 를 출력한다.

풀이방법:

약수들을 찾는 것은 어렵지 않으나 출력 요건을 주의 깊게 맞춰야 하는 문제인 것 같다.

약수들을 찾는 것은 브루트포스 방법으로 2부터 다 나눠보면서 나머지가 없는 값을 찾으면 된다. 이 때, 조금이라도 시간을 줄이기 위해서 n까지 다 나눠보는 것이 아닌 n//2-1까지 나눠보도록 했다. 이렇게 약수들을 모두 찾은 다음에 중복을 제거한 다음에 정렬을 했다. (중복은 제곱수를 위해 제거, 9와 같은 경우 1,3,3과 같이 들어가 있을 것)

약수들의 합이 n과 같으면 완전수이므로 출력 조건에 맞춰서 출력을 하고, 다르면 n is NOT perfect.로 출력한다.

100,000미만의 완전수는 6, 28, 496, 8128만 있으니 확인 후 제출하면 된다.

문제링크:

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

문제:

풀이방법:

문자열을 잘 parsing할 수 있는지와, 어느 시점에 최대가 되는지 알아야 하는 문제다.

 우선 문자열을 파싱하기 위해서 splitTime이라는 함수를 만들었고, 날짜, 시간, 처리시간은 공백으로 구분되어 있기 때문에 split해주고, 날짜는 항상 2016년 9월 15일로 고정되어 있기 때문에 사용하지 않는다. 시간은 다시한번 :로 구분되어 있기 때문에 split해주고 1초간 처리하는 요청의 최대 개수를 알아야 하기 때문에 시간을 1초 단위로 만들어준다. 처리시간은 초 단위로 나오고 항상 s로 끝나기 때문에 이를 제거한 다음에 float으로 만들어 준다. 그리고 처리시간은 시작시간과 끝시간을 포함하기 때문에 배열로 반환을 할 때 시작시간에 0.001만큼 더하도록 한다.

 보통 최대 개수인 부분은 시작시간이나 끝시간에서 발생하게 된다. 이 시간들을 기준으로 처리해야하는 데이터가 생성되거나 사라지기 때문이다. (배열의 모든 시간을 탐색해도 좋지만 시간이 오래 걸릴 것이다.) 각 트래픽별의 시작시간과 끝나는 시간을 기준으로 트래픽의 갯수를 세서 최대 갯수를 파악한다.

문제링크:

https://programmers.co.kr/learn/courses/30/lessons/17676?language=python3

문제:

풀이방법:

 문자열을 처리하고 규칙에 따라 정리를 하면 되는 문제이다.

우선 양 끝은 {{~~}}으로 고정이 되어 있다. 따라서 슬라이싱을 통해서 이 부분을 떼어내고 숫자들을 구분하기 위해서    '}.{'로 split을 한다. 이렇게 하면 ['2', '2,1' , '2,1,3' , '2,1,3,4'] 와 같이 분리되게 된다.

 반복문으로 순환을 하면서 다시 ','을 기준으로 분리를 하면 숫자만 남게 되는데 이를 각 원소값이 int인 list로 tuples에 정리하게 된다. 이 단계까지 마치면 문자열을 규칙에 적용할 수 있도록 정리가 마무리 되었다.

규칙은 다음과 같다.

1. 각 list들을 길이가 짧은 순으로 정렬을 한다.

2. list의 숫자 값을 탐색하며 answer list에 없는 값이라면 answer에 넣고 break를 한 뒤 다음 list를 탐색한다.

따라서 이 규칙을 끝까지 적용하면 answer를 얻을 수 있다.

문제링크:

https://programmers.co.kr/learn/courses/30/lessons/64065

문제:

풀이방법:

우선 파일명을 HEAD, NUMBER, TAIL로 정리를 해야한다. 이를 위해서 isdigit이라는 숫자인지 확인하는 함수를 사용한다.

 처음 isdigit이 참이 되는 순간 이전까지의 글자가 HEAD가 되므로 isdigit이 참이 되는 순간 parser에 값을 추가하고 break를 걸어서 반복문을 나온다. 

 해당 위치부터 다시 반복문을 사용해서 이번에는 isdigit이 거짓이 되는 순간이 NUMBER의 끝이므로 parser에 값을 추가하고 break를 걸어서 반복문을 나온다.

 이제 남은 부분은 TAIL에 해당하므로 parser에 추가해주면 되지만 TAIL이 아무것도 없을 경우에는 위 NUMBER를 파악하는 과정에서 맨 마지막 숫자가 추가되지 못했을 것이다. 따라서 해당 인덱스에 isdigit을 사용해서 참이면 TAIL이 없는 경우, 거짓이면 TAIL이 있는 경우를 의미한다.

 이제 파일명을 HEAD, NUMBER, TAIL로 나눴으므로 sort의 key를 사용해서 정렬을 하도록 한다. 우선 HEAD를 기준으로 사전 순 정렬을 하고, 대소문자 구별을 하지 않는다. 그리고 HEAD가 동일하다면 NUMBER가 작은순으로 정렬을 하는데 스트링 상태가 아닌 int 상태로 변환해서 정렬을 해야 한다. 따라서 sort의 key는 (x[0].upper(), int(x[1])) 이 된다. 이처럼 해야지 원래 파일명을 보존하면서 정렬을 할 수 있다.

 정렬을 완료했으므로 이를 다시 붙여서 출력을 해야 한다. TAIL이 있는 경우에는 parser에 2번째 인덱스가 존재하지만 없다면 1까지만 존재한다. 따라서 이를 try~ except ~ 예외처리 구문을 사용해서 추가하도록 한다.

https://programmers.co.kr/learn/courses/30/lessons/17686

문제:

풀이방법:

LZW 압축 과정대로 코드를 작성하면 된다.

 우선 길이가 1인 모든 단어를 포함해서 사전을 구축해야 하므로 dictionary에 밑과 같이 구축한다. 그 뒤에 idx가 입력으로 들어온 문자열의 길이와 같아질 때까지 반복해서 확인하고 추가하는 작업을 한다.

 LZW 압축과정은 다음과 같이 작동된다.

1. KAKAO의 경우에 KAKAO와 인덱스 0 그리고 사전이 check로 입력된다.

2. 이를 뒤에서부터 비교를 한다. 즉 KAKAO가 사전에 있는가? -> KAKA가 사전에 있는가? -> .... 순으로 진행이 되고 K가 사전에 있는가에서 참이므로 break를 걸고 반복문 밖으로 나온다.

3. 그러면 KA는 사전에 없는 단어였으므로 사전에 추가하고 인덱스와 사전을 반환한다.

4. check에서 나온 인덱스와 check에 넣기 전에 사용한 인덱스를 사용해서 슬라이싱을 하고 이를 사전의 색인 번호를 answer에 추가한다.

5. idx를 i로 지정한다.

 idx가 msg와 동일할 떄까지 진행을 하면 압축과정이 끝나게 된다.

문제링크:

https://programmers.co.kr/learn/courses/30/lessons/17684

문제:

풀이방법:

 이 문제에서 처리해야 할 것은 크게 두 가지이다. 재생된 시간의 길이에 따라서 음이 달라지므로 시간 형식으로 되어 있는 자료형을 분 단위로 바꿔야 한다. 그리고 음계 중에 C#, D#, F#, G#과 같이 #이 붙어 있는 음계가 있는데 스트링 형식으로 되어 있기 때문에 이들도 하나의 인덱스를 차지하고 있으므로 처리하는 방법에 대해서 생각해야 한다.

 우선 분으로 바꾸기 위해서 :를 기준으로 분할을 한다. 시작하는 분과 끝나는 분을 비교해서 음악의 총 재생된 시간을 구하도록 한다.

 C#과 같이 #이 달려있는 음들은 하나의 인덱스로 처리를 하는 것이 편하므로 소문자로 변경하도록 한다. (C#->c , D# ->d , ....) 이 작업을 하고 위에서 구한 재생된 시간으로 실제 재생된 멜로디를 구할 수 있고, 이 안에 m이 있는지 판단하여서 answers 리스트에 담도록 한다. 

 이 때 조건이 일치하는 음악이 여러 개일 경우에는 재생된 시간이 제일 긴 음악, 먼저 입력된 음악 제목 순으로 정렬해야 하므로 (재생된 시간, 입력된 인덱스,음악제목)과 같이 answers에 넣도록 한다.

 일치하는 음악을 모두 담았다면 sort의 key를 이용해서 위 조건에 맞게 정렬을 하도록 한다. 재생된 시간은 길수록 앞으로 와야 하므로 음수를 붙여주고, 먼저 입력된 것이 앞으로 와야 하므로 이는 양수로 정렬하도록 한다. 이렇게 정렬을 하고 난 뒤에 answers에 가장 앞에 있는 값의 맨 마지막 값을 출력한다면 그것이 음악제목일 것이다. (만약 answers가 비어 있다면 "(None)"을 출력해야 한다.

문제링크:

https://programmers.co.kr/learn/courses/30/lessons/17683

문제:

풀이방법:

 처음에는 스택으로 구축할까 생각하다가 많이 복잡할 것 같아서 슬라이싱을 활용한 문자열 비교로 해결하기로 하였다. 

문자열의 길이가 1이면 항상 답은 1이라는 예외처리로 시작한다. 몇 개 단위로 자르는 것이 가장 짧은 방법인지 알지 못하므로 1부터 len(s)까지 분할 하도록 한다. i개의 단어로 자르면서 앞과 현재가 같다면 count를 하나올려주도록 한다. 만약 다르다면 count를 비교해보도록 한다. count가 1이라면 그냥 문자열에 더하고, 1이 아니라면 숫자를 같이 더해주도록 한다.

 이렇게 각 길이의 단위로 자른 문자열을 모두 담았다면 가장 작은 값을 반환하도록 한다.

문제링크:

https://programmers.co.kr/learn/courses/30/lessons/60057

문제:

풀이방법:

아이디에 따른 명령어와 이름을 해시 방식으로 저장을 해줌으로써 데이터를 관리하였다. 이름을 바꾸는 경우에는 맨마지막에 해당하는 이름으로 모두 반영이 되므로 Change가 나올 때마다 덮어주는 방식으로 진행하였다. 이 외에는 명령어에 따라서 알맞게 출력해주면 된다.

문제링크:

https://programmers.co.kr/learn/courses/30/lessons/42888

문제:

 창영이는 민균이의 컴퓨터를 해킹해 텍스트 파일 하나를 자신의 메일로 전송했다. 파일에는 단어가 한 줄에 하나씩 적혀있었고, 이 중 하나는 민균이가 온라인 저지에서 사용하는 비밀번호이다.

파일을 살펴보던 창영이는 모든 단어의 길이가 홀수라는 사실을 알아내었다. 그리고 언젠가 민균이가 이 목록에 대해서 얘기했던 것을 생각해냈다. 민균이의 비밀번호는 목록에 포함되어 있으며, 비밀번호를 뒤집어서 쓴 문자열도 포함되어 있다.

예를 들어, 민균이의 비밀번호가 "tulipan"인 경우에 목록에는 "napilut"도 존재해야 한다. 알 수 없는 이유에 의해 모두 비밀번호로 사용 가능하다고 한다.

민균이의 파일에 적혀있는 단어가 모두 주어졌을 때, 비밀번호의 길이와 가운데 글자를 출력하는 프로그램을 작성하시오.

입력:

첫째 줄에 단어의 수 N(2<=N<=100)이 주어진다. 다음 N개의 줄에는 파일에 적혀있는 단어가 한 줄에 하나씩 주어진다.

단어는 알파벳 소문자로만 이루어져 있으며, 길이는 2보다 크고 14보다 작은 홀수이다.

출력:

첫째 줄에 비밀번호의 길이와 가운데 글자를 출력한다. 항상 답이 유일한 경우만 입력으로 주어진다.

풀이방법:

 처음 단어를 받을때 원래 단어와 뒤집은 단어 두개씩 넣도록 하였다. 이렇게 한다면 비밀번호인 단어는 words라는 배열에 두 개씩 담기게 될 것이다.

 그리고 이 words라는 배열에 set을 취하게 되면 중복인 것들이 사라지게 되고, words에 set을 한번 한 배열을 빼면 비밀번호인 문자만 남게 될 것이다. 항상 홀수 길이의 단어이므로 둘 중 어느것의 가운데 글자를 출력해도 상관없으니 아무 것이나 선택해서 출력하도록 했다.

문제링크:

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