[프로그래머스](파이썬)-방문길이-Level3-set사용문제

안녕하세요. 진또배기입니다. 오늘은 프로그래머스의 방문길이 문제에 대해 풀어보는 시간을 가져보겠습니다. 이 문제는 set을 사용하는 문제로 중복을 줄여주어야하기 때문입니다.

그러면, 시작하겠습니다!

1. 문제 소개

-문제링크: programmers.co.kr/learn/courses/30/lessons/49994

코딩테스트 연습 - 방문 길이

---

2. 슈도코드

앞서 말씀드린 것 처럼 set을 사용하는 문제입니다. 그 이유는 set은 원소를 unique하게 유지해주기 때문인데요.
여기서 A에서 --> B로 가는 것은 ==   B에서 -->A로 가는 것과 같은 것임을 고려해야합니다.

즉, set을 써서 지난 경로라면 unique하게 집계를 해주어야합니다.(Unique란 중복되지 않는 다는 말입니다.)

모든 명령어에 대해 다음을 수행
  1) 다음 방향으로 갈 수 없으면 명령어 무시
  2) 방문한 경로 기록:
           -A->B , B->A 경로를 모두 set에 넣어줌
  3) 다음 좌표로 내 좌표 업데이트
-set의 길이 /2값을 리턴 why? A->B , B->A 경로가 같기 때문에 원소길이 나누기 2

 

이해를 돕기 위해 시뮬레이션을 해보겠습니다.

dir ="RLD"라면 ("오,왼,아래"라면)

0. 현재 내 좌표 설정                               (0,0)
0-1. 지나온 경로를 저장하는 set만들기      paths = {}
----------------------------
1. 다음 방향(R)으로 갈 수 있는지 확인    next_point = (0,1)로 갈 수 있음  
2. set에 경로 넣기                                   set = {((0,0),(0,1)),((0,1),(0,0))}
3. 다음 좌표로 내 좌표 업데이트                current_point = next_point = (0,1)
----------------------------
1. 다음 방향(L)으로 갈 수 있는지 확인    next_point = (0,0)로 갈 수 있음  
2. set에 경로 넣기                                   set = {((0,0),(0,1)),((0,1),(0,0))} #원소가 unique하게(하나만) 유지됨
   원소가 있던 거면 아 이거 있던거네 하고 다시 안넣어줌
3. 다음 좌표로 내 좌표 업데이트                current_point = next_point = (0,0)
----------------------------
1. 다음 방향(D)으로 갈 수 있는지 확인    next_point = (1,0)으로 갈 수 있음  
2. set에 경로 넣기                                   set = {((0,0),(0,1)),((0,1),(0,0)),((0,0),(1,0)),((1,0),(0,0))}
3. 다음 좌표로 내 좌표 업데이트                current_point = next_point = (1,0)
-----------------------------
지나온 경로는 2개 = (set의 원소 수) /2 =2

---

3. 문제풀이

코드에 대한 설명은 노란색 주석으로 처리했습니다.

---

4. 알아야할 스킬 셋

이 문제에서 알아야할 스킬은 set을 사용하는 방법에 대해서 알아보겠습니다.

위에 말씀드린 것처럼 set은 중복값을 자동으로 제거해줍니다. 즉 모든 값이 유일합니다. 예시를 통해 알아보겠습니다.

1) set 선언
s = set()
a = set([2,4,6,8])	
a	
>>> {2,4,6,8}
s = {1, 5, 1, 1, 1, 3, 7}
s
>>> {1, 3, 5, 7}

2) 원소추가 add()
k = {100, 105}
k.add(50)
k
>>> {105, 50, 100}

3) set의 업데이트  -> 여러개의 값을 추가하거나 수정할 때 사용
k = {1, 2, 3}
k.update([3, 4, 5])
k
>>> {1, 2, 3, 4, 5}

4) 원소제거  --> remove() 와 discard()를 사용
s.remove(item) : item에 해당하는 원소를 제거하고, 없으면 KeyError 발생
s.discard(item) : item에 해당하는 원소를 제거하고, 없어도 에러발생하지 않음

마지막으로 기억해야 할 점은 set의 원소는 리스트는 불가능하고 튜플이 가능합니다. 만약 set에 리스트를 넣으려고 한다면 다음과 같은 에러가 발생합니다.

#튜플은 가능
set(map(tuple, seat))
>>> {(1, 1), (1, 2), (2, 1), (3, 4)}

#리스트는 에러발생
set(map(list, seat))
>>> TypeError: unhashable type: 'list'

---

오늘은 프로그래머스의 방문길이를 풀어보았습니다.

진또배기 올림