IT-garden

문제 설명

수평 직선에 탑 N대를 세웠습니다. 모든 탑의 꼭대기에는 신호를 송/수신하는 장치를 설치했습니다. 발사한 신호는 신호를 보낸 탑보다 높은 탑에서만 수신합니다. 또한, 한 번 수신된 신호는 다른 탑으로 송신되지 않습니다.

예를 들어 높이가 6, 9, 5, 7, 4인 다섯 탑이 왼쪽으로 동시에 레이저 신호를 발사합니다. 그러면, 탑은 다음과 같이 신호를 주고받습니다. 높이가 4인 다섯 번째 탑에서 발사한 신호는 높이가 7인 네 번째 탑이 수신하고, 높이가 7인 네 번째 탑의 신호는 높이가 9인 두 번째 탑이, 높이가 5인 세 번째 탑의 신호도 높이가 9인 두 번째 탑이 수신합니다. 높이가 9인 두 번째 탑과 높이가 6인 첫 번째 탑이 보낸 레이저 신호는 어떤 탑에서도 수신할 수 없습니다.

송신 탑(높이)수신 탑(높이)

맨 왼쪽부터 순서대로 탑의 높이를 담은 배열 heights가 매개변수로 주어질 때 각 탑이 쏜 신호를 어느 탑에서 받았는지 기록한 배열을 return 하도록 solution 함수를 작성해주세요.

제한조건

• heights는 길이 2 이상 100 이하인 정수 배열입니다.
• 모든 탑의 높이는 1 이상 100 이하입니다.
• 신호를 수신하는 탑이 없으면 0으로 표시합니다.

입출력 예

입출력 예 설명

입출력 예 #1
앞서 설명한 예와 같습니다.

입출력 예 #2

[1,2,3] 번째 탑이 쏜 신호는 아무도 수신하지 않습니다.
[4,5,6] 번째 탑이 쏜 신호는 3번째 탑이 수신합니다.
[7] 번째 탑이 쏜 신호는 6번째 탑이 수신합니다.

입출력 예 #3

[1,2,4,5] 번째 탑이 쏜 신호는 아무도 수신하지 않습니다.
[3] 번째 탑이 쏜 신호는 2번째 탑이 수신합니다.
[6] 번째 탑이 쏜 신호는 5번째 탑이 수신합니다.
[7] 번째 탑이 쏜 신호는 6번째 탑이 수신합니다.

나의 풀이

def solution(heights):
    answer = [0] * len(heights)
    for i in range(1,len(heights)):
        for j in range(i-1,-1,-1):
            if heights[i] < heights[j]:
                answer[i] = j + 1
                break
    return answer

1. i는 쏘는 신호, j는 받는 신호
2. j가 더 클 경우 answer의 값을 바꾸고 다음으로 넘어갑니다.

프로그래머스 '탑' : https://programmers.co.kr/learn/courses/30/lessons/42588

문제 설명

전화번호부에 적힌 전화번호 중, 한 번호가 다른 번호의 접두어인 경우가 있는지 확인하려 합니다.
전화번호가 다음과 같을 경우, 구조대 전화번호는 영석이의 전화번호의 접두사입니다.

• 구조대 : 119
• 박준영 : 97 674 223
• 지영석 : 11 9552 4421

전화번호부에 적힌 전화번호를 담은 배열 phone_book 이 solution 함수의 매개변수로 주어질 때, 어떤 번호가 다른 번호의 접두어인 경우가 있으면 false를 그렇지 않으면 true를 return 하도록 solution 함수를 작성해주세요.

제한조건

• phone_book의 길이는 1 이상 1,000,000 이하입니다.
• 각 전화번호의 길이는 1 이상 20 이하입니다.

입출력 예

입출력 예 설명

입출력 예 #1
앞에서 설명한 예와 같습니다.

입출력 예 #2
한 번호가 다른 번호의 접두사인 경우가 없으므로, 답은 true입니다.

입출력 예 #3
첫 번째 전화번호, “12”가 두 번째 전화번호 “123”의 접두사입니다. 따라서 답은 false입니다.

나의 풀이

def solution(phone_book):
    answer = True
    for i in range(len(phone_book)):
        a = phone_book[:i] + phone_book[i+1:] 
        for j in a:
            jj = j[:len(phone_book[i])]
            if phone_book[i] == jj:
                answer = False
                break
        if answer == False:
            break
    return answer

1. 전화번호부에 적힌 전화번호를 하나씩 기준으로 삼아 다른 번호의 접두어인 경우가 있는지 확인합니다.
2. 하나라도 접두어인 경우가 있으면 반복문을 나오고 False를 출력합니다.

