https://school.programmers.co.kr/learn/courses/30/lessons/64064

문제

개발팀 내에서 이벤트 개발을 담당하고 있는 "무지"는 최근 진행된 카카오이모티콘 이벤트에 비정상적인 방법으로 당첨을 시도한 응모자들을 발견하였습니다. 이런 응모자들을 따로 모아 불량 사용자라는 이름으로 목록을 만들어서 당첨 처리 시 제외하도록 이벤트 당첨자 담당자인 "프로도" 에게 전달하려고 합니다. 이 때 개인정보 보호을 위해 사용자 아이디 중 일부 문자를 '*' 문자로 가려서 전달했습니다. 가리고자 하는 문자 하나에 '*' 문자 하나를 사용하였고 아이디 당 최소 하나 이상의 '*' 문자를 사용하였습니다.
"무지"와 "프로도"는 불량 사용자 목록에 매핑된 응모자 아이디를 제재 아이디 라고 부르기로 하였습니다.

입출력

제한사항에 대해 보고싶으면 눌러주세요

풀이방법

일단, 제재 아이디가 아이디의 수에 따라서 다양하게 나오는 것을 통해 조합을 사용해야할 것을 떠올렸고 풀이 순서는 다음과 같다.

1. user_list를 기준으로 조합을 모든 조합을 만든다.
2. 각각 조합이 banned_id와 일치하는지 확인한다.
3. 일치한다면 set 자료구조에 추가한다.
4. set 자료구조의 길이를 구한다.

4가지 단계로 구성해서 문제를 해결했다.

코드

import itertools

def check(user, banned_id):
    for i in range(len(banned_id)):
        if len(user[i]) != len(banned_id[i]):
            return False

        for j in range(len(user[i])):
            if banned_id[i][j] == "*":
                continue
            if banned_id[i][j] != user[i][j]:
                return False
    return True

def solution(user_id, banned_id):
    user_permutation = list(itertools.permutations(user_id, len(banned_id)))
    ban_set = []
    
    for user in user_permutation:
        if not check(user, banned_id):
            continue
        else:
            user = set(user)
            if user not in ban_set:
                ban_set.append(user)
    
    
    return len(ban_set)
            



if __name__ == "__main__":
    print(solution(["frodo", "fradi", "crodo", "abc123", "frodoc"],
                   ["fr*d*", "*rodo", "******", "******"]))

https://school.programmers.co.kr/learn/courses/30/lessons/87390

문제

정수 n, left, right가 주어집니다. 다음 과정을 거쳐서 1차원 배열을 만들고자 합니다.

n행 n열 크기의 비어있는 2차원 배열을 만듭니다.
i = 1, 2, 3, ..., n에 대해서, 다음 과정을 반복합니다.
1행 1열부터 i행 i열까지의 영역 내의 모든 빈 칸을 숫자 i로 채웁니다.
1행, 2행, ..., n행을 잘라내어 모두 이어붙인 새로운 1차원 배열을 만듭니다.
새로운 1차원 배열을 arr이라 할 때, arr[left], arr[left+1], ..., arr[right]만 남기고 나머지는 지웁니다.
정수 n, left, right가 매개변수로 주어집니다. 주어진 과정대로 만들어진 1차원 배열을 return 하도록 solution 함수를 완성해주세요.

입출력

제한사항에 대해 보고싶으면 눌러주세요

풀이방법

첫번째 풀이 방법

일단, 처음으로 제한사항에서 n이 $10^7$인 것을 보고서, 시간복잡도 문제가 무조건 생길것이라고 판단하였다. 

이러한 형식의 배열을 만들고 펼치는 과정에서 시간초과가 발생할 것이라고 생각했다.

바로 이 과정을 만드는 방법에 대해 고민을 하기 시작했다. 그래서 배열을 펼치는 방식 구현을 생각했다. 

위와 같은 형식일 때, 몫과 나머지를 이용하는 것을 깨닫고 다음과 같은 형식으로 변환했다.

변환을 진행하고 몫과 나머지 중에서 큰 값을 반환하도록 했다. 다음과 같은 방식으로 해결했다.

코드

def cal_ans(n, idx):
    q, m = idx // n + 1, idx % n 
    
    if m == 0: m += n; q -= 1
    
    if q > m:
        return q
    else:
        return m


def solution(n, left, right):
    answer = []
    for idx in range(left, right+1):
        answer.append(cal_ans(n,idx + 1))
    return answer


