220421_w1_구현 - Sunny-W-Park/elice-sw2-algorithms GitHub Wiki

박선우 - #1138 한 줄로 서기

문제 해석

N: 총 인원 수
키가 1인 사람부터 순서대로, 본인 기준 왼쪽에 있는 키 큰 사람 수 -> 편의 상 '큰 사람 수' 라고 칭함

접근

'키가 작은 사람 순서'로 값이 주어졌기 때문에 idx 순서로 줄을 서도 뒤에 줄 서는 사람에게 영향을 주지 않음
즉, 줄을 설 때 왼쪽에 비어있는 자리 수 보다 크면서, 빈 자리일 경우 = 내가 설 자리가 됨

풀이 과정

dp = [0] * N 으로 줄 서는 위치 초기화
count = 왼쪽에 비어있는 자리 수를 세어주기
비어있는 자리 수가 큰 사람 수와 같아졌을때, 해당 idx+1부터 N-1자리 까지 dp값이 0인 자리에 배정

김재민 - #2947 나무 조각

문제 해석

섞여있는 1, 2, 3, 4, 5를 1, 2, 3, 4, 5이 될 때까지 이웃한 원소끼리 서로 변경
예시) index 0과 index 1을 비교하여 index가 낮은 수가 크다면 서로 변경
예시) index 1과 index 2을 비교하여 index가 낮은 수가 크다면 서로 변경
변경할 때마다 출력

접근

버블 정렬
index 0 부터 비교하면 마지막 비교시 에러나므로 index 1을 기준으로 index 0과 비교
flag = 1 : 마지막 index까지 해당 회차 변경이 끝나더라도 오름차순 정렬이 되지 않았음을 나타내기 위함

풀이 과정

flag = 1 로 초기화
while 문에서 flag = 1 이라면 계속 정렬
python swap : a, b = b, a (C언어와 다르게 swap이 가능)
마지막 index 까지 도달하고도 오름차순 정렬이 아니라면 flag = 1로 하여 while문 반복

백성호 - #2082 시계

문제 해석

시계의 고장난 4개의 숫자 디스플레이 (hh:mm)를 입력으로 받는다. 고장난 상태에서 가능한 시간 중에 가장 빠른 시간을 구해야 한다
디스플레이와 숫자는 3x5 문자열 형식으로 주어지고, 불이 꺼져있다면, “.”, 켜져있으면 “#”으로 나타낸다.

접근

시계 디스플레이와 0-9까지의 숫자를 쉽게 비교할 수 있게 동일한 방법으로 배열에 저장한다.
시계와 숫자를 비교했을 경우, 디스플레이가 “#”이면서 숫자가 “.” 일 때만, 숫자의 시계 배치가 불가능 하다. 나머지 경우에는 가능하다.

풀이 과정

입력 받는 시계 디스플레이와 숫자 0-9를 동일한 방식으로 3x5 배열에 저장.
임의의 하나의 시계 디스플레이와 임의의 숫자를 비교하는 함수를 만든다. (예: 첫번째 H와 숫자 0을 비교할 수 있는 함수)
비교했을 때 가능한 경우에는 True, 불가능한 경우에 False를 반환하게 한다.
가능한 빠른 시간을 구해야 하므로, 디스플레이마다 숫자를 작은 숫자부터 차례대로 비교하여 일치하는 가장 작은 수를 출력한다.

지의신 - #17070 파이프 옮기기1

문제 해석

2개의 칸을 차지하는 파이프는 좌표 (1,1),(1,2)에서 시작하여, 파이프의 한쪽을 (N,N)로 이동시키는 방법의 개수를 구하는 것이다.
이때 이동할 수 있는 방법은 오른쪽, 아래, 오른쪽-아래-대각선 방향이며 이동방향으로 45도 회전시킬 수 있다.
빈칸과 벽이 숫자 0과 1로 주어진다.

접근

2개의 칸을 차지하지만, 앞서는 한 칸만 고려하면 된다. 움직일 때 앞서는 칸으로 따라오기 때문이다.
파이프는 3가지의 상태를 가진다. 가로, 세로, 오른쪽-아래-대각선 방향으로 놓여진다. 상태를 0,1,2 정수로 표현한다.
dfs, bfs를 생각할 수 있다. bfs(반복문)이 항상 빠른 줄 알았지만 70%에서 시간초과 판정. dfs(재귀)는 통과한다. 이유는 모르겠다.

풀이 과정

한쪽의 좌표가 (n-1),(n-1)이면 result(방법의 개수)를 1 추가하고 return 한다.
한 칸 움직이고 좌표 범위를 검사하고 벽이 없으면 새로운 좌표와 방향 정보로 다시 dfs를 재귀로 호출한다.
가로와 대각선 방향일 때 오른쪽으로 이동, 세로와 대각선 방향일 때 아래로 이동, 그리고 마지막으로 대각선으로 이동할 수 있다.
마지막으로 result를 출력