다른 사람의 풀이

def solution(phoneBook):
    phoneBook = sorted(phoneBook)

    for p1, p2 in zip(phoneBook, phoneBook[1:]):
        if p2.startswith(p1):
            return False
    return True

전화번호부를 정렬하고 기준인 번호보다 뒤에 있는 전화번호부만 확인합니다.
뒤에 있는 전화번호가 기준인 번호로 시작하면 False를 리턴합니다.

프로그래머스 '전화번호 목록' : https://programmers.co.kr/learn/courses/30/lessons/42577

문제 설명

초 단위로 기록된 주식가격이 담긴 배열 prices가 매개변수로 주어질 때, 가격이 떨어지지 않은 기간은 몇 초인지를 return 하도록 solution 함수를 완성하세요.

제한조건

• prices의 각 가격은 1 이상 10,000 이하인 자연수입니다.
• prices의 길이는 2 이상 100,000 이하입니다.

입출력 예

입출력 예 설명

• 1초 시점의 ₩1은 끝까지 가격이 떨어지지 않았습니다.
• 2초 시점의 ₩2은 끝까지 가격이 떨어지지 않았습니다.
• 3초 시점의 ₩3은 1초뒤에 가격이 떨어집니다. 따라서 1초간 가격이 떨어지지 않은 것으로 봅니다.
• 4초 시점의 ₩2은 1초간 가격이 떨어지지 않았습니다.
• 5초 시점의 ₩3은 0초간 가격이 떨어지지 않았습니다.

나의 풀이

def solution(prices):
    answer = [0] * len(prices)
    for i in range(len(prices)):
        c=0
        for j in range(i+1,len(prices)):
            c += 1
            if prices[i] > prices[j]:
                break
        answer[i] = c      
    return answer

1. 리스트 prices의 각 원소들을 기준으로 잡고 뒤의 값들과 비교합니다.
2. 만약 앞에 있는 값이 뒤에 있는 값보다 크면 for문을 나와 개수를 리스트 answer에 넣습니다.
3. 마지막에 리스트 answer를 리턴합니다.

프로그래머스 '주식가격' : programmers.co.kr/learn/courses/30/lessons/42584

문제

N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로로 이동하려 한다. 최단경로는 맵에서 가장 적은 개수의 칸을 지나는 경로를 말하는데, 이때 시작하는 칸과 끝나는 칸도 포함해서 센다.

만약에 이동하는 도중에 한 개의 벽을 부수고 이동하는 것이 좀 더 경로가 짧아진다면, 벽을 한 개 까지 부수고 이동하여도 된다.

맵이 주어졌을 때, 최단 경로를 구해 내는 프로그램을 작성하시오.

입력

첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 1,000)이 주어진다. 다음 N개의 줄에 M개의 숫자로 맵이 주어진다. (1, 1)과 (N, M)은 항상 0이라고 가정하자.

출력

첫째 줄에 최단 거리를 출력한다. 불가능할 때는 -1을 출력한다.

예제 입력과 출력

알고리즘 분류

BFS

정답

from collections import deque
import sys
input = lambda : sys.stdin.readline().rstrip()

n,m=map(int,input().split()) 
a=[list(map(int,input())) for i in range(n)]
ch=[[[0,0] for j in range(m)] for i in range(n)]

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

def bfs():
    de=deque()
    de.append([0,0,0])
    ch[0][0][0]= 1
    while de:
        x,y,z=de.popleft()

        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]

            if 0 <= nx < n and 0 <= ny < m:
                if a[nx][ny] == 0 and ch[nx][ny][z] == 0:
                    ch[nx][ny][z] = ch[x][y][z] + 1
                    de.append([nx,ny,z])
                elif a[nx][ny] == 1 and  z == 0 and ch[nx][ny][z+1] == 0: 
                    ch[nx][ny][z+1] = ch[x][y][z] +1
                    de.append([nx,ny,z+1])
                              
bfs()
if ch[n-1][m-1][0] != 0 and ch[n-1][m-1][1] != 0: # 벽을 거친 경우와 거치지 않은 경우 둘 다 가능한 경우
    print(min(ch[n-1][m-1][0],ch[n-1][m-1][1]))
elif ch[n-1][m-1][0] != 0: # 벽을 거치지 않은 경우만 가능한 경우
    print(ch[n-1][m-1][0])
elif ch[n-1][m-1][1] != 0: #벽을 거친 경우만 가능한 경우
    print(ch[n-1][m-1][1])
else: # 불가능한 경우
    print(-1)