if __name__ == "__main__":
    print(solution(4,7,14))

두번째 풀이 방법

단순히 몫과 나머지 중에서 큰 값 + 1을 하면 된다. 여기서 이 것을 깨닫고 좀 현타가 왔다.

코드

def solution(n, left, right):
    answer = []
    for i in range(left,right+1):
        answer.append(max(i//n,i%n)+1)
    return answer

https://school.programmers.co.kr/learn/courses/30/lessons/169199

문제

리코쳇 로봇이라는 보드게임이 있습니다.

이 보드게임은 격자모양 게임판 위에서 말을 움직이는 게임으로, 시작 위치에서 목표 위치까지 최소 몇 번만에 도달할 수 있는지 말하는 게임입니다.

이 게임에서 말의 움직임은 상, 하, 좌, 우 4방향 중 하나를 선택해서 게임판 위의 장애물이나 맨 끝에 부딪힐 때까지 미끄러져 이동하는 것을 한 번의 이동으로 칩니다.

다음은 보드게임판을 나타낸 예시입니다.

...D..R
.D.G...
....D.D
D....D.
..D....

여기서 "."은 빈 공간을, "R"은 로봇의 처음 위치를, "D"는 장애물의 위치를, "G"는 목표지점을 나타냅니다.
위 예시에서는 "R" 위치에서 아래, 왼쪽, 위, 왼쪽, 아래, 오른쪽, 위 순서로 움직이면 7번 만에 "G" 위치에 멈춰 설 수 있으며, 이것이 최소 움직임 중 하나입니다.

게임판의 상태를 나타내는 문자열 배열 board가 주어졌을 때, 말이 목표위치에 도달하는데 최소 몇 번 이동해야 하는지 return 하는 solution함수를 완성하세요. 만약 목표위치에 도달할 수 없다면 -1을 return 해주세요.

입출력

제한사항에 대해 보고싶으면 눌러주세요

풀이방법

사용한 알고리즘 : BFS

1. board 와 같은 size인 matrix를 생성하고 99999999로 칸을 채웁니다.

-> 99999999로 되어 있는 칸은 방문하지 않은 칸을 의미합니다.

2. R의 위치를 찾고 deq에 위치를 저장합니다.

3. deq에서 popleft한 요소는 현재 위치를 가리킵니다.

  3-1 현재 위치에 G가 있다면 반복문을 탈출하고 현재 cnt를 반환합니다.

4. x, y에 dx[i],dy[i] 를 더해서 다음 위치가 D를 만나지 않거나 좌표 밖으로 나가지 않는다면 더합니다.

5. 만약 좌표 밖이나 D를 만나게 된다면 현재 위치의 cnt + 1 와 matrix에 저장되어있는 수를 비교해서 더 작은 수를 저장합니다.

6. 현재 좌표 nx, ny, cnt + 1 를 deq에 넣고  3번으로 돌아갑니다.

코드

from collections import deque


def solution(board):
    answer = 0
    N, M = len(board), len(board[0])
    deq = deque()
    matrix = [[999999999] * M for _ in range(N)]


    # R 찾기
    for i in range(N):
        for j in range(M):
            if board[i][j] == 'R':
                deq.append((i, j, 0))
                matrix[i][j] = 0


    dx = [-1, 1, 0, 0]
    dy = [0, 0, -1, 1]

    while deq:
        x, y, cnt = deq.popleft()

        if board[x][y] == 'G':
            return cnt

        for i in range(4):
            nx = x
            ny = y

            while 0 <= nx + dx[i] < N and 0 <= ny + dy[i] < M and board[nx + dx[i]][ny + dy[i]] != 'D':
                nx += dx[i]
                ny += dy[i]

            if matrix[nx][ny] > cnt + 1:
                matrix[nx][ny] = cnt + 1
                deq.append((nx, ny,cnt+1))

    return -1

결론

BFS를 이용해서 x, y 에 dx, dy를 더하면서 멈출 때까지 반복하고 cnt를 저장하면 정말 간단하게 풀 수 있는 문제다.

처음에 그래프를 구현할 때 오랜만이라 시간이 걸리기는 했지만 약 1시간을 투자해서 문제를 풀었다. 그래프 문제를 더 열심히 풀어봐야겠다.

그리고 list가 아니라 deque를 넣어 풀어서 시간이 더 단축되었다.

문제

수빈이는 TV를 보고 있다. 수빈이는 채널을 돌리려고 했지만, 버튼을 너무 세게 누르는 바람에, 일부 숫자 버튼이 고장 났다.

리모컨에는 버튼이 0부터 9까지 숫자, +와 -가 있다. +를 누르면 현재 보고 있는 채널에서 +1된 채널로 이동하고, -를 누르면 -1된 채널로 이동한다. 채널 0에서 -를 누른 경우에는 채널이 변하지 않고, 채널은 무한대만큼 있다.

수빈이가 지금 이동하려고 하는 채널은 N이다. 어떤 버튼이 고장 났는지 주어졌을 때, 채널 N으로 이동하기 위해서 버튼을 최소 몇 번 눌러야 하는지 구하는 프로그램을 작성하시오.

수빈이가 지금 보고 있는 채널은 100번이다.

입력

출력

풀이방법

알고리즘은 생각보다 간단했다.

1. 만들 수 있는 수 중에서 목표와 가장 가까운 수를 찾는다.

2. 가장 가까운 수와 목표 번호와의 차이를 구한다.

가장 가까운 수를 찾는 방법 = 브루트포스를 사용하면 된다.

1부터 시작해서 1,000,000까지 숫자 중 만들 수 있는 수를 찾는다.

알고리즘 구현은 밑에 코드에 자세하게 적어놨다.

코드

# gold
# 리모컨
import sys

def main():
    target = int(input())
    # ++ or -- 로 이동할 경우 -> 최댓값
    ans = abs(100 - target)  
    
    # 고장난 버튼 입력
    M = int(input())
    if M > 0:
        broken = set(input().split())
    else:
        broken = set()

    # 작은수에서 큰수로 이동할 땐 500,000이며
    # 큰수에서 작은수로 이동할 땐 1,000,000까지 봐야한다.
    for num in range(1000001):
        for N in str(num):
        	# 만들 수 없는 숫자인 경우
            if N in broken: 
                break
        # 만들 수 있는 숫자인 경우  
        else:  
            # min(기존 답, 버튼을 누른 횟수 + 해당 번호와의 차이)
            if ans > len(str(num)) + abs(num - target):
                ans = len(str(num)) + abs(num - target)

    print(ans)


if __name__ == '__main__':
    input = sys.stdin.readline
    main()

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

문제

solved.ac는 Sogang ICPC Team 학회원들의 알고리즘 공부에 도움을 주고자 만든 서비스이다. 지금은 서강대뿐만 아니라 수많은 사람들이 solved.ac의 도움을 받아 알고리즘 공부를 하고 있다.

ICPC Team은 백준 온라인 저지에서 문제풀이를 연습하는데, 백준 온라인 저지의 문제들에는 난이도 표기가 없어서, 지금까지는 다양한 문제를 풀어 보고 싶더라도 난이도를 가늠하기 어려워 무슨 문제를 풀어야 할지 판단하기 곤란했기 때문에 solved.ac가 만들어졌다. solved.ac가 생긴 이후 전국에서 200명 이상의 기여자 분들께서 소중한 난이도 의견을 공유해 주셨고, 지금은 약 7,000문제에 난이도 표기가 붙게 되었다.

어떤 문제의 난이도는 그 문제를 푼 사람들이 제출한 난이도 의견을 바탕으로 결정한다. 난이도 의견은 그 사용자가 생각한 난이도를 의미하는 정수 하나로 주어진다. solved.ac가 사용자들의 의견을 바탕으로 난이도를 결정하는 방식은 다음과 같다.

• 아직 아무 의견이 없다면 문제의 난이도는 0으로 결정한다.
• 의견이 하나 이상 있다면, 문제의 난이도는 모든 사람의 난이도 의견의 30% 절사평균으로 결정한다.

절사평균이란 극단적인 값들이 평균을 왜곡하는 것을 막기 위해 가장 큰 값들과 가장 작은 값들을 제외하고 평균을 내는 것을 말한다. 30% 절사평균의 경우 위에서 15%, 아래에서 15%를 각각 제외하고 평균을 계산한다. 따라서 20명이 투표했다면, 가장 높은 난이도에 투표한 3명과 가장 낮은 난이도에 투표한 3명의 투표는 평균 계산에 반영하지 않는다는 것이다.

제외되는 사람의 수는 위, 아래에서 각각 반올림한다. 25명이 투표한 경우 위, 아래에서 각각 3.75명을 제외해야 하는데, 이 경우 반올림해 4명씩을 제외한다.

마지막으로, 계산된 평균도 정수로 반올림된다. 절사평균이 16.7이었다면 최종 난이도는 17이 된다.

사용자들이 어떤 문제에 제출한 난이도 의견 목록이 주어질 때, solved.ac가 결정한 문제의 난이도를 계산하는 프로그램을 작성하시오.

입력

출력

풀이방법

1. 입력을 모두 배열에 추가한다.

2. 배열을 정렬한다.

3. 범위를 지정하여 합을 구한다.

4. 합을 범위의 길이만큼으로 나눈다.

5.값을 정수형으로 출력한다.

* 여기서 파이썬의 round 함수의 오사오입과 사사오입 문제를 이해하고 따로 함수를 만들어 해결해야 한다. 그 방식에 대해서는 밑의 글에서 설명했다.

https://giliit.tistory.com/80

코드

# silver
# solved.ac
# 절사평균 30 : 위 15%, 아래 15%

import sys
from math import ceil, floor

# 파이썬의 사사오입, 오사오입 해결위한 방법
def custom_round(num):
    if num % 1 >= 0.5:
        return int(ceil(num))
    else:
        return int(floor(num))

def main():
    n = int(input())
    lst = []
    # 배열 입력
    for _ in range(n):
        tmp = int(input())
        lst.append(tmp)

	# 상위 15%와 하위 15% 수치를 구한다.
    k = int(custom_round(n * 0.15))
    
    # 배열을 정렬한다.
    lst.sort()
	
    # 0인 경우, 0 출력, 0이 아닌 경우, 값을 출력한다.
    if n == 0:
        print(0)
    else:
        print(int(custom_round(sum(lst[k:n-k])/(n-2*k))))



if __name__ == "__main__":
    input = sys.stdin.readline
    main()

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개이다.

입력

출력

풀이방법

C++언에서 Substr을 이용해서 문자열을 slicing 한다. 이후에 set 자료구조를 이용해 중복을 제거하고 출련한다.

코드

#include<bits/stdc++.h>
#define fastio ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
using namespace std;

int main()
{
  fastio;
  string str; cin>>str;

  set<string> sstr;

  for(int i=0;i<str.size();i++)
  {
    for(int j=1;j+i<=str.size();j++)
      sstr.insert(str.substr(i,j));
  }
  cout<<sstr.size();
}

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

문제

친구로부터 노트북을 중고로 산 스브러스는 노트북을 켜자마자 경악할 수밖에 없었다. 바탕화면에 온갖 파일들이 정리도 안 된 채 가득했기 때문이다. 그리고 화면의 구석에서 친구의 메시지를 확인할 수 있었다.

바탕화면의 파일들에는 값진 보물에 대한 정보가 들어 있어. 하나라도 지우게 된다면 보물은 물론이고 다시는 노트북을 쓸 수 없게 될 거야. 파일들을 잘 분석해서 보물의 주인공이 될 수 있길 바랄게. 힌트는 “확장자”야.

화가 났던 스브러스는 보물 이야기에 금세 화가 풀렸고 보물의 정보를 알아내려고 애썼다. 하지만 파일이 너무 많은 탓에 이내 포기했고 보물의 절반을 보상으로 파일의 정리를 요청해왔다. 스브러스의 요청은 다음과 같다.

• 파일을 확장자 별로 정리해서 몇 개씩 있는지 알려줘
• 보기 편하게 확장자들을 사전 순으로 정렬해 줘

그럼 보물의 절반을 얻어내기 위해 얼른 스브러스의 노트북 파일 정리를 해줄 프로그램을 만들자!

입력

출력

풀이방법

1. 파일을 파일이름과 파일 확장자로 나눈다.

2. 파일 확장자를 dictionary를 사용해 처음 나오는 확장자라면 value = 1을, 이전에 나온 확장자라면 value = value + 1

ex) 

3. 확장자(key)의 값들을 정렬한다.

4. 정렬된 확장자들을 차례대로 출력하면서 value값도 출력한다.

코드

# silver
# 파일 정리

import sys

def main():
    n = int(input())
    file = dict()
    
    # 파일이름과 파일 확장자로 나누는 코드
    for _ in range(n):
        file_name, file_extension = input().rstrip().split('.')
        
        # 처음나오는 확장자라면 dict에 추가
        if file_extension not in file:
            file[file_extension] = 1
        # 이전에 나온 확장자라면 dict에서 + 1을 한다.
        else:
            file[file_extension] += 1
    
    # key들을 정렬한다.
    file_extension_lst = sorted(file.keys())
    
    # key와 value들을 차례대로 출력한다.
    for i in file_extension_lst:
        print(f'{i} {file[i]}\n')

if __name__ == '__main__':
    input = sys.stdin.readline
    print = sys.stdout.write
    main()

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

문제

김진영이 듣도 못한 사람의 명단과, 보도 못한 사람의 명단이 주어질 때, 듣도 보도 못한 사람의 명단을 구하는 프로그램을 작성하시오.

입력

출력

풀이방법

1. 듣도 못한 사람을 set에 추가한다.

2. 보도 못한 사람이 set에 있다면 KK 에 추가한다.

3. KK라는 요소들을 출력한다.

코드

#include<bits/stdc++.h>
using namespace std;


int main()
{
  int a,b;
  cin>>a>>b;
  set <string> K;
  
  // 듣도 못한 사람을 추가한다.
  while(a--)
  {
    string temp;  cin>>temp;
    K.insert(temp);
  }
  set<string> KK;
  // 보도 못한 사람이 듣도 못한 사람에 있다면 KK에 추가한다.
  while(b--)
  {
    string temp; cin>>temp;
    if(K.count(temp)) KK.insert(temp);
  }

  // 듣도 보도 못한 사람을 출력한다.
  cout<<KK.size()<<"\n";
  for(auto k : KK)
  {
    cout<<k<<"\n";
  }

}

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

문제

79를 영어로 읽되 숫자 단위로 하나씩 읽는다면 "seven nine"이 된다. 80은 마찬가지로 "eight zero"라고 읽는다. 79는 80보다 작지만, 영어로 숫자 하나씩 읽는다면 "eight zero"가 "seven nine"보다 사전순으로 먼저 온다.

문제는 정수 M, N(1 ≤ M ≤ N ≤ 99)이 주어지면 M 이상 N 이하의 정수를 숫자 하나씩 읽었을 때를 기준으로 사전순으로 정렬하여 출력하는 것이다.

입력

출력

풀이방법

1. N to M의 숫자를 문자로 변환하여 arr에 추가한다.

2. arr의 문자들을 알파벳 숫서대로 정렬한다.

3. 정렬한 arr의 문자들을 숫자로 변환한다.

4. 양식에 맞게 10개 출력 후 줄바꿈을 한다.

코드

# silver
# 숫자놀이

import sys

def main():
    num = ['zero ', 'one ', 'two ', 'three ', 'four ', 'five ', 'six ', 'seven ', 'eight ', 'nine ']
    num_dict = {'zero': '0','one':'1', 'two':'2','three':'3' , 'four':'4', 'five' : '5', 'six' : '6', 'seven': '7', 'eight' : '8', 'nine' : '9'}
    arr = []
    n, m = map(int, input().rstrip().split())
    
    # 숫자 -> 문자 변환
    for i in range(n,m+1):
        i_lst = list(str(i))
        i_str = ""
        for j in range(len(i_lst)):
            i_str += num[int(i_lst[j])]
        arr.append(i_str)
    
    # 문자 정렬
    arr.sort()

	# 문자 -> 숫자 변환 및 출력
    for i in range(len(arr)):
        a = arr[i].split()
        tmp = ''
        for k in a:
            tmp += num_dict[k]
        print(tmp+" ",end='')
        
        # 10개 출력 후 줄 바꿈
        if i % 10 == 9:
            print()


if __name__ == '__main__':
    main()

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

문제

두 단어 A와 B가 주어졌을 때, A에 속하는 알파벳의 순서를 바꾸어서 B를 만들 수 있다면, A와 B를 애너그램이라고 한다.

두 단어가 애너그램인지 아닌지 구하는 프로그램을 작성하시오.

입력

출력

풀이방법

2개의 문장을 정렬한다.

2개의 문장이 동일하다면 애너그램이며, 동일하지 않으면 애너그램이 아니다.

코드

# bronze
# 애너그램

import sys

def main():

    n = int(input())
    for _ in range(n):
        a, b = map(list,input().rstrip().split())
        a_sorted = sorted(a)
        b_sorted = sorted(b)
		
        # 정렬한 문장이 동일하다면
        if a_sorted == b_sorted:
            print(f"{''.join(a)} & {''.join(b)} are anagrams.")
		
        # 정렬한 문장이 동일하지 않다면
        else:
            print(f"{''.join(a)} & {''.join(b)} are NOT anagrams.")

if __name__ == '__main__':
    input = sys.stdin.readline
    main()