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

 

10825번: 국영수

첫째 줄에 도현이네 반의 학생의 수 N (1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 한 줄에 하나씩 각 학생의 이름, 국어, 영어, 수학 점수가 공백으로 구분해 주어진다. 점수는 1보다 크거나 같고, 1

www.acmicpc.net

 

문제 해결을 위한 과정

이 문제는 정렬 알고리즘의 방식입니다. 문제에서 여러 가지 조건이 있는데 파이썬이 제공하는 기본적인 sort와 lambda만으로 해결이 가능한 문제입니다. 조건을 보면 다음과 같습니다.

  1. 국어 점수가 감소하는 순서로
  2. 국어 점수가 같으면 영어 점수가 증가하는 순서로
  3. 국어 점수와 영어 점수가 같으면 수학 점수가 감소하는 순서로
  4. 모든 점수가 같으면 이름이 사전 순으로 증가하는 순서로 (단, 아스키코드에서 대문자는 소문자보다 작으므로 사전 순으로 앞에 온다.)

이를 lambda에 넣을 조건이라고 생각하면 국어 점수는 감소하는 순서 즉 내림차순으로 정렬이 되어야 하므로 국어점수를 음수로 바꾸어서.

영어 점수의 경우 오름차순이므로 그대로.

수학점수의 경우 내림차순이므로 음수로 바꾸어서

이름의 경우 사전 순으로 증가하는 즉 오름차순이므로 그대로 lambda에 조건으로 넣어주면 되는 것입니다.

소스코드

 

1
2
3
4
5
6
7
8
9
10
N = int(input())
data = []
for i in range(N):
  name, kor, eng, math = input().split()
  data.append((name, int(kor), int(eng), int(math)))
 
data.sort(key = lambda x: ((-x[1]), x[2], (-x[3]), x[0]))
 
for i in range(N):
  print(data[i][0])
 cs

'알고리즘 > 백준' 카테고리의 다른 글

백준 알고리즘 2110: 공유기 설치 (Python)  (0) 2020.12.18
백준 알고리즘 18310: 안테나(Python)  (2) 2020.12.10
백준 알고리즘 16234: 인구이동(Python)  (0) 2020.12.07
백준 알고리즘 18428: 감시 피하기(Python)  (0) 2020.12.05
백준 알고리즘 14888: 연산자 끼워 넣기(Python)  (0) 2020.12.05

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

 

16234번: 인구 이동

N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모

www.acmicpc.net

문제 해결을 위한 과정

이 문제의 경우 bfs를 이용하여 해결하는 문제였습니다. 배열을 조회하다가 방문하지 않은 곳이 있다면 그 좌표에 한해서 절댓값의 차이가 L 이상 R이하인 곳을 탐색을 한 뒤 각각의 칸들의 평균값을 다시 대입을 해주면 되는 문제였습니다. 단지 까다로웠던 점은 while True: 를 통해 무한 반복할 때마다 visited를 계속 만들어서 계속 반복되게 해야 한다는 점이였습니다. 

소스코드

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
from collections import deque
import sys
input = sys.stdin.readline 
 
N, L, R = map(int, input().split())
graph = []
for i in range(N):
  graph.append(list(map(int, input().split())))
 
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
 
def bfs(xPos, yPos):
  q = deque()
  q.append((xPos, yPos))
  visited[xPos][yPos] = 1
  count = 1
  sum = graph[xPos][yPos]
  arr = [(xPos, yPos)]
  while q:
    x, y = q.popleft()
    for i in range(4):
      nx = x + dx[i]
      ny = y + dy[i]
      # 그래프의 범위를 벗어나지 않은경우
      if 0 <= nx < N and 0 <= ny < N: 
        # 방문한 곳이 아니고 차의 절댓값이 L, R 사이일때
        if visited[nx][ny] == 0 and L <= abs(graph[nx][ny]-graph[x][y]) <= R:
          visited[nx][ny] = 1
          sum += graph[nx][ny]
          count += 1
          q.append((nx, ny))
          arr.append((nx, ny))
 
  if count > 1: # count가 2 이상인 경우
    ans = sum // count
    for a, b in arr: # 해당 지역에 인구 이동
      graph[a][b] = ans
    return True
  return False
      
      
count = 0
while True:
  visited = [[0]*N for _ in range(N)] # N행 N열짜리 visited리스트
  flag = False # 인구 이동할 칸의 유무를 체크하는 플레그 False로 초기화
  for i in range(N):
    for j in range(N):
      if visited[i][j] == 0 and bfs(i, j) == True: # 방문하지 않았고 bfs의 반환값이 참이라면
        flag = True
  if flag == False: # 인구이동할 칸이 없는 경우
    break
  elif flag == True: # 인구이동한 칸이 있는 경우 count를 하나 증가
    count += 1
 
print(count)
 cs

'알고리즘 > 백준' 카테고리의 다른 글

백준 알고리즘 18310: 안테나(Python)  (2) 2020.12.10
백준 알고리즘 16234: 국영수(Python)  (0) 2020.12.09
백준 알고리즘 18428: 감시 피하기(Python)  (0) 2020.12.05
백준 알고리즘 14888: 연산자 끼워 넣기(Python)  (0) 2020.12.05
백준 알고리즘 18405: 경쟁적 전염(Python)  (0) 2020.12.05

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

 

18428번: 감시 피하기

NxN 크기의 복도가 있다. 복도는 1x1 크기의 칸으로 나누어지며, 특정한 위치에는 선생님, 학생, 혹은 장애물이 위치할 수 있다. 현재 몇 명의 학생들은 수업시간에 몰래 복도로 빠져나왔는데, 복

www.acmicpc.net

문제 해결을 위한 과정

이 문제는 BFS로 해결하기보다는 문제의 조건을 따라서 해결하면 더 쉬웠던 문제입니다. 처음에 그래프입력을 받으면서 x인 곳을 blank라는 리스트에 따로 추가하고 T인 곳을 teacher이라는 리스트에 따로 추가를 해줍니다. 선생님들은 상, 하 , 좌, 우 4곳으로 볼 수 있고 방해물이 없다면 그래프의 끝까지 조회할 수 있으므로 방향 리스트인 dx, dy를 만들고 bfs함수를 정의합니다. 각 방향을 끝까지 조회하면서 빈칸인 경우 T로 방문처리를 해주거나, 방해물이 있는경우 그 뒤쪽은 볼수 없는 경우를 처리해주고, 학생을 찾은 경우 바로 bfs함수에서 False를 return해주면 쉽게 해결할 수 있습니다. 학생을 찾지 못한 경우는 True를 return해주면 되겠습니다.

소스코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
from collections import deque
from itertools import combinations
import copy
 
n = int(input())
graph = []
teacher = []
blank = []
 
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
 
for i in range(n):
  graph.append(list(input().split()))
  for j in range(n):
    if graph[i][j] == 'T':
      teacher.append((i, j))
    elif graph[i][j] == "X":
      blank.append((i, j))
 
def bfs(): # 학생 찾으면 False 반환
  q = deque(teacher)
  test_graph = copy.deepcopy(graph)
  while q:
    x, y = q.popleft()
    for i in range(4):
      temp_x, temp_y = x, y
      while True:
        nx = temp_x + dx[i]
        ny = temp_y + dy[i]
        if 0 <= nx < n and 0 <= ny < n:
          if test_graph[nx][ny] == 'X':
            test_graph[nx][ny] = 'T'
          elif test_graph[nx][ny] == 'S':
            return False
          elif test_graph[nx][ny] == 'O':
            break
          temp_x, temp_y = nx, ny
        else:
          break
  return True
 
check = False
for data in list(combinations(blank, 3)):
  for x, y in data:
    graph[x][y] = 'O'
  if bfs():
    check = True
    break
  for x, y in data:
    graph[x][y] = 'X'
    
if check:
  print("YES")
else:
  print("NO")
 cs

'알고리즘 > 백준' 카테고리의 다른 글

백준 알고리즘 16234: 국영수(Python)  (0) 2020.12.09
백준 알고리즘 16234: 인구이동(Python)  (0) 2020.12.07
백준 알고리즘 14888: 연산자 끼워 넣기(Python)  (0) 2020.12.05
백준 알고리즘 18405: 경쟁적 전염(Python)  (0) 2020.12.05
백준 알고리즘 14502: 연구소(Python)  (0) 2020.12.05

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

 

18405번: 경쟁적 전염

첫째 줄에 자연수 N, K가 공백을 기준으로 구분되어 주어진다. (1 ≤ N ≤ 200, 1 ≤ K ≤ 1,000) 둘째 줄부터 N개의 줄에 걸쳐서 시험관의 정보가 주어진다. 각 행은 N개의 원소로 구성되며, 해당 위치

www.acmicpc.net

문제 해결을 위한 과정

이 문제의 경우 BFS만 알고 있다면 쉽게 해결할 수 있는 문제입니다. 그래프를 입력을 받을 때 0이 아닌 즉 바이러스가 있는 부분들에 대한 좌표를 따로 virus라는 리스트를 만들어서 그 리스트에 있는 좌표값들에 대해서만 BFS를 수행하면 되는 것입니다. 이때 문제에서 알 수 있듯이 이미 바이러스가 퍼진 구역에는 어떠한 바이러스도 퍼질 수 없으므로 그래프에서 해당 좌표의 지역이 0 인 경우 즉 비어있는 경우만 탐색을 할 수 있습니다. 또한 문제에서 숫자가 낮은 바이러스가 우선적으로 퍼지는 조건이 있습니다. 이 경우는 문제 해결을 위한 팁에서 알아보겠습니다.

문제 해결을 위한 팁

저의 경우는 바이러스가 있는 곳을 리스트에 넣을때 해당 좌표에 있는 바이러스에 값과 좌표를 리스트에 저장했습니다. 만약 입력 예시 1의 경우 0 행 0열에 있는 바이러스가 1 이기 때문에 virus.append((graph[i][j], i, j)) 이렇게 저장했습니다. 이 형태로 저장을 하게 되면 입력을 다 한 후 virus.sort()를 하게 되면 맨 앞 원소를 기준으로 오름차순으로 정렬을 하기 때문에 별도의 처리 없이 오름차순 된 virus 리스트 그대로 BFS를 수행하면 숫자가 낮은 바이러스부터 우선적으로 탐색을 할 수 있습니다.

소스코드

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
from collections import deque
 
N, K = map(int, input().split())
graph = []
virus = []
for i in range(N):
  graph.append(list(map(int, input().split())))
  for j in range(N):
    if graph[i][j] != 0:
      virus.append(((graph[i][j], i, j)))
S, X, Y = map(int, input().split())
 
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
 
def bfs(s, X, Y):
  q = deque(virus)
  count = 0
  while q:
    if count == s:
      break
    for _ in range(len(q)):
      prev, x, y = q.popleft()
      for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if 0 <= nx < N and 0 <= ny < N:
          if graph[nx][ny] == 0:
            graph[nx][ny] = graph[x][y]
            q.append((graph[nx][ny], nx, ny))
    count += 1
  return graph[X-1][Y-1]
 
virus.sort()
print(bfs(S, X, Y))
 cs

'알고리즘 > 백준' 카테고리의 다른 글

백준 알고리즘 18428: 감시 피하기(Python)  (0) 2020.12.05
백준 알고리즘 14888: 연산자 끼워 넣기(Python)  (0) 2020.12.05
백준 알고리즘 14502: 연구소(Python)  (0) 2020.12.05
백준 알고리즘 18352: 특정 거리의 도시 찾기(Python)  (0) 2020.12.04
백준 알고리즘 15686: 치킨 배달 (Python)  (0) 2020.11.30

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

 

14502번: 연구소

인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크

www.acmicpc.net

문제

문제 해결을 위한 과정

이 문제의 경우 조건을 보면 8 x 8로 크기가 제한이 되어있는 것을 알 수 있습니다. 또한 3가지의 벽을 세우는 경우 이므로 64가지의 경우에서 순서에 상관없이 3을 뽑는 즉 64C3이기 때문에 완전 탐색으로 해결해야 함을 알 수 있습니다. 따라서 그래프를 입력받을 때 바이러스인 좌표를 저장하는 리스트와 빈칸을 저장하는 리스트를 각각 만든 후 빈칸의 영역에서 combinations을 사용하여 3개의 구역에 벽을 세운 후 BFS를 이용하여 문제를 해결합니다.

문제 해결을 위한 팁

조합을 이용해 3가지 구역에 대해서 벽을 세운 후 BFS를 수행한 후 다시 벽을 없애주어야 합니다. 그래야 다른 지역에 벽을 세울 수 있기 때문입니다.

소스코드

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
from itertools import combinations
from collections import deque
import copy
 
N, M = map(int, input().split())
graph = []
blank = []
virus = []
 
for i in range(N):
  graph.append(list(map(int, input().split())))
  for j in range(M):
    if graph[i][j] == 0:
      blank.append((i, j))
    elif graph[i][j] == 2:
      virus.append((i, j))
 
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
 
def bfs():
  testgraph = copy.deepcopy(graph)
  q = deque(virus)
  while q:
    x, y = q.popleft()
    for i in range(4):
      nx = x + dx[i]
      ny = y + dy[i]
      if 0 <= nx < N and 0 <= ny < M:
          if testgraph[nx][ny] == 0:
            testgraph[nx][ny] = 2
            q.append((nx, ny))
 
  count = 0
  for i in range(N):
    for j in range(M):
      if testgraph[i][j] == 0:
        count += 1
  
  return count
 
 
answer = 0
for data in combinations(blank, 3):
  for x, y in data:
    graph[x][y] = 1
  answer = max(answer, bfs())
  for x, y in data:
    graph[x][y] = 0
 
print(answer)
 cs

'알고리즘 > 백준' 카테고리의 다른 글

백준 알고리즘 14888: 연산자 끼워 넣기(Python)  (0) 2020.12.05
백준 알고리즘 18405: 경쟁적 전염(Python)  (0) 2020.12.05
백준 알고리즘 18352: 특정 거리의 도시 찾기(Python)  (0) 2020.12.04
백준 알고리즘 15686: 치킨 배달 (Python)  (0) 2020.11.30
백준 알고리즘 3190: 뱀(Python, c++)  (0) 2020.11.29

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

 

18352번: 특정 거리의 도시 찾기

첫째 줄에 도시의 개수 N, 도로의 개수 M, 거리 정보 K, 출발 도시의 번호 X가 주어진다. (2 ≤ N ≤ 300,000, 1 ≤ M ≤ 1,000,000, 1 ≤ K ≤ 300,000, 1 ≤ X ≤ N) 둘째 줄부터 M개의 줄에 걸쳐서 두 개

www.acmicpc.net

문제 

문제 해결을 위한 과정

이 문제의 경우 BFS를 통해서 쉽게 해결할 수 있는 문제였습니다. 정답률은 32퍼센트로 좀 낮은 편인데 난이도에 비해서는 정답률이 조금 낮게 나온 것 같습니다. BFS라는 개념을 정확히 알면 쉬운 문제입니다. 만일 BFS를 잘 모르시겠다면 https://bgspro.tistory.com/15?category=981927

 

BFS 너비 우선탐색 (Python)

BFS란? BFS 즉 Breath-Frist-Search는 영어를 해석한 그대로 넓이를 우선으로 탐색하는 즉 깊이 우선 탐색입니다. 넓이를 우선 탐색한다는 것은 그래프에서 한 노드에서 연결된 다른 노드들을 퍼져가면

bgspro.tistory.com

한번 보고 오시는걸 추천드립니다. 예시의 그림을 보면 노드가 양방향으로 연결이 된 것이 아닌 단방향으로 연결이 되어있는 것을 확인할 수 있습니다.  시작 지점부터 BFS방식을 통해 탐색을 해 나아가면 예시의 그림을 예로 들면 첫 번째로 탐색이 되는 2, 3 그리고 두 번째로 탐색이 되는 4를 통해 몇 번째로 탐색이 되느냐가 시작 지점 노드 1부터 얼마만큼의 거리가 떨어져 있는지를 의미하는 것이라고 보면 되겠습니다. 따라서 몇 번째로 탐색이 되는지 확인을 한 뒤 입력받은 k와 같다면 어떠한 리스트에 추가를 한 뒤 오름차순으로 정렬을 하면 되는 문제였습니다.

소스코드 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
import sys
from collections import deque
# 입력을 빠르게 하기 위함 이 방식이 아닌 일반 input일 경우 pypy3는 통과하지만 python3로는 통과하지 못함
input = sys.stdin.readline 
 
N, M, K, X = map(int, input().split())
graph = [[] for _ in range(1 + N)]
visited = [False] * (1 + N)
answer = []
 
for i in range(M):
  a, b = map(int, input().split())
  graph[a].append(b)
 
def bfs(graph, x, visited):
  queue = deque([x])
  visited[x] = True
  count = 1
  while queue:
    for _ in range(len(queue)): # 몇번째로 탐색이 되는지 확인하기 위한 for문
      v = queue.popleft()
      for i in graph[v]:
        if not visited[i] and count == K: # 방문하지 않고 K와 ㅏㅌ은 경우
          answer.append(i)
        if not visited[i]: # 방문하지 않은 경우
          visited[i] = True
          queue.append(i)
    count += 1
 
bfs(graph, X, visited)
answer.sort() # 오름차순으로 
 
if len(answer) != 0:
  for data in answer:
    print(data)
else:
  print(-1)
 
 
 cs

'알고리즘 > 백준' 카테고리의 다른 글

백준 알고리즘 18405: 경쟁적 전염(Python)  (0) 2020.12.05
백준 알고리즘 14502: 연구소(Python)  (0) 2020.12.05
백준 알고리즘 15686: 치킨 배달 (Python)  (0) 2020.11.30
백준 알고리즘 3190: 뱀(Python, c++)  (0) 2020.11.29
백준 알고리즘 1914: 하노이 탑  (0) 2020.11.28

 

 

15686번: 치킨 배달

크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸

www.acmicpc.net

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

문제

문제 해결을 위한 과정

이 문제의 경우 가장 중요했던 것은 조합 즉 combination을 이용하는 것이었습니다. 만일 a, b, c, d, e라는 5개의 치킨집이 있을 때 3개를 뽑는 경우라면 a, b, c와 a,c,b와 b,a,c와 b,c,a 등등 이렇게 뽑은 것이라면 같은 경우입니다. 즉 순서가 중요하지 않은 조합을 이용하여 해결하는 것입니다. 파이썬에서 조합을 사용하기 위해서는 다음의 코드를 추가합니다.

from itertools import combinations

이 방법을 통해 치킨집들중 입력받은 M개를 고른 후 각각의 집마다 치킨 거리를 구한 후 도시의 최소 치킨 거리를 구하면 됩니다.

문제 해결을 위한 팁

None

소스코드

town.append(list(map(<span

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
from itertools import combinations
 
def compute(data):
  answer = 0
  for i in range(len(house)):
    a, b = house[i]
    temp = int(1e9)
    for x, y in data:
      temp = min(temp, abs(x - a) + abs(y - b))
    answer += temp
  return answer
 
N, M = map(int, input().split())
town = []
house = []
store = []
 
for i in range(N):
  town.append(list(map(int, input().split())))
  for j in range(N):
    if town[i][j] == 1:
      house.append((i, j))
    elif town[i][j] == 2:
      store.append((i, j))
 
ans = int(1e9)
for data in combinations(store, M):
  ans = min(ans, compute(data))
 
print(ans)
 
 
 cs

'알고리즘 > 백준' 카테고리의 다른 글

백준 알고리즘 14502: 연구소(Python)  (0) 2020.12.05
백준 알고리즘 18352: 특정 거리의 도시 찾기(Python)  (0) 2020.12.04
백준 알고리즘 3190: 뱀(Python, c++)  (0) 2020.11.29
백준 알고리즘 1914: 하노이 탑  (0) 2020.11.28
백준 알고리즘 18406: 럭키 스트레이트 (Python)  (0) 2020.11.27

 

 

코딩테스트 연습 - 모의고사

수포자는 수학을 포기한 사람의 준말입니다. 수포자 삼인방은 모의고사에 수학 문제를 전부 찍으려 합니다. 수포자는 1번 문제부터 마지막 문제까지 다음과 같이 찍습니다. 1번 수포자가 찍는

programmers.co.kr

https://programmers.co.kr/learn/courses/30/lessons/42840

문제

문제 설명

수포자는 수학을 포기한 사람의 준말입니다. 수포자 삼인방은 모의고사에 수학 문제를 전부 찍으려 합니다. 수포자는 1번 문제부터 마지막 문제까지 다음과 같이 찍습니다.

1번 수포자가 찍는 방식: 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, ...
2번 수포자가 찍는 방식: 2, 1, 2, 3, 2, 4, 2, 5, 2, 1, 2, 3, 2, 4, 2, 5, ...
3번 수포자가 찍는 방식: 3, 3, 1, 1, 2, 2, 4, 4, 5, 5, 3, 3, 1, 1, 2, 2, 4, 4, 5, 5, ...

1번 문제부터 마지막 문제까지의 정답이 순서대로 들은 배열 answers가 주어졌을 때, 가장 많은 문제를 맞힌 사람이 누구인지 배열에 담아 return 하도록 solution 함수를 작성해주세요.

제한 조건

  • 시험은 최대 10,000 문제로 구성되어있습니다.
  • 문제의 정답은 1, 2, 3, 4, 5중 하나입니다.
  • 가장 높은 점수를 받은 사람이 여럿일 경우, return하는 값을 오름차순 정렬해주세요.

입출력 예

answersreturn

[1,2,3,4,5] [1]
[1,3,2,4,2] [1,2,3]

입출력 예 설명

입출력 예 #1

  • 수포자 1은 모든 문제를 맞혔습니다.
  • 수포자 2는 모든 문제를 틀렸습니다.
  • 수포자 3은 모든 문제를 틀렸습니다.

따라서 가장 문제를 많이 맞힌 사람은 수포자 1입니다.

입출력 예 #2

  • 모든 사람이 2문제씩을 맞췄습니다.
문제 해결을 위한 과정

Level 1 문제로서 쉬운 문제였습니다. 단순하게 사람을 p1, p2, p3라 한다면 시험문제가 최대 10,000개 이므로 다음과 같습니다.

 

p1의 경우 [1, 2, 3, 4, 5] * 2000 

p2의 경우 [2, 1, 2, 3, 2, 4, 2, 5] * 2000 

p3의 경우 [3, 3, 1, 1, 2, 2, 4, 4, 5, 5] * 1000

여기서 p2의 경우 반복되는 숫자가 8 이므로 원래는 대략 1300을 곱해줘야 하지만 대략적인 값으로 2000번 반복을 시켰습니다. 그 후 입력으로 들어오는 answers 리스트와 비교하며 찍은 답이 정답이라면 각각의 카운트를 증가시켜 줍니다. 

문제 해결을 위한 팁

저의 경우는 정답자가 여러 명인 경우 오름차순으로 정렬을 하기 위해 임시 리스트 temp = []를 선언하였습니다. 그 후 각 사람별 맞힌 정답의 수와 각 사람(몇 번째 사람인지)에 대한 정보를 묶어서 temp리스트에 append 해주었습니다.

이 방법을 통해 문제를 많이 맞힌 사람별로 정렬이 가능하고 그 사람이 몇 번째 사람인지 조회도 가능합니다.

소스코드

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
def solution(answers):
    answer = []
    people_1 = [1, 2, 3, 4, 5] * 2000
    people_2 = [2, 1, 2, 3, 2, 4, 2, 5] * 2000
    people_3 = [3, 3, 1, 1, 2, 2, 4, 4, 5, 5] * 1000
    num_of_1 = 0; num_of_2 = 0; num_of_3 = 0
    
    for i in range(len(answers)):
        if answers[i] == people_1[i]:
            num_of_1 += 1
        if answers[i] == people_2[i]:
            num_of_2 += 1
        if answers[i] == people_3[i]:
            num_of_3 += 1
    
    temp = [(num_of_1,1), (num_of_2,2), (num_of_3,3)] 
    temp.sort(reverse = True)
    temp.append((-1, -1)) # 마지막 원소를 비교하기 위해 의미없는 수 입력 index out of range를 방지 하기 위함
    
    for i in range(3):
        if temp[i][0] != temp[i+1][0]: # 내림차순을 한 결과가 다음 원소랑 다르다면 앞 사람이 무조건 많이 맞춘 사람이므로 앞 사람만 append 해줌
            answer.append(temp[i][1])
            answer.sort()
            return answer
        elif temp[i][0] == temp[i+1][0]: 
            answer.append(temp[i][1])
    answer.sort()
    return answer
 cs

'알고리즘 > 프로그래머스' 카테고리의 다른 글

괄호 변환 (Python)  (0) 2020.12.05
자물쇠와 열쇠 (Python)  (0) 2020.12.03
기둥과 보 설치 (Python)  (0) 2020.11.29
완주하지 못한 선수 (Level 1 Python)  (0) 2020.11.28
두 개 뽑아서 더하기 (Level 1 Python)  (0) 2020.11.28

+ Recent posts

티스토리툴바