배열 ch를 x좌표, y좌료, 부순 것 개수로 3차원으로 만듭니다.
기본 BFS에서 벽이 나왔는데 벽을 뚫은 적이 없는 경우 세번째 차수 값을 바꿔 ch에 저장하고 그 값을 큐에 넣습니다.
한번 BFS를 수행하고 벽을 거쳤을 때와 거치지 않은 것 중 최단 거리를 구합니다.

백준 알고리즘 2206번 : www.acmicpc.net/problem/2206

문제

세계는 균형이 잘 잡혀있어야 한다. 양과 음, 빛과 어둠 그리고 왼쪽 괄호와 오른쪽 괄호처럼 말이다.

정민이의 임무는 어떤 문자열이 주어졌을 때, 괄호들의 균형이 잘 맞춰져 있는지 판단하는 프로그램을 짜는 것이다.

문자열에 포함되는 괄호는 소괄호("()") 와 대괄호("[]")로 2종류이고, 문자열이 균형을 이루는 조건은 아래와 같다.

• 모든 왼쪽 소괄호("(")는 오른쪽 소괄호(")")와만 짝을 이뤄야 한다.
• 모든 왼쪽 대괄호("[")는 오른쪽 대괄호("]")와만 짝을 이뤄야 한다.
• 모든 오른쪽 괄호들은 자신과 짝을 이룰 수 있는 왼쪽 괄호가 존재한다.
• 모든 괄호들의 짝은 1:1 매칭만 가능하다. 즉, 괄호 하나가 둘 이상의 괄호와 짝지어지지 않는다.
• 짝을 이루는 두 괄호가 있을 때, 그 사이에 있는 문자열도 균형이 잡혀야 한다.

정민이를 도와 문자열이 주어졌을 때 균형잡힌 문자열인지 아닌지를 판단해보자.

입력

하나 또는 여러줄에 걸쳐서 문자열이 주어진다. 각 문자열은 영문 알파벳, 공백, 소괄호("( )") 대괄호("[ ]")등으로 이루어져 있으며, 길이는 100글자보다 작거나 같다.

입력의 종료조건으로 맨 마지막에 점 하나(".")가 들어온다.

출력

각 줄마다 해당 문자열이 균형을 이루고 있으면 "yes"를, 아니면 "no"를 출력한다.

예제 입력과 출력

알고리즘 분류

문자열 처리 

정답

import sys
input = lambda : sys.stdin.readline().rstrip()

while True:
    a=input()
    st=[]
    if a == '.':
        break

    for i in a:
        if i == '[' or i == '(':
            st.append(i)
        elif i == ']':
            if len(st) != 0 and st[-1] == '[':
                st.pop()
            else:
                st.append(']')
                break
        elif i == ')':
            if len(st) != 0 and st[-1] == '(':
                st.pop()
            else:
                st.append(')')
                break
        
    if len(st) == 0:
        print('yes')
    else:
        print('no')

백준 알고리즘 4949번 : www.acmicpc.net/problem/4949

문제

나코더 기장 재민이는 동아리 회식을 준비하기 위해서 장부를 관리하는 중이다.

재현이는 재민이를 도와서 돈을 관리하는 중인데, 애석하게도 항상 정신없는 재현이는 돈을 실수로 잘못 부르는 사고를 치기 일쑤였다.

재현이는 잘못된 수를 부를 때마다 0을 외쳐서, 가장 최근에 재민이가 쓴 수를 지우게 시킨다.

재민이는 이렇게 모든 수를 받아 적은 후 그 수의 합을 알고 싶어 한다. 재민이를 도와주자!

입력

첫 번째 줄에 정수 K가 주어진다. (1 ≤ K ≤ 100,000)

이후 K개의 줄에 정수가 1개씩 주어진다. 정수는 0에서 1,000,000 사이의 값을 가지며, 정수가 "0" 일 경우에는 가장 최근에 쓴 수를 지우고, 아닐 경우 해당 수를 쓴다.

정수가 "0"일 경우에 지울 수 있는 수가 있음을 보장할 수 있다.

출력

재민이가 최종적으로 적어 낸 수의 합을 출력한다. 최종적으로 적어낸 수의 합은 231-1보다 작거나 같은 정수이다.

예제 입력과 출력

정답

import sys
input = lambda : sys.stdin.readline().strip()

k=int(input())
st=[]

for i in range(k):
    a=int(input())
    if a == 0:
        st.pop()
    else:
        st.append(a)

print(sum(st))

백준 알고리즘 10773번 : https://www.acmicpc.net/problem/10773