Algorithms, Data Analytics

문제 난이도 : 하

문제 유형 : 해시, 배열, 구현

추천 풀이 시간 : 20분

문제

N개의 정수 A[1], A[2], …, A[N]이 주어져 있을 때, 이 안에 X라는 정수가 존재하는지 알아내는 프로그램을 작성하시오.

입력

첫째 줄에 자연수 N(1≤N≤100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1≤M≤100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들이 A안에 존재하는지 알아내면 된다. 모든 정수들의 범위는 int 로 한다.

출력

M개의 줄에 답을 출력한다. 존재하면 1을, 존재하지 않으면 0을 출력한다.

n = int(input())

data = set(map(int,input().split()))

m = int(input())

test = list(map(int, input().split()))

for i in range(m):
    
    if test[i] in data:
        print(1)
        
    else:
        print(0)

풀어봤는데 답은 맞았다 근데 이상하게 data를 set구조가 아니라 list로 하면 시간 초과가 나온다.

list로 하면 하나하나 다 따져봐서 그런건가

set은 하나의 집합 느낌이고 음..

문제 난이도 : 중

문제 유형 : 스택, 구현, 그리디

추천 풀이 시간 : 40분

문제

창영이는 강산이의 비밀번호를 훔치기 위해서 강산이가 사용하는 컴퓨터에 키로거를 설치했다. 며칠을 기다린 끝에 창영이는 강산이가 비밀번호 창에 입력하는 글자를 얻어냈다.

키로거는 사용자가 키보드를 누른 명령을 모두 기록한다. 따라서, 강산이가 비밀번호를 입력할 때, 화살표나 백스페이스를 입력해도 정확한 비밀번호를 알아낼 수 있다.

강산이가 비밀번호 창에서 입력한 키가 주어졌을 때, 강산이의 비밀번호를 알아내는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스는 한줄로 이루어져 있고, 강산이가 입력한 순서대로 길이가 L인 문자열이 주어진다. (1 ≤ L의 길이 ≤ 1,000,000) 강산이가 백스페이스를 입력했다면, '-'가 주어진다. 이때 커서의 바로 앞에 글자가 존재한다면, 그 글자를 지운다. 화살표의 입력은 '<'와 '>'로 주어진다. 이때는 커서의 위치를 움직일 수 있다면, 왼쪽 또는 오른쪽으로 1만큼 움직인다. 나머지 문자는 비밀번호의 일부이다. 물론, 나중에 백스페이스를 통해서 지울 수는 있다. 만약 커서의 위치가 줄의 마지막이 아니라면, 그 문자를 입력하고, 커서는 오른쪽으로 한 칸 이동한다.

출력

각 테스트 케이스에 대해서, 강산이의 비밀번호를 출력한다. 비밀번호의 길이는 항상 0보다 크다.

n = int(input())

for _ in range(n):
    
    stack_1 = []
    stack_2 = []
    data = input()
    
    for item in data:
        
        if item == '-':
            if stack_1:
                stack_1.pop()
        
        elif item == '<':
            if stack_1:
                stack_2.append(stack_1.pop())

        elif item == '>':
            if stack_2:
                stack_1.append(stack_2.pop())
            
        else:
            stack_1.append(item)
            
    stack_2.reverse()
    print(''.join(stack_1 + stack_2))

처음에는 입력 값을 받아서 그 안에서 해결하여 출력하려고 했지만

잘 안됐다.. 그래서 강의 봄

스택 2개를 사용하여 푸셨다.

문제를 보면 무슨 말인지는 알겠는데 구현이 참 어렵다.

문제

여러분도 알다시피 여러분의 프린터 기기는 여러분이 인쇄하고자 하는 문서를 인쇄 명령을 받은 ‘순서대로’, 즉 먼저 요청된 것을 먼저 인쇄한다. 여러 개의 문서가 쌓인다면 Queue 자료구조에 쌓여서 FIFO - First In First Out - 에 따라 인쇄가 되게 된다. 하지만 상근이는 새로운 프린터기 내부 소프트웨어를 개발하였는데, 이 프린터기는 다음과 같은 조건에 따라 인쇄를 하게 된다.

1. 현재 Queue의 가장 앞에 있는 문서의 ‘중요도’를 확인한다.
2. 나머지 문서들 중 현재 문서보다 중요도가 높은 문서가 하나라도 있다면, 이 문서를 인쇄하지 않고 Queue의 가장 뒤에 재배치 한다. 그렇지 않다면 바로 인쇄를 한다.

예를 들어 Queue에 4개의 문서(A B C D)가 있고, 중요도가 2 1 4 3 라면 C를 인쇄하고, 다음으로 D를 인쇄하고 A, B를 인쇄하게 된다.

여러분이 할 일은, 현재 Queue에 있는 문서의 수와 중요도가 주어졌을 때, 어떤 한 문서가 몇 번째로 인쇄되는지 알아내는 것이다. 예를 들어 위의 예에서 C문서는 1번째로, A문서는 3번째로 인쇄되게 된다.

입력

첫 줄에 test case의 수가 주어진다. 각 test case에 대해서 문서의 수 N(100이하)와 몇 번째로 인쇄되었는지 궁금한 문서가 현재 Queue의 어떤 위치에 있는지를 알려주는 M(0이상 N미만)이 주어진다. 다음줄에 N개 문서의 중요도가 주어지는데, 중요도는 1 이상 9 이하이다. 중요도가 같은 문서가 여러 개 있을 수도 있다. 위의 예는 N=4, M=0(A문서가 궁금하다면), 중요도는 2 1 4 3이 된다.

출력

각 test case에 대해 문서가 몇 번째로 인쇄되는지 출력한다.

case = int(input())

for i in range(case):
    count = 0
    n, m = map(int, input().split())
    queue = list(map(int, input().split()))
    queue = [(item, idx) for idx, item in enumerate(queue)]
        
    while True:
        
        if (queue[0][0] == max(queue, key = lambda x: x[0])[0]):
            count += 1
            
            if queue[0][1] == m:
                print(count)
                break
                
            else:
                queue.pop(0)
                
        else:
            queue.append(queue.pop(0))

lambda의 사용법과 데이터에 인덱스를 같이 붙여서 리스트화 시킬 수 있는 것 그리고

queue에 데이터를 뽑아내는 동시에 append 할 수 있는 기술을 알게 되었다.