- 같은 숫자는 싫어
문제 설명
배열 arr가 주어집니다. 배열 arr의 각 원소는 숫자 0부터 9까지로 이루어져 있습니다. 이때, 배열 arr에서 연속적으로 나타나는 숫자는 하나만 남기고 전부 제거하려고 합니다. 단, 제거된 후 남은 수들을 반환할 때는 배열 arr의 원소들의 순서를 유지해야 합니다. 예를 들면,
- arr = [1, 1, 3, 3, 0, 1, 1] 이면 [1, 3, 0, 1] 을 return 합니다.
- arr = [4, 4, 4, 3, 3] 이면 [4, 3] 을 return 합니다.
배열 arr에서 연속적으로 나타나는 숫자는 제거하고 남은 수들을 return 하는 solution 함수를 완성해 주세요.
제한사항
- 배열 arr의 크기 : 1,000,000 이하의 자연수
- 배열 arr의 원소의 크기 : 0보다 크거나 같고 9보다 작거나 같은 정수
입출력 예
| arr | answer |
|---|---|
| [1,1,3,3,0,1,1] | [1,3,0,1] |
| [4,4,4,3,3] | [4,3] |
입출력 예 설명
입출력 예 #1,2
문제의 예시와 같습니다.
def solution(arr):
# 구조상 처음의 요소는 리스트에 넣을 수 없고 무조건 들어가야하기 때문에 초기에 삽입
result = [arr[0]]
# 이후로 순회를 하면서 만약 뒤에 요소가 같지 않을 때만 결과 리스트에 추가
for i in range(len(arr) - 1):
if arr[i] != arr[i + 1] :
result.append(arr[i + 1])
answer = result
return answer배울점
상당히 쉬운 문제였지만 처음에 풀 때 당시 중복 제거만 있는 줄 알고 오류가 났었다. 문제를 이해했다고 해서 예시를 건너 뛰는 무식한 행동은 하지말자!
- 두 개 뽑아서 더하기
문제 설명
정수 배열 numbers가 주어집니다. numbers에서 서로 다른 인덱스에 있는 두 개의 수를 뽑아 더해서 만들 수 있는 모든 수를 배열에 오름차순으로 담아 return 하도록 solution 함수를 완성해주세요.
제한사항
- numbers의 길이는 2 이상 100 이하입니다.
- numbers의 모든 수는 0 이상 100 이하입니다.
입출력 예
| numbers | result |
|---|---|
[2,1,3,4,1] | [2,3,4,5,6,7] |
[5,0,2,7] | [2,5,7,9,12] |
입출력 예 설명
입출력 예 #1
- 2 = 1 + 1 입니다. (1이 numbers에 두 개 있습니다.)
- 3 = 2 + 1 입니다.
- 4 = 1 + 3 입니다.
- 5 = 1 + 4 = 2 + 3 입니다.
- 6 = 2 + 4 입니다.
- 7 = 3 + 4 입니다.
- 따라서
[2,3,4,5,6,7]을 return 해야 합니다.
입출력 예 #2
- 2 = 0 + 2 입니다.
- 5 = 5 + 0 입니다.
- 7 = 0 + 7 = 5 + 2 입니다.
- 9 = 2 + 7 입니다.
- 12 = 5 + 7 입니다.
- 따라서
[2,5,7,9,12]를 return 해야 합니다.
def solution(numbers):
result = []
for i in range(len(numbers)):
for j in range(len(numbers)):
if i != j :
result.append(numbers[i] + numbers[j])
print(list(set(result)))
answer = list(set(result))
answer.sort()
return answer배울점
처음에 풀때만 해도 오름차순으로 굳이 정렬을 하지 않아도 된다고 생각했다. 왜냐하면 어차피 set으로 형변환을 하면 양수들은 알아서 크기별로 정렬이 된다. 애초에 범위도 0부터 100까지라서 당연히 될꺼라고 생각했지만
실행결과 4, 5번 케이스에서 오류가 발생하였다. 찾아보니 범위는 0이상 100이하지만 음수도 포함이 된다고 생각해야한다고 해서 .sort() method를 추가하였다. sorted() 함수는 프로그래머스 툴에서는 실행이 불가능하다.
프로그래머스 제대로 문제 안만드냐!!!
- 게임 맵 최단거리
문제 설명
ROR 게임은 두 팀으로 나누어서 진행하며, 상대 팀 진영을 먼저 파괴하면 이기는 게임입니다. 따라서, 각 팀은 상대 팀 진영에 최대한 빨리 도착하는 것이 유리합니다.
지금부터 당신은 한 팀의 팀원이 되어 게임을 진행하려고 합니다. 다음은 5 x 5 크기의 맵에, 당신의 캐릭터가 (행: 1, 열: 1) 위치에 있고, 상대 팀 진영은 (행: 5, 열: 5) 위치에 있는 경우의 예시입니다.
위 그림에서 검은색 부분은 벽으로 막혀있어 갈 수 없는 길이며, 흰색 부분은 갈 수 있는 길입니다. 캐릭터가 움직일 때는 동, 서, 남, 북 방향으로 한 칸씩 이동하며, 게임 맵을 벗어난 길은 갈 수 없습니다.
아래 예시는 캐릭터가 상대 팀 진영으로 가는 두 가지 방법을 나타내고 있습니다.
- 첫 번째 방법은 11개의 칸을 지나서 상대 팀 진영에 도착했습니다.
- 두 번째 방법은 15개의 칸을 지나서 상대팀 진영에 도착했습니다.
위 예시에서는 첫 번째 방법보다 더 빠르게 상대팀 진영에 도착하는 방법은 없으므로, 이 방법이 상대 팀 진영으로 가는 가장 빠른 방법입니다.
만약, 상대 팀이 자신의 팀 진영 주위에 벽을 세워두었다면 상대 팀 진영에 도착하지 못할 수도 있습니다. 예를 들어, 다음과 같은 경우에 당신의 캐릭터는 상대 팀 진영에 도착할 수 없습니다.
게임 맵의 상태 maps가 매개변수로 주어질 때, 캐릭터가 상대 팀 진영에 도착하기 위해서 지나가야 하는 칸의 개수의 최솟값을 return 하도록 solution 함수를 완성해주세요. 단, 상대 팀 진영에 도착할 수 없을 때는 -1을 return 해주세요.
제한사항
- maps는 n x m 크기의 게임 맵의 상태가 들어있는 2차원 배열로, n과 m은 각각 1 이상 100 이하의 자연수입니다.
- n과 m은 서로 같을 수도, 다를 수도 있지만, n과 m이 모두 1인 경우는 입력으로 주어지지 않습니다.
- maps는 0과 1로만 이루어져 있으며, 0은 벽이 있는 자리, 1은 벽이 없는 자리를 나타냅니다.
- 처음에 캐릭터는 게임 맵의 좌측 상단인 (1, 1) 위치에 있으며, 상대방 진영은 게임 맵의 우측 하단인 (n, m) 위치에 있습니다.
입출력 예
| maps | answer |
|---|---|
| [[1,0,1,1,1],[1,0,1,0,1],[1,0,1,1,1],[1,1,1,0,1],[0,0,0,0,1]] | 11 |
| [[1,0,1,1,1],[1,0,1,0,1],[1,0,1,1,1],[1,1,1,0,0],[0,0,0,0,1]] | -1 |
입출력 예 설명
입출력 예 #1
주어진 데이터는 다음과 같습니다.
캐릭터가 적 팀의 진영까지 이동하는 가장 빠른 길은 다음 그림과 같습니다.
따라서 총 11칸을 캐릭터가 지나갔으므로 11을 return 하면 됩니다.
입출력 예 #2
문제의 예시와 같으며, 상대 팀 진영에 도달할 방법이 없습니다. 따라서 -1을 return 합니다.
from collections import deque
def solution(maps):
def bfs(x, y, d) :
# 전체 범위 설정
height = len(maps)
width = len(maps[0])
# 상 하 좌 우
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
# 큐 생성
q = deque()
# 시발점
q.append((x, y, d))
# 초기 거리 0으로 설정
distance = 0
while q:
x, y, d = q.popleft()
# 이 문제에서는 끝 좌표가 목표지점이기 떄문에 끝 좌표에 도달시 거리 출력
if x == height - 1 and y == width - 1:
return d
# 상하좌우 방향으로 다음 좌표 탐색
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
# 범위안에 있고
if 0 <= nx < height and 0 <= ny < width :
# 만약 갈 수 있는 곳이라면
if maps[nx][ny] == 1:
# 거리 + 1를 해주고 다음 좌표와 묶어서 queue에 추가
nd = d + 1
q.append((nx, ny, nd))
# 방문한 좌표이기 때문에 0으로 처리
maps[nx][ny] = 0
# 만약 끝좌표에 도달하지 못하고 q에 남은 값이 없으면 좌표 도달 불가능이기 때문에 -1출력
return -1
return bfs(0, 0, 1)배울점
오랜만에 bfs문제를 푸니 살짝 감이 오기까지 조금 시간이 걸렸다. 최단 거리 구하는 알고리즘 문제는 이 방법으로 푸는건 아니였던거 같은데 일단 queue에 거리까지 같이 넣어서 while문으로 돌렸음.
배웠던 정석으로 풀면 재귀식으로 풀었던 거 같은데 찾아봐야겠다.
